How to resolve the algorithm Mian-Chowla sequence step by step in the XPL0 programming language

Published on 12 May 2024 09:40 PM

How to resolve the algorithm Mian-Chowla sequence step by step in the XPL0 programming language

Table of Contents

Problem Statement

The Mian–Chowla sequence is an integer sequence defined recursively.

Mian–Chowla is an infinite instance of a Sidon sequence, and belongs to the class known as B₂ sequences.

The sequence starts with: then for n > 1, an is the smallest positive integer such that every pairwise sum is distinct, for all i and j less than or equal to n.

Demonstrating working through the first few terms longhand: Speculatively try a2 = 2 There are no repeated sums so 2 is the next number in the sequence. Speculatively try a3 = 3 Sum of 4 is repeated so 3 is rejected. Speculatively try a3 = 4 There are no repeated sums so 4 is the next number in the sequence. And so on...

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Mian-Chowla sequence step by step in the XPL0 programming language

Source code in the xpl0 programming language

define N = 100;
define NN = (N * (N+1)) >> 1;

func Contains(Lst, Item, Size);
int  Lst, Item, Size, I;
[for I:= Size-1 downto 0 do
    if Item = Lst(I) then return true;
return false;
];
 
int MC(N);

proc MianChowla;
int  Sums(NN), Sum, LE, SS, I, J, K;
[MC(0):= 1;
Sums(0):= 2;
SS:= 1;
for I:= 1 to N-1 do
    [LE:= SS;
    J:= MC(I-1) + 1;
    MC(I):= J;
    K:= 0;
    loop    [Sum:= MC(K) + J;
            if Contains(Sums, Sum, SS) then
                [SS:= LE;
                J:= J+1;
                MC(I):= J;
                K:= 0;
                ]
            else
                [Sums(SS):= Sum;
                SS:= SS+1;
                K:= K+1;
                if K > I then quit;
                ];
            ];
        ];
];
 
int  I;
[MianChowla;
Text(0, "The first 30 terms of the Mian-Chowla sequence are:^m^j");
for I:= 0 to 30-1 do
    [IntOut(0, MC(I));  ChOut(0, ^ )];
Text(0, "^m^j^m^jTerms 91 to 100 of the Mian-Chowla sequence are:^m^j");
for I:= 90 to 100-1 do 
    [IntOut(0, MC(I));  ChOut(0, ^ )];
CrLf(0);
]

  

You may also check:How to resolve the algorithm Sorting algorithms/Cocktail sort with shifting bounds step by step in the Phix programming language
You may also check:How to resolve the algorithm Luhn test of credit card numbers step by step in the Java programming language
You may also check:How to resolve the algorithm Brownian tree step by step in the Octave programming language
You may also check:How to resolve the algorithm Factors of an integer step by step in the C++ programming language
You may also check:How to resolve the algorithm Cistercian numerals step by step in the Python programming language