Mian-Chowla sequence: Difference between revisions

{{task}}

The [[wp:Mian–Chowla sequence|Mian–Chowla sequence]] is an integer sequence defined recursively.

 

The sequence starts with:

:* [[oeis:A005282|OEIS:A005282 Mian-Chowla sequence]]

 

 

=={{header|ALGOL 68}}==

{{works with|ALGOL 68G|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.

where: ai = 1,

and: an = smallest integer such that ai + aj is unique

FOR i FROM 91 TO 100 DO print( ( " ", whole( mc[ i ], 0 ) ) ) OD

 

{{out}}

<pre>

</pre>

elapsed time approx 0.25 seconds on my Windows 7 system (note under Windows, A68G runs as an interpreter only).

 

=={{header|AWK}}==

Translation of the ALGOL 68 - largely implements the "by hand" method in the task.

# where: ai = 1,

# and: an = smallest integer such that ai + aj is unique

printf( "\n" );

 

{{out}}

<pre>

===Alternate===

{{trans|Go}}Hopefully the comments help explain the algorithm.

#

# determine if a list is empty or not

} # for i

print "\n"

{{out}}

<pre>Mian Chowla sequence elements 1..30:

=={{header|C}}==

{{trans|Go}}

#include <stdbool.h>

#include <time.h>

for (int i = 90; i < 100; i++) printf("%d ", mc[i]);

printf("\n\nComputation time was %f seconds.", et);

{{out}}

<pre>The first 30 terms of the Mian-Chowla sequence are:

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

#include <stdlib.h>

#include <stdbool.h>

char buf[100]; approx(buf, nn * sizeof(bool));

printf("\n\nComputation time was %6.3f ms. Allocation was %s.", et, buf);

{{out}}

<pre>The first 30 terms of the Mian-Chowla sequence are:

=={{header|C#|CSharp}}==

{{trans|Go}}

using System.Collections.Generic;

using System.Diagnostics;

string.Join(" ", mc.Skip(n - 10)), sw.ElapsedMilliseconds);

}

{{out}}

<pre>The first 30 terms of the Mian-Chowla sequence are:

{{trans|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).

 

#include <iostream>

for (int i = 90; i < 100; i++) { cout << mc[i] << ' '; }

cout << "\n\nComputation time was " << et << " seconds.";

{{out}}

<pre>The first 30 terms of the Mian-Chowla sequence are:

=={{header|F_Sharp|F#}}==

===The function===

// Generate Mian-Chowla sequence. Nigel Galloway: March 23rd., 2019

let mC=let rec fN i g l=seq{

yield b; yield! fN (l::i) (a|>List.filter(fun n->n>b)) b}

seq{yield 1; yield! fN [] [] 1}

===The Tasks===

;First 30

mC |> Seq.take 30 |> Seq.iter(printf "%d ");printfn ""

{{out}}

<pre>

</pre>

;91 to 100

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

{{out}}

<pre>

22526 23291 23564 23881 24596 24768 25631 26037 26255 27219

</pre>

=={{header|Go}}==

 

import "fmt"

fmt.Println("\nTerms 91 to 100 of the Mian-Chowla sequence are:")

fmt.Println(mc[90:100])

 

{{out}}

<br>

Quicker version (runs in less than 0.02 seconds on Celeron N3050 @1.6 GHz), output as before:

 

import "fmt"

fmt.Println("\nTerms 91 to 100 of the Mian-Chowla sequence are:")

fmt.Println(mc[90:100])

 

=={{header|JavaScript}}==

'use strict';

 

const main = () => {

const genMianChowla = mianChowlas();

console.log([

'Mian-Chowla terms 1-30:',

 

'\nMian-Chowla terms 91-100:',

].join('\n') + '\n');

};

function* mianChowlas() {

let

sumSet = new Set([2]),

x = 1;

while (true) {

yield x;

}

}

 

// Set of sums -> Series up to n -> Next term in series

return [

),

];

};

 

// sumList :: [Int] -> Int -> [Int]

 

 

 

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

// drop :: Int -> Generator [a] -> Generator [a]

// drop :: Int -> String -> String

xs.slice(n)

 

 

// length :: [a] -> Int

const length = xs =>

xs.length

) : Infinity;

 

 

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

// take :: Int -> String -> String

xs.slice(0, n)

) : [].concat.apply([], Array.from({

return x.done ? [] : [x.value];

}));

 

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

 

// MAIN ---

return main();

{{Out}}

<pre>Mian-Chowla terms 1-30:

 

Mian-Chowla terms 91-100:

 

 

 

=={{header|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.

seq = ones(Int, n)

sums = Dict{Int,Int}()

@time testmianchowla()

 

<pre>

...

0.007524 seconds (168 allocations: 404.031 KiB)

</pre>

=={{header|Pascal}}==

{{works with|Free Pascal}}

keep sum of all sorted.Memorizing the compare positions speeds up.

const

type

t_n = array[0..maxCnt+1] of tElem;

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

 

var

n_sum_all : t_n_sum_all;

 

maxIdx,

max_SumIdx := 1;

n_sum_all[max_SumIdx] := 2*maxN;

n_LastPos[i] := 1;

end;

 

procedure InsertNew_sum(NewValue:NativeUint);

var

pElem :tpElem;

Begin

newIdx := maxIdx;

oldIdx := max_SumIdx;

//extend sum_

inc(max_SumIdx,maxIdx);

//heighest value already known

repeat

Begin

dec(oldIdx);

end;

dec(newIdx);

end;

procedure FindNew;

var

TestRes : boolean;

begin

repeat

i := 1;

IF LastCheckPos < n_LastPos[i] then

LastCheckPos := n_LastPos[i];

inc(LastCheckPos);

IF TestRes then

BREAK;

//found?

If not(TestRes) then

BREAK;

until false;

end;

 

var

BEGIN

Init;

writeln(#13,'The first 30 terms of the Mian-Chowla sequence are');

For i := 1 to 30 do

writeln;

writeln;

write(n[i],' ');

writeln;

END.

{{Out}}

 

 

=={{header|Perl}}==

use warnings;

use feature 'say';

my @mian_chowla = generate_mc(100);

say "First 30 terms in the Mian–Chowla sequence:\n", join(' ', @mian_chowla[ 0..29]),

{{out}}

<pre>First 30 terms in the Mian–Chowla sequence:

22526 23291 23564 23881 24596 24768 25631 26037 26255 27219</pre>

 

{{out}}

 

=={{header|Python}}==

===Procedural===

import time

 

pretty("The first 30 terms", ts, 0, 30)

pretty("\nTerms 91 to 100", ts, 90, 100)

{{out}}

<pre>The first 30 terms of the Mian-Chowla sequence are:

Computation time was 53.58004570007324 ms</pre>

 

 

from itertools import (islice)

 

 

def mianChowlas():

sumSet = set([2])

x = 1

while True:

yield x

 

 

 

 

 

'''Tests'''

 

genMianChowlas = mianChowlas()

print(

take(10)(genMianChowlas),

'\n'

)

 

 

 

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

 

 

 

 

 

if __name__ == '__main__':

{{Out}}

<pre>First 30 terms of the Mian-Chowla series:

 

Terms 91 to 100 of the Mian-Chowla series:

 

=={{header|REXX}}==

do j=i to t; ···

but the 1^st version is faster.

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

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

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

end /*j*/

end /*i*/

#= # + 1 /*bump the counter of terms in the list*/

end /*t*/

say 'The Mian─Chowla sequence for terms ' LO "──►" HI ' (inclusive):'

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

The Mian─Chowla sequence for terms 91 ──► 100 (inclusive):

22526 23291 23564 23881 24596 24768 25631 26037 26255 27219

</pre>

 

=={{header|Ruby}}==

{{trans|Go}}

n, ts, mc, sums = 100, [], [1], Set.new

sums << 2

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"

{{out}}

<pre>The first 30 terms of the Mian-Chowla sequence are:

Or using an Enumerator:

 

mc, sums = [1], {}

1.step do |n|

puts "The first 30 terms#{s}#{res[0,30].join(' ')}\n

Terms 91 to 100#{s}#{res[90,10].join(' ')}"

 

=={{header|Sidef}}==

{{trans|Go}}

for i in (1 ..^ n) {

for j in (mc[i-1]+1 .. Inf) {

for k in (0 .. i) {

var sum = mc[k]+j

ts.clear

break

}

if (ts.len > 0) {

break

}

}

}

var s = " of the Mian-Chowla sequence are:\n"

{{out}}

<pre>The first 30 terms of the Mian-Chowla sequence are:

22526 23291 23564 23881 24596 24768 25631 26037 26255 27219

 

 

=={{header|VBScript}}==

Const m = 100, mm=28000

ReDim r(mm), v(mm * 2)

wscript.echo "The Mian-Chowla sequence for elements 91 to 100:"

wscript.echo s2

{{out}}

<pre>

'''Shorter execution time'''

{{trans|Go}}

 

Function Find(x(), val) ' finds val on a pre-sorted list

If i < 30 or i >= 90 Then wscript.stdout.write(mc(i) & " ")

Next

{{out}}

''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.<br/>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.

=={{header|Visual Basic .NET}}==

{{trans|Go}}

Function MianChowla(ByVal n As Integer) As Integer()

Dim mc(n - 1) As Integer, sums, ts As New HashSet(Of Integer),

String.Join(" ", mc.Take(30)), String.Join(" ", mc.Skip(n - 10)), sw.ElapsedMilliseconds)

End Sub

{{out}}

<pre>The first 30 terms of the Mian-Chowla sequence are:

 

Computation time was 18ms.</pre>