Mian-Chowla sequence

From Rosetta Code
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:

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


ALGOL 68

Works with: ALGOL 68G version Any - tested with release 2.8.3.win32

Based on the AWK sample.

<lang algol68># 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 

   INT max mc           = 100;
   INT mc count        := 0;
   [ max mc ]INT mc;
   INT curr size       := 10 000;    # initial sizes of the arrays #
   INT size increment   = curr size; # size to increase the arrays by #
   REF[]INT  sum count := HEAP[ curr size ]INT;
   REF[]BOOL is mc     := HEAP[ curr size ]BOOL;
   FOR i TO curr size DO sum count[ i ] := 0; is mc[ i ] := FALSE OD;
   FOR i WHILE mc count < max mc DO
       # assume i will be part of the sequence #
       BOOL is unique  := TRUE;
       mc count       +:= 1;
       mc[ mc count ]  := i;
       is mc[ i ]      := TRUE;
       # check the sums #
       FOR j TO i WHILE is unique DO
           IF is mc[ j ] THEN
               # have a sequence element #
               INT sumij            = i + j;
               IF sumij > curr size THEN
                   # the sum count and is mc arrays are too small - make them larger #
                   REF[]BOOL new is mc = HEAP[ curr size + size increment ]BOOL;
                   REF[]INT  new count = HEAP[ curr size + size increment ]INT;
                   FOR i TO curr size DO
                       new is mc[ i ] := is mc    [ i ];
                       new count[ i ] := sum count[ i ]
                   OD;
                   FOR i TO size increment DO
                       new is mc[ curr size + i ] := FALSE;
                       new count[ curr size + i ] := 0
                   OD;
                   curr size +:= size increment;
                   is mc      := new is mc;
                   sum count  := new count
               FI;
               sum count[ sumij ] +:= 1;
               is unique           := sum count[ sumij ] < 2;
               IF NOT is unique THEN
                   # the sum is not unique - remove it from the sequence #
                   FOR k TO j DO IF is mc[ k ] THEN sum count[ i + k ] -:= 1 FI OD;
                   mc[ mc count ] := 0;
                   is mc[ i ] := FALSE;
                   mc count -:= 1
               FI
           FI
       OD
   OD;

   # print parts of the sequence #
   print( ( "Mian Chowla sequence elements 1..30:", newline ) );
   FOR i TO 30 DO print( ( " ", whole( mc[ i ], 0 ) ) ) OD;
   print( ( newline ) );
   print( ( "Mian Chowla sequence elements 91..100:", newline ) );
   FOR i FROM 91 TO 100 DO print( ( " ", whole( mc[ i ], 0 ) ) ) OD

END</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.75 seconds.

AWK

<lang awk># Find Mian-Chowla numbers: an

  1. where: ai = 1,
  2. and: an = smallest integer such that ai + aj is unique
  3. 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.

C

Translation of: Go

<lang C>#include <stdio.h>

  1. include <stdbool.h>
  2. include <time.h>
  1. define n 100
  2. define nn ((n * (n + 1)) >> 1)

bool Contains(int lst[], int item, int size) { for (int i = size - 1; i >= 0; 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;

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.Linq; using System.Collections.Generic;

static class Program { 

   static int[] MianChowla(int n) {
       int[] mc = new int[n];
       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++) {
           ts.Clear(); 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)) {
                       sums.ExceptWith(ts); goto nxtJ;
                   }
                   sums.Add(sum); ts.Add(sum);
               }
               break;
           nxtJ: ;
           }
       }
       return mc;
   }

   static void Main(string[] args)
   {
       string str = " terms of the Mian-Chowla sequence are:\n";
       DateTime st = DateTime.Now; int[] mc = MianChowla(100); 
       double et = (DateTime.Now - st).TotalSeconds;
       Console.Write("The first 30{1}{2}{0}{0}Terms 91 to 100{1}{3}{0}{0}" +
           "Computation time was {4} seconds.", '\n', str,
           string.Join(" ", mc.Take(30)), string.Join(" ", mc.Skip(90)), 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 terms of the Mian-Chowla sequence are:
22526 23291 23564 23881 24596 24768 25631 26037 26255 27219

Computation time was 0.4796447 seconds.

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;

  1. include <iostream>
  2. include <ctime>
  1. define n 100
  2. 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.06 seconds), 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)
   is[2] = true
   var sum int
   var isx []int
   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] { 
                   for _, x := range isx {
                       delete(is, x)
                   }
                   isx = isx[:0] 
                   continue jloop
               }               
               is[sum] = true
               isx = append(isx, 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>

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

<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) || haskey(tempsums, 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

mianchowla(5)

@time begin 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

</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.132969 seconds (297.83 k allocations: 14.958 MiB, 3.18% gc time)

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

Python

Procedural

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

def mian_chowla(): 

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

if __name__ == '__main__': 

   print(list(islice(mian_chowla(), 30)))
   print(list(islice(mian_chowla(), 90, 100)))</lang>
Output:
[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]
[22526, 23291, 23564, 23881, 24596, 24768, 25631, 26037, 26255, 27219]

Composition of pure functions

This turns out to execute a little faster than the procedural version above.

(About 8X faster by a simple time.time() start and end measure)

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

from itertools import (islice)


  1. 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]


  1. 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(qds):
           Predicate: only new sums created ?
           ds = qds[1]
           return all(d not in setSums for d in ds)

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

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


  1. TEST ----------------------------------------------------
  2. 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'
   )
  1. GENERIC -------------------------------------------------


  1. drop :: Int -> [a] -> [a]
  2. 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)


  1. take :: Int -> [a] -> [a]
  2. 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))
   )


  1. 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] 

[Finished in 0.206s]

(Executed in Atom editor, using Run Script)

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 1st 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.*/

  1. = 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

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 - 17/03/2019 

   Const n = 100 : ReDim mc(n), sums((n * (n + 1)) / 2)
   mc(0) = 1 : sums(0) = 2
   Dim sum, le, ss, i, j, k, l, f, st : ss = 1 : st = Timer
   wscript.echo "The Mian-Chowla sequence for elements 1 to 30:"
   wscript.stdout.write("1 ")
   For i = 1 To n - 1
       le = ss : For j = mc(i - 1) + 1 To 1000000
           mc(i) = j : For k = 0 To i
               sum = mc(k) + j
               f = -1 : For l = ss - 1 To 0 Step -1
                   If sums(l) = sum Then f = l : Exit For
               Next : If f >= 0 Then ss = le : Exit For
               sums(ss) = sum : ss = ss + 1
           Next : If ss <> le Then Exit For
       Next
       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. 

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: 62.9375 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 : ts.Clear()
           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 sums.ExceptWith(ts) : GoTo nxtJ
                   sums.Add(sum) : ts.Add(sum)
               Next : Exit For 
         nxtJ: Next : Next : Return mc
   End Function

   Sub Main(ByVal args As String())
       Dim str As String = " terms of the Mian-Chowla sequence are:" & vbLf,
           st As DateTime = DateTime.Now, mc As Integer() = MianChowla(100),
           et As Double = (DateTime.Now - st).TotalSeconds
       Console.Write("The first 30{1}{2}{0}{0}Terms 91 to 100{1}{3}{0}{0}" & _
           "Computation time was {4} seconds.", vbLf, str,
           String.Join(" ", mc.Take(30)), String.Join(" ", mc.Skip(90)), et)
   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 terms of the Mian-Chowla sequence are:
22526 23291 23564 23881 24596 24768 25631 26037 26255 27219

Computation time was 0.4687451 seconds.
Retrieved from "https://rosettacode.org/wiki/Mian-Chowla_sequence?oldid=288722"