Mian-Chowla sequence: Difference between revisions

Content added Content deleted

Inline

Revision as of 18:44, 22 March 2019

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

AWK

<lang awk># 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 \ {

   FALSE      = 0;
   TRUE       = 1;

   mcCount    = 0;

   for( i = 1; mcCount < 100; i ++ )
   {
       # assume i will be part of the sequence
       isUnique  = TRUE;
       mcCount ++;
       mc[ mcCount ] = i;
       isMc[ i ]     = TRUE;
       # check the sums
       for( j = 1; j <= i && isUnique; j ++ )
       {
           if( j in isMc )
           {
               sumIJ = i + j;
               sumCount[ sumIJ ] += 1;
               isUnique = sumCount[ sumIJ ] < 2;
               if( ! isUnique )
               {
                   # the sum is not unique - remove it from the sequence
                   for( k = j; k > 0; k -- )
                   {
                       if( k in isMc )
                       {
                           sumCount[ i + k ] -= 1;
                       } # if k in isMc
                   } # for k
                   delete mc[ mcCount ];
                   delete isMc[ i ];
                   mcCount --;
               } # if isUnique
           } # if j in isMc
       } # for j
   } # for i
   # print the sequence
   printf( "Mian Chowla sequence elements 1..30:\n" );
   for( i = 1; i <= 30; i ++ )
   {
       printf( " %d", mc[ i ] );
   } # for i
   printf( "\n" );
   printf( "Mian Chowla sequence elements 91..100:\n" );
   for( i = 91; i <= 100; i ++ )
   {
       printf( " %d", mc[ i ] );
   } # for i
   printf( "\n" );

} # BEGIN</lang>

Output:

Mian Chowla sequence elements 1..30:
 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
Mian Chowla sequence elements 91..100:
 22526 23291 23564 23881 24596 24768 25631 26037 26255 27219

elapsed time approx 2.85 seconds.

Alternate

Translation of: Go

Hopefully the comments help explain the algorithm.

<lang awk># helper functions

determine if a list is empty or not

function isEmpty(a) { for (ii in a) return 0; return 1 }

list concatination

function concat(a, b) { for (cc in b) a[cc] = cc }

BEGIN \ {

   mc[0] = 1; sums[2] = 0;      # initialize lists
   for ( i = 1; i < 100; i ++ ) # iterate for each item in result
   {
       for ( j = mc[i-1]+1; ; j ++ ) # iterate thru trial values
       {
           mc[i] = j;           # set trial value into result
           for ( k = 0; k <= i; k ++ ) # test new iteration of sums
           {
               # test trial sum against old sums list
               if ((sum = mc[k] + j) in sums) 
               {                # collision, so
                   delete ts;   # toss out any accumulated items,
                   break;       #  and break out to the next j
               }
               ts[sum] = sum;   # (else) accumulate to new sum list
           } # for k
           if ( isEmpty( ts ) ) # nothing to add, 
               continue;        #  so try next j
           concat( sums, ts );  # combine new sums to old,
           delete ts;           #  clear out the new,
           break;               #  break out to next i
       } # for j
   } # for i
   # print the sequence
   ps = "Mian Chowla sequence elements %d..%d:\n";
   for ( i = 0; i < 100; i ++ )
   {
       if ( i == 0 )  printf ps, 1, 30;
       if ( i == 90 ) printf "\n\n" ps, 91, 100;
       if ( i < 30 || i >= 90 ) printf "%d ", mc[ i ];
   } # for i
   print "\n"

} # BEGIN</lang>

Output:

Mian Chowla sequence elements 1..30:
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 

Mian Chowla sequence elements 91..100:
22526 23291 23564 23881 24596 24768 25631 26037 26255 27219

Computation time is about 110 ms on tio.run

int * MianChowla() { static int mc[n]; mc[0] = 1; int sums[nn]; sums[0] = 2; int sum, le, ss = 1; for (int i = 1; i < n; i++) { le = ss; for (int j = mc[i - 1] + 1; ; j++) { mc[i] = j; for (int k = 0; k <= i; k++) { sum = mc[k] + j; if (Contains(sums, sum, ss)) { ss = le; goto nxtJ; } sums[ss++] = sum; } break; nxtJ:; } } return mc; }

int main() { clock_t st = clock(); int * mc; mc = MianChowla();

       double et = ((double)(clock() - st)) / CLOCKS_PER_SEC;

printf("The first 30 terms of the Mian-Chowla sequence are:\n"); for (int i = 0; i < 30; i++) printf("%d ", mc[i]); printf("\n\nTerms 91 to 100 of the Mian-Chowla sequence are:\n"); for (int i = 90; i < 100; i++) printf("%d ", mc[i]); printf("\n\nComputation time was %f seconds.", et); }</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.575556 seconds.

C#

Translation of: Go

<lang csharp>using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq;

static class Program {

   static int[] MianChowla(int n) {
       int[] mc = new int[n - 1 + 1];
       HashSet<int> sums = new HashSet<int>(), ts = new HashSet<int>();
       int sum; mc[0] = 1; sums.Add(2);
       for (int i = 1; i <= n - 1; i++) {
           for (int j = mc[i - 1] + 1; ; j++) {
               mc[i] = j;
               for (int k = 0; k <= i; k++) {
                   sum = mc[k] + j;
                   if (sums.Contains(sum)) { ts.Clear(); break; }
                   ts.Add(sum);
               }
               if (ts.Count > 0) { sums.UnionWith(ts); break; }
           }
       }
       return mc;
   }

   static void Main(string[] args)
   {
       const int n = 100; Stopwatch sw = new Stopwatch();
       string str = " of the Mian-Chowla sequence are:\n";
       sw.Start(); int[] mc = MianChowla(n); sw.Stop();
       Console.Write("The first 30 terms{1}{2}{0}{0}Terms 91 to 100{1}{3}{0}{0}" +
           "Computation time was {4}ms.{0}", '\n', str, string.Join(" ", mc.Take(30)),
           string.Join(" ", mc.Skip(n - 10)), sw.ElapsedMilliseconds);
   }

}</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 17ms.

C++

Translation of: Go

The sums array expands by "i" on each iteration from 1 to n, so the max array length can be pre-calculated to the nth triangular number (n * (n + 1) / 2). <lang cpp>using namespace std;

include <iostream>
include <ctime>

define n 100
define nn ((n * (n + 1)) >> 1)

bool Contains(int lst[], int item, int size) { for (int i = 0; i < size; i++) if (item == lst[i]) return true; return false; }

int * MianChowla() { static int mc[n]; mc[0] = 1; int sums[nn]; sums[0] = 2; int sum, le, ss = 1; for (int i = 1; i < n; i++) { le = ss; for (int j = mc[i - 1] + 1; ; j++) { mc[i] = j; for (int k = 0; k <= i; k++) { sum = mc[k] + j; if (Contains(sums, sum, ss)) { ss = le; goto nxtJ; } sums[ss++] = sum; } break; nxtJ:; } } return mc; }

int main() { clock_t st = clock(); int * mc; mc = MianChowla(); double et = ((double)(clock() - st)) / CLOCKS_PER_SEC; cout << "The first 30 terms of the Mian-Chowla sequence are:\n"; for (int i = 0; i < 30; i++) { cout << mc[i] << ' '; } cout << "\n\nTerms 91 to 100 of the Mian-Chowla sequence are:\n"; for (int i = 90; i < 100; i++) { cout << mc[i] << ' '; } cout << "\n\nComputation time was " << et << " seconds."; }</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.92958 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]

Quicker version (runs in less than 0.02 seconds on Celeron N3050 @1.6 GHz), output as before: <lang go>package main

import "fmt"

type set map[int]bool

func mianChowla(n int) []int {

   mc := make([]int, n)
   mc[0] = 1
   is := make(set, n*(n+1)/2)
   is[2] = true
   var sum int
   isx := make([]int, 0, n)
   for i := 1; i < n; i++ {
       isx = isx[:0]
   jloop:
       for j := mc[i-1] + 1; ; j++ {
           mc[i] = j
           for k := 0; k <= i; k++ {
               sum = mc[k] + j
               if is[sum] {                   
                   isx = isx[:0]
                   continue jloop
               }
               isx = append(isx, sum)
           }
           for _, x := range isx {
               is[x] = true
           }
           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>

JavaScript

Translation of: Python

(Second Python version)

<lang javascript>(() => {

   'use strict';

   const main = () => {

       const genMianChowla = mianChowlas();
       console.log([
           'Mian-Chowla terms 1-30:',
           take(30, genMianChowla),

           '\nMian-Chowla terms 91-100:',
           (() => {
               drop(60, genMianChowla);
               return take(10, genMianChowla);
           })()
       ].join('\n') + '\n');
   };

   // mianChowlas :: Gen [Int]
   function* mianChowlas() {
       let
           preds = [1],
           sumSet = new Set([2]),
           x = 1;
       while (true) {
           yield x;
           [sumSet, x] = mcSucc(sumSet, preds, x);
           preds = preds.concat(x);
       }
   }

   // mcSucc :: Set Int -> [Int] -> Int -> (Set Int, Int)
   const mcSucc = (setSums, preds, n) => {
       // Set of sums -> Series up to n -> Next term in series
       const
           q = until(
               x => all(
                   v => !setSums.has(v),
                   sumList(preds, x)
               ),
               succ,
               succ(n)
           );
       return [
           foldl(
               (a, x) => (a.add(x), a),
               setSums,
               sumList(preds, q)
           ),
           q
       ];
   };

   // sumList :: [Int] -> Int -> [Int]
   const sumList = (xs, n) =>
       // Series so far -> additional term -> addition sums
       [2 * n].concat(map(x => n + x, xs));

   // GENERIC FUNCTIONS ----------------------------

   // all :: (a -> Bool) -> [a] -> Bool
   const all = (p, xs) => xs.every(p);

   // drop :: Int -> [a] -> [a]
   // drop :: Int -> Generator [a] -> Generator [a]
   // drop :: Int -> String -> String
   const drop = (n, xs) =>
       Infinity > length(xs) ? (
           xs.slice(n)
       ) : (take(n, xs), xs);

   // foldl :: (a -> b -> a) -> a -> [b] -> a
   const foldl = (f, a, xs) => xs.reduce(f, a);

   // Returns Infinity over objects without finite length.
   // This enables zip and zipWith to choose the shorter
   // argument when one is non-finite, like cycle, repeat etc

   // length :: [a] -> Int
   const length = xs =>
       (Array.isArray(xs) || 'string' === typeof xs) ? (
           xs.length
       ) : Infinity;

   // map :: (a -> b) -> [a] -> [b]
   const map = (f, xs) =>
       (Array.isArray(xs) ? (
           xs
       ) : xs.split()).map(f);

   // succ :: Int -> Int
   const succ = x => 1 + x;

   // take :: Int -> [a] -> [a]
   // take :: Int -> String -> String
   const take = (n, xs) =>
       'GeneratorFunction' !== xs.constructor.constructor.name ? (
           xs.slice(0, n)
       ) : [].concat.apply([], Array.from({
           length: n
       }, () => {
           const x = xs.next();
           return x.done ? [] : [x.value];
       }));

   // until :: (a -> Bool) -> (a -> a) -> a -> a
   const until = (p, f, x) => {
       let v = x;
       while (!p(v)) v = f(v);
       return v;
   };

   // MAIN ---
   return main();

})();</lang>

Output:

Mian-Chowla terms 1-30:
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

Mian-Chowla terms 91-100:
22526,23291,23564,23881,24596,24768,25631,26037,26255,27219

[Finished in 0.393s]

(Executed in the Atom editor, using Run Script)

Julia

Optimization in Julia can be an incremental process. The first version of this program ran in over 2 seconds. Using a hash table for lookup of sums and avoiding reallocation of arrays helps considerably. <lang julia>function mianchowla(n)

   seq = ones(Int, n)
   sums = Dict{Int,Int}()
   tempsums = Dict{Int,Int}()
   for i in 2:n
       seq[i] = seq[i - 1] + 1
       incrementing = true
       while incrementing
           for j in 1:i
               tsum = seq[j] + seq[i]
               if haskey(sums, tsum)
                   seq[i] += 1
                   empty!(tempsums)
                   break
               else
                   tempsums[tsum] = 0
                   if j == i
                       merge!(sums, tempsums)
                       empty!(tempsums)
                       incrementing = false
                   end
               end
           end
       end
   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() @time 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].
  0.007524 seconds (168 allocations: 404.031 KiB)

Pascal

Works with: Free Pascal

keep sum of all sorted.Memorizing the compare positions speeds up. 10 min for n = 5818 1998652370. The cost of inserting 5818 values into sum_all array takes about 9 seconds. That is not relevant. <lang pascal>program MianChowla; const

 maxCnt = 100;

type

 tElem = Uint32;
 tpElem = ^tElem;
 t_n = array[0..maxCnt+1] of tElem;
 t_n_sum_all = array[0..(maxCnt+1)*(maxCnt+2) DIV 2] of tElem;

var

 n_sum_all : t_n_sum_all;
 n,
 n_LastPos : t_n; //memorize compare positions :-)

 maxIdx,
 maxN,
 max_SumIdx : NativeUInt;

procedure Init; var

 i : NativeInt;

begin

 maxIdx := 1;
 maxN   := 1;
 n[maxIdx] := maxN;
 max_SumIdx := 1;
 n_sum_all[max_SumIdx] := 2*maxN;
 For i := 1 to maxCnt do
   n_LastPos[i] := 1;

end;

procedure InsertNew_sum(NewValue:NativeUint); var

 pElem :tpElem;
 oldIdx,newIdx,nextValue : nativeInt;

Begin

 write(#13,MaxIdx:10,NewValue:10);
 newIdx := maxIdx;
 oldIdx := max_SumIdx;
 //append new value
 inc(maxIdx);
 n[maxIdx] := NewValue;
 //extend sum_
 inc(max_SumIdx,maxIdx);

 //heighest value already known
 n_sum_all[max_SumIdx] := 2*NewValue;

 pElem := @n_sum_all[max_SumIdx-1];
 nextValue := NewValue+n[newIdx];
 repeat
   while n_sum_all[oldIdx] > nextValue do
   Begin
     pElem^ := n_sum_all[oldIdx];
     dec(oldIdx);
     dec(pElem);
   end;
   pElem^ := nextValue;
   dec(pElem);
   dec(newIdx);
   IF newIdx = 0 then
     BREAK;
   nextValue := NewValue+n[newIdx];
 until newIdx < 0;

end;

procedure FindNew; var

 i,LastCheckPos,Ofs,newVal : NativeUint;
 TestRes : boolean;

begin

 ofs := n[maxIdx]+1;
 For i := 1 to maxIdx+1 do
   n_LastPos[i] := 1;
 repeat
   LastCheckPos := 1;
   i := 1;
   For i := 1 to maxIdx do
   Begin
     newVal := ofs+n[i];
     IF LastCheckPos < n_LastPos[i] then
       LastCheckPos := n_LastPos[i];
     while n_sum_all[LastCheckPos] < newVal do
     Begin
       inc(LastCheckPos);
       if LastCheckPos >= max_SumIdx then
         BREAK;
     end;
     TestRes:= n_sum_all[LastCheckPos] = newVal;
     IF TestRes then
       BREAK;
     //memorize LastCheckPos;
     n_LastPos[i] := LastCheckPos-1;
   end;
   //found?
   If not(TestRes) then
     BREAK;
   inc(ofs);
 until false;
 InsertNew_sum(ofs);

end;

var

 i : NativeInt;

BEGIN

 Init;
 For i := 1 to maxCnt do
   FindNew;
 writeln(#13,'The first 30 terms of the Mian-Chowla sequence are');
 For i := 1 to 30 do
   write(n[i],' ');
 writeln;
 writeln;
 writeln('The terms 90 - 100 of the Mian-Chowla sequence are');
 For i := 90 to 100 do
   write(n[i],' ');
 writeln;

END. {https://oeis.org/A005282/b005282.txt

5816 1998326307 5817 1998387406 5818 1998652370

... 5818 1998652370

real 9m55,050s </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 terms 90 - 100 of the Mian-Chowla sequence are
21948 22526 23291 23564 23881 24596 24768 25631 26037 26255 27219 

real	0m0,002s

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;
   ((|@mian-chowla[^$index], $test) »+» $test).map: { ++$next and last if %sums{$_}:exists; ++%these{$_} };
   next if $next;
   %sums.push: %these;
   ++$index;
   $test

};

put "First 30 terms in the Mian–Chowla sequence:\n", @mian-chowla[^30]; put "\nTerms 91 through 100:\n", @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

Python

Procedural

<lang python>from itertools import count, islice, chain import time

def mian_chowla():

   mc = [1]
   yield mc[-1]
   psums = set([2])
   newsums = set([])
   for trial in count(2):
       for n in chain(mc, [trial]):
           sum = n + trial
           if sum in psums:
               newsums.clear()
               break
           newsums.add(sum)
       else:
           psums |= newsums
           newsums.clear()
           mc.append(trial)
           yield trial

def pretty(p, t, s, f):

   print(p, t, " ".join(str(n) for n in (islice(mian_chowla(), s, f))))

if __name__ == '__main__':

   st = time.time()
   ts = "of the Mian-Chowla sequence are:\n"
   pretty("The first 30 terms", ts, 0, 30)
   pretty("\nTerms 91 to 100", ts, 90, 100)
   print("\nComputation time was", (time.time()-st) * 1000, "ms")</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 53.58004570007324 ms

Composition of pure functions

<lang python>"""Mian-Chowla series"""

from itertools import (islice)

mianChowlas :: Int -> Gen [Int]

def mianChowlas():

   Mian-Chowla series - Generator constructor
   preds = [1]
   sumSet = set([2])
   x = 1
   while True:
       yield x
       (sumSet, x) = mcSucc(sumSet)(preds)(x)
       preds = preds + [x]

mcSucc :: Set Int -> [Int] -> Int -> (Set Int, Int)

def mcSucc(setSums):

   Set of sums -> series up to N -> N -> (updated set, next term)
   def go(xs, n):
       # p :: (Int, [Int]) -> Bool
       def p(tpl):
           Predicate: only new sums created ?
           return all(d not in setSums for d in snd(tpl))

       # nxt :: (Int, [Int]) -> (Int, [Int])
       def nxt(tpl):
           Next integer, and the additional sums it would introduce.
           d = 1 + fst(tpl)
           return (d, [d + x for x in xs] + [2 * d])

       q, ds = until(p)(nxt)(nxt((n, [])))
       setSums.update(ds)
       return (setSums, q)
   return lambda preds: lambda n: go(preds, n)

TEST ----------------------------------------------------
main :: IO ()

def main():

   Tests

   genMianChowlas = mianChowlas()
   print(
       'First 30 terms of the Mian-Chowla series:\n',
       take(30)(genMianChowlas)
   )
   drop(60)(genMianChowlas)
   print(
       '\n\nTerms 91 to 100 of the Mian-Chowla series:\n',
       take(10)(genMianChowlas),
       '\n'
   )

GENERIC -------------------------------------------------

drop :: Int -> [a] -> [a]
drop :: Int -> String -> String

def drop(n):

   The suffix of xs after the
      first n elements, or [] if n > length xs
   def go(xs):
       if isinstance(xs, list):
           return xs[n:]
       else:
           take(n)(xs)
           return xs
   return lambda xs: go(xs)

fst :: (a, b) -> a

def fst(tpl):

   First component of a tuple.
   return tpl[0]

snd :: (a, b) -> b

def snd(tpl):

   Second component of a tuple.
   return tpl[1]

take :: Int -> [a] -> [a]
take :: Int -> String -> String

def take(n):

   The prefix of xs of length n,
      or xs itself if n > length xs.
   return lambda xs: (
       xs[0:n]
       if isinstance(xs, list)
       else list(islice(xs, n))
   )

until :: (a -> Bool) -> (a -> a) -> a -> a

def until(p):

   The result of applying f until p holds.
      The initial seed value is x.
   def go(f, x):
       v = x
       while not p(v):
           v = f(v)
       return v
   return lambda f: lambda x: go(f, x)

if __name__ == '__main__':

   main()</lang>

Output:

First 30 terms of the Mian-Chowla series:
 [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 series:
 [22526, 23291, 23564, 23881, 24596, 24768, 25631, 26037, 26255, 27219]

REXX

Programming note: the do loop (line ten):

      do j=i  for t-i+1;  ···

can be coded as:

      do j=i  to t;       ···

but the 1^st version is faster. <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 rejects stemmed array.*/

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

$= /*the Mian─Chowla sequence (so far). */

  do t=1  until #=HI;      !.= r.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                                  /*calculate the sum of   I   and   J.  */
      if !._  then do;  r.t= 1; iterate t;  end /*reject  T  from the Mian─Chowla seq. */
      !._= 1                                    /*mark _ as one of the sums in sequence*/
      end   /*j*/
    end     /*i*/
  #= # + 1                                      /*bump the counter of terms in the list*/
  if #>=LO  &  #<=HI  then $= $ t               /*In the specified range?  Add to list.*/
  end       /*t*/

say 'The Mian─Chowla sequence for terms ' LO "──►" HI ' (inclusive):' say strip($) /*ignore the leading superfluous blank.*/</lang>

output when using the default inputs:

The Mian─Chowla sequence for terms  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 terms 91 ──► 100  (inclusive):
22526 23291 23564 23881 24596 24768 25631 26037 26255 27219

Ruby

Translation of: Go

<lang ruby>require 'set' n, ts, mc, sums = 100, [], [1], Set.new sums << 2 st = Time.now for i in (1 .. (n-1))

  for j in mc[i-1]+1 .. Float::INFINITY
     mc[i] = j
     for k in (0 .. i)
        if (sums.include?(sum = mc[k]+j))
           ts.clear
           break 
        end
        ts << sum
     end
     if (ts.length > 0)
        sums = sums | ts
        break
     end
  end

end et = (Time.now - st) * 1000 s = " of the Mian-Chowla sequence are:\n" puts "The first 30 terms#{s}#{mc.slice(0..29).join(' ')}\n\n" puts "Terms 91 to 100#{s}#{mc.slice(90..99).join(' ')}\n\n" puts "Computation time was #{et.round(1)}ms."</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 63.0ms.

Sidef

Translation of: Go

<lang ruby>var (n, sums, ts, mc) = (100, Set([2]), [], [1]) var st = Time.micro_sec for i in (1 ..^ n) {

  for j in (mc[i-1]+1 .. Inf) {
     mc[i] = j
     for k in (0 .. i) {
        var sum = mc[k]+j
        if (sums.exists(sum)) { 
           ts.clear
           break
        }
        ts << sum
     }
     if (ts.len > 0) {
        sums = (sums|Set(ts...))
        break
     }
  }

} var et = (Time.micro_sec - st) var s = " of the Mian-Chowla sequence are:\n" say "The first 30 terms#{s}#{mc.ft(0, 29).join(' ')}\n" say "Terms 91 to 100#{s}#{mc.ft(90, 99).join(' ')}\n" say "Computation time was #{et} seconds."</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 3.9831 seconds.

VBScript

<lang vb>' Mian-Chowla sequence - VBScript - 15/03/2019

   Const m = 100, mm=28000
   ReDim r(mm), v(mm * 2)
   Dim n, t, i, j, l, s1, s2, iterate_t
   ReDim seq(m)
   t0=Timer
   s1 = "1": s2 = ""
   seq(1) = 1: n = 1: t = 1
   Do While n < m
       t = t + 1
       iterate_t = False
       For i = 1 to t * 2
           v(i) = 0
       Next
       i = 1
       Do While i <= t And Not iterate_t
           If r(i) = 0 Then
               j = i
               Do While j <= t And Not iterate_t
                   If r(j) = 0 Then
                       l = i + j
                       If v(l) = 1 Then
                           r(t) = 1
                           iterate_t = True
                       End If
                       If Not iterate_t Then v(l) = 1
                   End If
                   j = j + 1
               Loop
           End If
           i = i + 1
       Loop
       If Not iterate_t Then
           n = n + 1
           seq(n) = t
           if           n<= 30 then s1 = s1 & " " & t
           if n>=91 and n<=100 then s2 = s2 & " " & t
       End If
   Loop
   wscript.echo "t="& t
   wscript.echo "The Mian-Chowla sequence for elements 1 to 30:"
   wscript.echo s1
   wscript.echo "The Mian-Chowla sequence for elements 91 to 100:"
   wscript.echo s2
   wscript.echo "Computation time: "&  Int(Timer-t0) &" sec"</lang>

Output:

The Mian-Chowla sequence for elements 1 to 30:
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 Mian-Chowla sequence for elements 91 to 100:
 22526 23291 23564 23881 24596 24768 25631 26037 26255 27219
Computation time: 2381 sec

Execution time: 40 min

Shorter execution time

Translation of: Go

<lang vb>' Mian-Chowla sequence - VBScript - March 19th, 2019

   Function Find(x(), val) ' finds val on a pre-sorted list
       Dim l, u, h : l = 0 : u = ubound(x) : Do : h = (l + u) \ 2
           If val = x(h) Then Find = h : Exit Function
           If val > x(h) Then l = h + 1 Else u = h - 1
       Loop Until l > u : Find = -1
   End Function

   ' adds next item from a() to result (r()), adds all remaining items
   ' from b(), once a() is exhausted
   Sub Shuffle(ByRef r(), a(), b(), ByRef i, ByRef ai, ByRef bi, al, bl)
       r(i) = a(ai) : ai = ai + 1 : If ai > al Then Do : i = i + 1 : _
           r(i) = b(bi) : bi = bi + 1 : Loop until bi = bl
   End Sub

   Function Merger(a(), b(), bl) ' merges two pre-sorted lists
       Dim res(), ai, bi, i : ReDim res(ubound(a) + bl) : ai = 0 : bi = 0
       For i = 0 To ubound(res)
           If a(ai) < b(bi) Then Shuffle res, a, b, i, ai, bi, ubound(a), bl _
           Else Shuffle res, b, a, i, bi, ai, bl, ubound(a)
       Next : Merger = res
   End Function

   Const n = 100 : Dim mc(), sums(), ts(), sp, tc : sp = 1 : tc = 0
   ReDim mc(n - 1), sums(0), ts(n - 1) : mc(0) = 1 : sums(sp - 1) = 2
   Dim sum, i, j, k, st : st = Timer
   wscript.echo "The Mian-Chowla sequence for elements 1 to 30:"
   wscript.stdout.write("1 ")
   For i = 1 To n - 1 : j = mc(i - 1) + 1 : Do    
           mc(i) = j : For k = 0 To i
               sum = mc(k) + j : If Find(sums, sum) >= 0 Then _
                   tc = 0 : Exit For Else ts(tc) = sum : tc = tc + 1
           Next : If tc > 0 Then
             nu = Merger(sums, ts, tc) : ReDim sums(ubound(nu)) 
             For e = 0 To ubound(nu) : sums(e) = nu(e) : Next
             tc = 0 : Exit Do 
           End If : j = j + 1 : Loop
       if i = 90 then wscript.echo vblf & vbLf & _
           "The Mian-Chowla sequence for elements 91 to 100:"
       If i < 30 or i >= 90 Then wscript.stdout.write(mc(i) & " ")
   Next
   wscript.echo vblf & vbLf & "Computation time: "& Timer - st &" seconds."</lang>

Output:

Hint: save the code to a .vbs file (such as "mc.vbs") and start it with this command Line: "cscript.exe /nologo mc.vbs". This will send the output to the console instead of a series of message boxes.
This goes faster because the cache of sums is maintained throughout the computation instead of being reinitialized at each iteration. Also the sums() array is kept sorted to find any previous values quicker.

The Mian-Chowla sequence for elements 1 to 30:
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 Mian-Chowla sequence for elements 91 to 100:
22526 23291 23564 23881 24596 24768 25631 26037 26255 27219

Computation time: 1.328125 seconds.

Visual Basic .NET

Translation of: Go

<lang vbnet>Module Module1 Function MianChowla(ByVal n As Integer) As Integer()

       Dim mc(n - 1) As Integer, sums, ts As New HashSet(Of Integer),
       sum As Integer : mc(0) = 1 : sums.Add(2)
       For i As Integer = 1 To n - 1
           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 ts.Clear() : Exit For
                   ts.Add(sum)
               Next
               If ts.Count > 0 Then sums.UnionWith(ts) : Exit For
           Next
       Next
       Return mc
   End Function

   Sub Main(ByVal args As String())
       Const n As Integer = 100
       Dim sw As New Stopwatch(), str As String = " of the Mian-Chowla sequence are:" & vbLf
       sw.Start() : Dim mc As Integer() = MianChowla(n) : sw.Stop()
       Console.Write("The first 30 terms{1}{2}{0}{0}Terms 91 to 100{1}{3}{0}{0}" &
           "Computation time was {4}ms.{0}", vbLf, str,
           String.Join(" ", mc.Take(30)), String.Join(" ", mc.Skip(n - 10)), sw.ElapsedMilliseconds)
   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 18ms.