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

<lang perl>use strict; use warnings; use feature 'say';

sub generate_mc {

   my($max)  = @_;
   my $index = 0;
   my $test  = 1;
   my %sums  = (2 => 1);
   my @mc    = 1;
   while ($test++) {
       my %these = %sums;
       map { next if ++$these{$_ + $test} > 1 } @mc[0..$index], $test;
       %sums = %these;
       $index++;
       return @mc if (push @mc, $test) > $max-1;
   }

}

my @mian_chowla = generate_mc(100); say "First 30 terms in the Mian–Chowla sequence:\n", join(' ', @mian_chowla[ 0..29]),

   "\nTerms 91 through 100:\n",                     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

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

REXX

<lang rexx>/*REXX program computes and displays any range of the Mian─Chowla integer sequence. */ parse arg LO HI . /*obtain optional arguments from the CL*/ if LO== | LO=="," then LO= 1 /*Not specified? Then use the default.*/ if HI== | HI=="," then HI= 30 /* " " " " " " */ r.= 0 /*initialize the rekects stemmed array.*/ $=; if 1>=LO then $= 1 /*the Mian─Chowla sequence (so far)*/ @.=; @.1= 1 /*define start of the Mian─Chowla seq. */

1. = 1 /*count of numbers in sequence (so far)*/

    do t=2  until #>=HI;   !.= 0                /*process numbers until range is filled*/
      do i=1   for t;      if r.i  then iterate /*I  already rejected?  Then ignore it.*/
        do j=i for t-i+1;  if r.j  then iterate /*J     "        "        "     "    " */
        _= i + j                                /*get sum; [↑]  see if previously found*/
        if !._  then do; r.t=1; iterate t; end  /*reject  T  from the Mian─Chowla seq. */
        !._= 1                                  /*mark   _   as being one of the sums. */
        end   /*j*/
      end     /*i*/
    #= # + 1;              @.#= t               /*bump counter;  assign number to seq. */
    if #>=LO  &  #<=HI  then $= $ t             /*In the specified range?  Add to list.*/
    end       /*t*/

say 'The Mian─Chowla sequence for elements ' LO "──►" HI ' (inclusive):' say $</lang>

output   when using the default inputs:

The Mian─Chowla sequence for elements  1 ──► 30  (inclusive):
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

output   when using the input of:     91   100

The Mian─Chowla sequence for elements  91 ──► 100  (inclusive):
22526 23291 23564 23881 24596 24768 25631 26037 26255 27219