Mian-Chowla sequence

From Rosetta Code
Revision as of 18:56, 15 March 2019 by Hout (talk | contribs) (→‎{{header|Python}}: (minor simplification of set update))
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


C#

Translation of: Go

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

static class Program { 

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

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

}</lang>

Output:
The first 30 terms of the Mian-Chowla sequence are:
1 2 4 8 13 21 31 45 66 81 97 123 148 182 204 252 290 361 401 475 565 593 662 775 822 916 970 1016 1159 1312

Terms 91 to 100 of the Mian-Chowla sequence are:
22526 23291 23564 23881 24596 24768 25631 26037 26255 27219

Computation time was 1.1993837 seconds.

Go

<lang go>package main

import "fmt"

func contains(is []int, s int) bool { 

   for _, i := range is {
       if s == i {
           return true
       }
   }
   return false

}

func mianChowla(n int) []int { 

   mc := make([]int, n)
   mc[0] = 1
   is := []int{2}
   var sum int
   for i := 1; i < n; i++ {
       le := len(is)
   jloop:
       for j := mc[i-1] + 1; ; j++ {
           mc[i] = j
           for k := 0; k <= i; k++ {
               sum = mc[k] + j
               if contains(is, sum) {
                   is = is[0:le]
                   continue jloop
               }
               is = append(is, sum)
           }
           break
       }
   }
   return mc

}

func main() { 

   mc := mianChowla(100)
   fmt.Println("The first 30 terms of the Mian-Chowla sequence are:")
   fmt.Println(mc[0:30])
   fmt.Println("\nTerms 91 to 100 of the Mian-Chowla sequence are:")
   fmt.Println(mc[90:100])

}</lang>

Output:
The first 30 terms of the Mian-Chowla sequence are:
[1 2 4 8 13 21 31 45 66 81 97 123 148 182 204 252 290 361 401 475 565 593 662 775 822 916 970 1016 1159 1312]

Terms 91 to 100 of the Mian-Chowla sequence are:
[22526 23291 23564 23881 24596 24768 25631 26037 26255 27219]


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)
   tempsums = Vector{Int}()
   for i in 2:n
       seq[i] = seq[i - 1] + 1
       trialsums = deepcopy(tempsums)
       incrementing = true
       while incrementing
           for j in 1:i
               tsum = seq[j] + seq[i]
               if tsum in tempsums
                   seq[i] += 1
                   tempsums = deepcopy(trialsums)
                   break
               else
                   push!(tempsums, tsum)
                   if j == i
                       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

@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.551461 seconds (246.32 k allocations: 1.126 GiB, 4.92% 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

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


Alternatively, composing generic functions, and (as it happens) executing a little faster: <lang python>"""Mian-Chowla series"""

from functools import (reduce) 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 -> Next term in series
   def go(xs, n):
       q = until(
           lambda x: every(lambda v: v not in setSums)(
               sumList(xs)(x)
           )
       )(succ)(succ(n))
       setSums.update(sumList(xs)(q))
       return (setSums, q)
   return lambda preds: lambda n: go(preds, n)


  1. sumList :: [Int] -> Int -> [Int]

def sumList(xs): 

   Series so far -> additional term -> additional sums
   return lambda n: [2 * n] + [n + x for x in xs]


  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. every :: (a -> Bool) -> [a] -> Bool

def every(p): 

   True if p(x) holds for every x in xs
   return lambda xs: all(map(p, xs))


  1. succ :: Int -> Int

def succ(x): 

   Succeeding value in Integer series
   return 1 + x


  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.23s]

(Executed in Atom editor, using Run Script)

REXX

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

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

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

output   when using the default inputs:
The Mian─Chowla sequence for elements  1 ──► 30  (inclusive):
1 2 4 8 13 21 31 45 66 81 97 123 148 182 204 252 290 361 401 475 565 593 662 775 822 916 970 1016 1159 1312
output   when using the input of:     91   100 
The Mian─Chowla sequence for elements  91 ──► 100  (inclusive):
22526 23291 23564 23881 24596 24768 25631 26037 26255 27219

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


Visual Basic .NET

Translation of: Go

<lang vbnet>Module Module1 

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

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

End Module</lang>

Output:
The first 30 terms of the Mian-Chowla sequence are:
1 2 4 8 13 21 31 45 66 81 97 123 148 182 204 252 290 361 401 475 565 593 662 775 822 916 970 1016 1159 1312

Terms 91 to 100 of the Mian-Chowla sequence are:
22526 23291 23564 23881 24596 24768 25631 26037 26255 27219

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