Mian-Chowla sequence

Mian-Chowla sequence
You are encouraged to solve this task according to the task description, using any language you may know.

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

ALGOL 68

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

Allocating a large-enough array initially would gain some performance but might be considered cheating - 60 000 elements would be enough for the task.

<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;
   [ max mc ]INT mc;
   INT curr size       :=      0; # initial size of the array     #
   INT size increment   = 10 000; # size to increase the array by #
   REF[]BOOL is sum    := HEAP[ 1 : 0 ]BOOL;
   INT mc count        := 1;
   FOR i WHILE mc count <= max mc DO
       # assume i will be part of the sequence                    #
       mc[ mc count ]  := i;
       # check the sums                                           #
       IF  ( 2 * i ) > curr size THEN
           # the is sum array is too small - make a larger one    #
           REF[]BOOL new sum = HEAP[ curr size + size increment ]BOOL;
           new sum[ 1 : curr size ] := is sum;
           FOR n TO size increment DO new sum[ curr size + n ] := FALSE OD;
           curr size  +:= size increment;
           is sum      := new sum
       FI;
       BOOL is unique  := TRUE;
       FOR mc pos TO mc count WHILE is unique := NOT is sum[ i + mc[ mc pos ] ] DO SKIP OD;
       IF is unique THEN
           # i is a sequence element - store the sums             #
           FOR k TO mc count DO is sum[ i + mc[ k ] ] := TRUE OD;
           mc count +:= 1
       FI
   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 0.25 seconds on my Windows 7 system (note under Windows, A68G runs as an interpreter only).

AWK

Translation of the ALGOL 68 - largely implements the "by hand" method in the task. <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    = 1;

   for( i = 1; mcCount <= 100; i ++ )
   {
       # assume i will be part of the sequence
       mc[ mcCount ] = i;
       # check the sums
       isUnique = TRUE;
       for( mcPos = 1; mcPos <= mcCount && isUnique; mcPos ++ )
       {
           isUnique = ! ( ( i + mc[ mcPos ] ) in isSum );
       } # for j
       if( isUnique )
       {
           # i is a sequence element - store the sums
           for( k = 1; k <= mcCount; k ++ )
           {
               isSum[ i + mc[ k ] ] = TRUE;
           } # for k
           mcCount ++;
       } # if isUnique
   } # 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 0.20 seconds on my Windows 7 system.

Alternate

Translation of: Go

Hopefully the comments help explain the algorithm.

<lang awk># helper functions

2. determine if a list is empty or not

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

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

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.

Quick, but...

...is memory hungry. This will allocate a bigger buffer as needed to keep track of the sums involved. Based on the ALGOL 68 version. The minimum memory needed is double of the highest entry calculated. This program doubles the buffer size each time needed, so it will use more than the minimum. The ALGOL 68 increments by a fixed increment size. Which could be just as wasteful if the increment is too large and slower if the increment is too small). <lang C>#include <stdio.h>

1. include <stdlib.h>
2. include <stdbool.h>
3. include <time.h>

// helper function for indicating memory used. void approx(char* buf, double count) {

   const char* suffixes[] = { "Bytes", "KiB", "MiB" };
   uint s = 0; 
   while (count >= 1024 && s < 3) { s++; count /= 1024; }
   if (count - (double)((int)count) == 0.0)
       sprintf(buf, "%d %s", (int)count, suffixes[s]);
   else
       sprintf(buf, "%.1f %s", count, suffixes[s]);

}

int main() {

   int i, j, k, c = 0, n = 100, nn = 110;
   int* mc = (int*) malloc((n) * sizeof(int));
   bool* isSum = (bool*) calloc(nn, sizeof(bool));
   char em[] = "unable to increase isSum array to %ld.";
   if (n > 100)  printf("Computing terms 1 to %d...\n", n);
   clock_t st = clock();
   for (i = 1; c < n; i++) {
       mc[c] = i;
       if (i + i > nn) {
           bool* newIs = (bool*)realloc(isSum, (nn <<= 1) * sizeof(bool));
           if (newIs == NULL) { printf(em, nn); return -1; }
           isSum = newIs;
           for (j = (nn >> 1); j < nn; j++) isSum[j] = false;
       }
       bool isUnique = true;
       for (j = 0; (j < c) && isUnique; j++) isUnique = !isSum[i + mc[j]];
       if (isUnique) {
           for (k = 1; k <= c; k++) isSum[i + mc[k]] = true;
           c++;
       }
   }
   double et = 1e3 * ((double)(clock() - st)) / CLOCKS_PER_SEC;
   free(isSum);
   printf("The first 30 terms of the Mian-Chowla sequence are:\n");
   for (i = 0; i < 30; i++) printf("%d ", mc[i]);
   printf("\n\nTerms 91 to 100 of the Mian-Chowla sequence are:\n");
   for (i = 90; i < 100; i++) printf("%d ", mc[i]);
   if (c > 100) printf("\nTerm %d is: %d" ,c , mc[c - 1]);
   free(mc);
   char buf[100]; approx(buf, nn * sizeof(bool));
   printf("\n\nComputation time was %6.3f ms.  Allocation was %s.", et, buf);

}</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.773 ms.  Allocation was 55 KiB.

Here is the output for a larger calculation:

Computing terms 1 to 1300...
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 
Term 1300 is: 29079927

Computation time was 7979.042 ms.  Allocation was 110 MiB.

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;

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.

F#

The function

<lang fsharp> // Generate Mian-Chowla sequence. Nigel Galloway: March 23rd., 2019 let mC=let rec fN i g l=seq{

        let a=(l*2)::[for i in i do yield i+l]@g
        let b=[l+1..l*2]|>Seq.find(fun e->Seq.forall(fun g->(Seq.contains (g-e)>>not) i) a)
        yield b; yield! fN (l::i) (a|>List.filter(fun n->n>b)) b}
      seq{yield 1; yield! fN [] [] 1}

</lang>

The Tasks

First 30

<lang fsharp> mC |> Seq.take 30 |> Seq.iter(printf "%d ");printfn "" </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

91 to 100

<lang fsharp> mC |> Seq.skip 90 |> Seq.take 10 |> Seq.iter(printf "%d ");printfn "" </lang>

Output:

22526 23291 23564 23881 24596 24768 25631 26037 26255 27219

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)

Kotlin

Translation of: Go

<lang scala>// Version 1.3.21

fun mianChowla(n: Int): List<Int> {

   val mc = MutableList(n) { 0 }
   mc[0] = 1
   val hs = HashSet<Int>(n * (n + 1) / 2)
   hs.add(2)
   val hsx = mutableListOf<Int>()
   for (i in 1 until n) {
       hsx.clear()
       var j = mc[i - 1]
       outer@ while (true) {
           j++
           mc[i] = j
           for (k in 0..i) {
               val sum = mc[k] + j
               if (hs.contains(sum)) {
                   hsx.clear()
                   continue@outer
               }
               hsx.add(sum)
           }
           hs.addAll(hsx)
           break
       }
   }
   return mc

}

fun main() {

   val mc = mianChowla(100)
   println("The first 30 terms of the Mian-Chowla sequence are:")
   println(mc.subList(0, 30))
   println("\nTerms 91 to 100 of the Mian-Chowla sequence are:")
   println(mc.subList(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]

Pascal

Works with: Free Pascal

keep sum of all sorted.Memorizing the compare positions speeds up.
Calculating runtime to expect.

n-> 2x n ~> 
average distance between d = mian[n]-mian[n-1] d ~ 4x d 
runtime  t-> >10x t. -> 
  n       mian[n]  avg dist  runtime
  2700   225432491  195419   43411 ms
  5400  1613654038  766839  471468 ms

So calculating mian[25000] = mian[5940*(2**2,0733)] runtime minimum > 10.86**2.0733 *471.5s = 66251 s and round about 2.5 Gbyte for Uint64. One or two days should be enough. <lang pascal>program MianChowla; //compiling with /usr/lib/fpc/3.2.0/ppcx64.2 -MDelphi -O4 -al "%f" {$CODEALIGN proc=8,loop=4 } uses

 sysutils;

const

 deltaK = 100;
 maxCnt = 1000;

{

 deltaK = 540;
 maxCnt = (5966 DIV deltaK)*deltaK;
 *}

type

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

var

 n_LastPos,
 n : t_n;

 n_sum_all : t_n_sum_all;

 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 := 0 to maxCnt do
   n_LastPos[i] := 1;

end;

procedure InsertNew_sum(NewValue:NativeUint); //insertionsort var

 pElem :tpElem;
 InsIdx,chkIdx,oldIdx,newIdx : nativeInt;

Begin

 newIdx := maxIdx;
 oldIdx := max_SumIdx;
 //append new value
 inc(maxIdx);
 n[maxIdx] := NewValue;
 //extend sum_
 inc(max_SumIdx,maxIdx);
 //heighest value already known
 InsIdx := max_SumIdx;
 n_sum_all[InsIdx] := 2*NewValue;
 //stop mark
 n_sum_all[InsIdx+1] := High(tElem);
 pElem := @n_sum_all[0];
 dec(InsIdx);
 //n_LastPos[newIdx]+newIdx-1 == InsIdx
 repeat
   //move old bigger values
   chkIdx := n_LastPos[newIdx]+newIdx-1;
   while InsIdx > chkIdx do
   Begin
     pElem[InsIdx] := pElem[oldIdx];
     dec(InsIdx);
     dec(oldIdx);
   end;
   //insert new value
   pElem[InsIdx] := NewValue+n[newIdx];
   dec(InsIdx);
   dec(newIdx);
   //all inserted
 until newIdx <= 0;
 //new minimum search position one behind, oldidx is one to small
 inc(oldidx,2);
 For newIdx := 1 to maxIdx do
   n_LastPos[newIdx] := oldIdx;

end; procedure FindNew; var

 pSumAll,pn : tpElem;
 i,LastCheckPos,newValue,newSum : NativeUint;
 TestRes : boolean;

begin

 //start value = last inserted value
 newValue := n[maxIdx];
 pSumAll := @n_sum_all[0];
 pn := @n[0];
 repeat
   //try next number
   inc(newValue);
   LastCheckPos := n_LastPos[1];
   i := 1;
   //check if sum = new is already n all_sum
   repeat
     newSum := newValue+pn[i];
     IF LastCheckPos < n_LastPos[i] then
       LastCheckPos := n_LastPos[i];
     while pSumAll[LastCheckPos] < newSum do
       inc(LastCheckPos);
     //memorize LastCheckPos;
     n_LastPos[i] := LastCheckPos;
     TestRes:= pSumAll[LastCheckPos] = newSum;
     IF TestRes then
       BREAK;
     inc(i);
   until i>maxIdx;
   //found?
   If not(TestRes) then
     BREAK;
 until false;
 InsertNew_sum(newValue);

end;

var

 T1,T0: Int64;
 i,k : NativeInt;

procedure Out_num(k:NativeInt); Begin

 T1 := GetTickCount64;
 //     k      n[k]     average dist last deltak          total time
 writeln(k:6,n[k]:12,(n[k]-n[k-deltaK+1]) DIV deltaK:8,T1-T0:8,' ms');

end;

BEGIN

 writeln('Allocated memory ',2*SizeOf(t_n)+Sizeof(t_n_sum_all));
 T0 := GetTickCount64;
 while t0 = GetTickCount64 do;
 T0 := GetTickCount64;
 Init;

 k := deltaK;
 i := 1;
 repeat
   repeat
     FindNew;
     inc(i);
   until i=k;
   Out_num(k);
   k := k+deltaK;
 until k>maxCnt;
 writeln;
 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 91 - 100 of the Mian-Chowla sequence are');
 For i := 91 to 100 do
   write(n[i],' ');
 writeln;

END. {#####

 deltaK = 540;
 maxCnt = (5966 DIV deltaK)*deltaK;

Allocated memory 70650384

  540     2574622    4767     234 ms
 1080    17315247   27269    2084 ms
 1620    53808559   67542    7876 ms
 2160   119743492  121877   20367 ms
 2700   225432491  195419   43411 ms
 3240   377659559  281283   80801 ms
 3780   585851493  384664  137472 ms
 4320   853722843  494787  217026 ms
 4860  1198603744  637443  328136 ms
 5400  1613654038  766839  471468 ms
 5940  2124053407  944624  659681 ms

real 10m59,682s } </lang>

Output:

Allocated memory 2014024
   100       27219     272   0.002 s
   200      172922    1443   0.011 s
   300      514644    3404   0.037 s
   400     1144080    6197   0.090 s
   500     2085045    9398   0.179 s
   600     3375910   12689   0.311 s
   700     5253584   18705   0.520 s
   800     7600544   23438   0.801 s
   900    10441056   28339   1.160 s
  1000    14018951   35611   1.640 s
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 91 - 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;
   ((|@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)

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(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)

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. fst :: (a, b) -> a

def fst(tpl):

   First component of a tuple.
   return tpl[0]

1. snd :: (a, b) -> b

def snd(tpl):

   Second component of a tuple.
   return tpl[1]

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]

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

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

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.

Or using an Enumerator:

<lang ruby>mian_chowla = Enumerator.new do |yielder|

 mc, sums  = [1], {}
 1.step do |n|
   mc << n
   if  mc.none?{|k| sums[k+n] } then
     mc.each{|k| sums[k+n] = true }
     yielder << n
   else 
     mc.pop # n didn't work, get rid of it.
   end
 end

end

res = mian_chowla.take(100).to_a

s = " of the Mian-Chowla sequence are:\n" puts "The first 30 terms#{s}#{res[0,30].join(' ')}\n Terms 91 to 100#{s}#{res[90,10].join(' ')}" </lang>

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.