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

C#

Translation of: Go

<lang csharp>using System; using System.Linq;

static class Program {

   static int[] MianChowla(int n) {
       int[] mc = new int[n]; int[] sums = new int[] { 2 };
       int sum, le; mc[0] = 1; for (int i = 1; i <= n - 1; i++) {
           le = sums.Length; for (int j = mc[i - 1] + 1; ; j++) {
               mc[i] = j; for (int k = 0; k <= i; k++) {
                   if (sums.Contains(sum = mc[k] + j)) {
                       Array.Resize(ref sums, le); goto nxtJ;
                   }
                   Array.Resize(ref sums, sums.Length + 1);
                   sums[sums.Length - 1] = sum;
               }
               break;
           nxtJ: ;
           }
       }
       return mc;
   }

   static void Main(string[] args)
   {
       DateTime st = DateTime.Now; int[] mc = MianChowla(100);
       Console.WriteLine("The first 30 terms of the Mian-Chowla sequence are:\n{0}",
           string.Join(" ", mc.Take(30)));
       Console.WriteLine("\nTerms 91 to 100 of the Mian-Chowla sequence are:\n{0}",
           string.Join(" ", mc.Skip(90)));
       Console.Write("\nComputation time was {0} seconds.", (DateTime.Now - st).TotalSeconds);
   }

}</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

Computation time was 1.1993837 seconds.

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]

Julia

<lang julia>function mianchowla(n)

   seq = ones(Int, n)
   tempsums = Vector{Int}()
   for i in 2:n
       seq[i] = seq[i - 1] + 1
       while true 
           for j in 1:i, k in j:i
               tsum = seq[j] + seq[k]
               if tsum in tempsums
                   seq[i] += 1
                   empty!(tempsums)
                   break
               else
                   if j == i && k == i
                       empty!(tempsums)
                       @goto nextseq
                   end
                   push!(tempsums, tsum)
               end
           end
       end
       @label nextseq
   end
   seq

end

function testmianchowla()

   println("The first 30 terms of the Mian-Chowla sequence are $(mianchowla(30)).")
   println("The 91st through 100th terms of the Mian-Chowla sequence are $(mianchowla(100)[91:100]).")

end

testmianchowla()

</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].
The 91st through 100th terms 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

Visual Basic .NET

Translation of: Go

<lang vbnet>Module Module1

   Function MianChowla(ByVal n As Integer) As Integer()
       Dim mc As Integer() = New Integer(n - 1) {}, sums As Integer() = New Integer() {2}
       Dim sum, le As Integer : mc(0) = 1 : For i As Integer = 1 To n - 1 : le = sums.Length
           For j As Integer = mc(i - 1) + 1 To Integer.MaxValue
               mc(i) = j : For k As Integer = 0 To i
                   sum = mc(k) + j : If sums.Contains(sum) Then Array.Resize(sums, le) : GoTo nxtJ
                   Array.Resize(sums, sums.Length + 1) : sums(sums.Length - 1) = sum
               Next : Exit For 
         nxtJ: Next : Next : Return mc
   End Function

   Sub Main(ByVal args As String())
       Dim st As DateTime = DateTime.Now, mc As Integer() = MianChowla(100)
       Console.WriteLine("The first 30 terms of the Mian-Chowla sequence are:" & _
           vbLf & "{0}", String.Join(" ", mc.Take(30)))
       Console.WriteLine(vbLf & "Terms 91 to 100 of the Mian-Chowla sequence are:" & _
           vbLf & "{0}", String.Join(" ", mc.Skip(90)))
       Console.Write(vbLf & "Computation time was {0} seconds.", (DateTime.Now - st).TotalSeconds)
   End Sub

End Module</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

Computation time was 1.1661764 seconds.