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