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:

a1 = 1
then for n > 1, an is the smallest positive integer such that every pairwise sum

ai + aj 
is distinct, for all i and j less than or equal to n.

The Task

 Find and display, here, on this page the first 30 terms of the Mian–Chowla sequence.
 Find and display, here, on this page the 91st through 100th terms of the Mian–Chowla sequence.


Demonstrating working through the first few terms longhand:

a1 = 1
1 + 1 = 2
Speculatively try a2 = 2

1 + 1 = 2
1 + 2 = 3
2 + 2 = 4
There are no repeated sums so 2 is the next number in the sequence.

Speculatively try a3 = 3

1 + 1 = 2
1 + 2 = 3 
1 + 3 = 4
2 + 2 = 4
2 + 3 = 5
3 + 3 = 6
Sum of 4 is repeated so 3 is rejected.

Speculatively try a3 = 4

1 + 1 = 2
1 + 2 = 3
1 + 4 = 5
2 + 2 = 4
2 + 4 = 6
4 + 4 = 8
There are no repeated sums so 4 is the next number in the sequence.

And so on...

See also

 OEIS:A005282 Mian-Chowla sequence
# Find Mian-Chowla numbers: an
                     where: ai = 1,
                       and: an = smallest integer such that ai + aj is unique
                                             for all i, j in 1 .. n && i <= j
#
BEGIN
    INT max mc           = 100;
    [ max mc ]INT mc;
    INT curr size       :=      0; # initial size of the array     #
    INT size increment   = 10 000; # size to increase the array by #
    REF[]BOOL is sum    := HEAP[ 1 : 0 ]BOOL;
    INT mc count        := 1;
    FOR i WHILE mc count <= max mc DO
        # assume i will be part of the sequence                    #
        mc[ mc count ]  := i;
        # check the sums                                           #
        IF  ( 2 * i ) > curr size THEN
            # the is sum array is too small - make a larger one    #
            REF[]BOOL new sum = HEAP[ curr size + size increment ]BOOL;
            new sum[ 1 : curr size ] := is sum;
            FOR n TO size increment DO new sum[ curr size + n ] := FALSE OD;
            curr size  +:= size increment;
            is sum      := new sum
        FI;
        BOOL is unique  := TRUE;
        FOR mc pos TO mc count WHILE is unique := NOT is sum[ i + mc[ mc pos ] ] DO SKIP OD;
        IF is unique THEN
            # i is a sequence element - store the sums             #
            FOR k TO mc count DO is sum[ i + mc[ k ] ] := TRUE OD;
            mc count +:= 1
        FI
    OD;
 
    # print parts of the sequence                                  #
    print( ( "Mian Chowla sequence elements 1..30:", newline ) );
    FOR i TO 30 DO print( ( " ", whole( mc[ i ], 0 ) ) ) OD;
    print( ( newline ) );
    print( ( "Mian Chowla sequence elements 91..100:", newline ) );
    FOR i FROM 91 TO 100 DO print( ( " ", whole( mc[ i ], 0 ) ) ) OD
 
END