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
 
import java.util.Arrays;
 
public class MianChowlaSequence {
 
    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        System.out.println("First 30 terms of the Mian–Chowla sequence.");
        mianChowla(1, 30);
        System.out.println("Terms 91 through 100 of the Mian–Chowla sequence.");
        mianChowla(91, 100);
        long end = System.currentTimeMillis();
        System.out.printf("Elapsed = %d ms%n", (end-start));
    }
 
    private static void mianChowla(int minIndex, int maxIndex) {
        int [] sums = new int[1];
        int [] chowla = new int[maxIndex+1];
        sums[0] = 2;
        chowla[0] = 0;
        chowla[1] = 1;
        if ( minIndex == 1 ) {
            System.out.printf("%d ", 1);
        }
        int chowlaLength = 1;
        for ( int n = 2 ; n <= maxIndex ; n++ ) {
 
            //  Sequence is strictly increasing.
            int test = chowla[n - 1];
            //  Bookkeeping.  Generate only new sums.
            int[] sumsNew = Arrays.copyOf(sums, sums.length + n);
            int sumNewLength = sums.length;
            int savedsSumNewLength = sumNewLength;
 
            //  Generate test candidates for the next value of the sequence.
            boolean found = false;
            while ( ! found ) {
                test++;
                found = true;
                sumNewLength = savedsSumNewLength;
                //  Generate test sums
                for ( int j = 0 ; j <= chowlaLength ; j++ ) {
                    int testSum = (j == 0 ? test : chowla[j]) + test;
                    boolean duplicate = false;
 
                    //  Check if test Sum in array
                    for ( int k = 0 ; k < sumNewLength ; k++ ) {
                        if ( sumsNew[k] == testSum ) {
                            duplicate = true;
                            break;
                        }
                    }
                    if ( ! duplicate ) {
                        //  Add to array 
                        sumsNew[sumNewLength] = testSum;
                        sumNewLength++;
                    }
                    else {
                        //  Duplicate found.  Therefore, test candidate of the next value of the sequence is not OK.
                        found = false;
                        break;
                    }
                }
            }
 
            //  Bingo!  Now update bookkeeping.
            chowla[n] = test;
            chowlaLength++;            
            sums = sumsNew;
            if ( n >= minIndex ) {
                System.out.printf("%d %s", chowla[n], (n==maxIndex ? "\n" : ""));
            }
        }
    }
 
}
 