Mian-Chowla sequence

Mian-Chowla sequence is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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

The sequence starts with:

a₁ = 1

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

a_i + a_j

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:

a₁ = 1

1 + 1 = 2

Speculatively try a₂ = 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 a₃ = 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 a₃ = 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

Go

<lang go>package main

import "fmt"

func contains(is []int, s int) bool {

   for _, i := range is {
       if s == i {
           return true
       }
   }
   return false

}

func mianChowla(n int) []int {

   mc := make([]int, n)
   mc[0] = 1
   is := []int{2}
   var sum int
   for i := 1; i < n; i++ {
       le := len(is)
   jloop:
       for j := mc[i-1] + 1; ; j++ {
           mc[i] = j
           for k := 0; k <= i; k++ {
               sum = mc[k] + j
               if contains(is, sum) {
                   is = is[0:le]
                   continue jloop
               }
               is = append(is, sum)
           }
           break
       }
   }
   return mc

}

func main() {

   mc := mianChowla(100)
   fmt.Println("The first 30 terms of the Mian-Chowla sequence are:")
   fmt.Println(mc[0:30])
   fmt.Println("\nTerms 91 to 100 of the Mian-Chowla sequence are:")
   fmt.Println(mc[90:100])

}</lang>

Output:

The first 30 terms of the Mian-Chowla sequence are:
[1 2 4 8 13 21 31 45 66 81 97 123 148 182 204 252 290 361 401 475 565 593 662 775 822 916 970 1016 1159 1312]

Terms 91 to 100 of the Mian-Chowla sequence are:
[22526 23291 23564 23881 24596 24768 25631 26037 26255 27219]

Perl 6

<lang perl6>my @mian-chowla = 1, |(2..Inf).map: -> $test {

   state $index = 1;
   state %sums = 2 => 1;
   my $next;
   my %these = %sums;
   (|@mian-chowla[^$index], $test).map: { ++$next and last if ++%these{$_ + $test} > 1 };
   next if $next;
   %sums = %these;
   ++$index;
   $test

};

put 'First 30 terms in the Mian–Chowla sequence:'; put join ', ', @mian-chowla[^30];

put "\nTerms 91 through 100:"; put join ', ', @mian-chowla[90..99];</lang>

Output:

First 30 terms in the Mian–Chowla sequence:
1, 2, 4, 8, 13, 21, 31, 45, 66, 81, 97, 123, 148, 182, 204, 252, 290, 361, 401, 475, 565, 593, 662, 775, 822, 916, 970, 1016, 1159, 1312

Terms 91 through 100:
22526, 23291, 23564, 23881, 24596, 24768, 25631, 26037, 26255, 27219