Mian-Chowla sequence: Difference between revisions

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

 

 

=={{header|Ada}}==

{{works with|Ada|Ada|2012}}

 

with Ada.Containers.Hashed_Sets;

 

Ada.Text_IO.Put(term'Img);

end loop;

{{out}}

<pre>Mian Chowla sequence first 30 terms :

22526 23291 23564 23881 24596 24768 25631 26037 26255 27219

</pre>

 

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

 

=={{header|Factor}}==

 

: next ( seq sums speculative -- seq' sums' speculative' )

[ 30 head "First 30 terms of the Mian-Chowla sequence:" ]

[ 10 tail* "Terms 91-100 of the Mian-Chowla sequence:" ] bi

{{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|Haskell}}==

{{Trans|Python}}

{{Trans|JavaScript}}

 

mianChowlas :: Int -> [Int]

 

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

nextMC (sumSet, mcs@(n:_)) =

 

main :: IO ()

main =

, "Terms 91 to 100 of the Mian-Chowla series:"

, show $ drop 90 (mianChowlas 100)

{{Out}}

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

=={{header|J}}==

 

NB. http://rosettacode.org/wiki/Mian-Chowla_sequence

 

 

prime_q =: 1&p: NB. for fun look at prime generation suitability

 

<pre>

0 1 0 0 0 0 0 0 0 0

</pre>

=={{header|Java}}==

 

import java.util.Arrays;

 

 

}

{{out}}

<pre>

=={{header|JavaScript}}==

{{Trans|Python}} (Functional Python version)

'use strict';

 

const main = () => {

const genMianChowla = mianChowlas();

console.log([

'Mian-Chowla terms 1-30:',

 

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

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

};

return true;

};

return [

.reduce(

(a, n) => (a.add(n), a),

mcs.concat(x),

x

};

 

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

// Series so far -> additional term -> new sums

 

 

 

// 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|Kotlin}}==

 

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

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

println(mc.subList(90, 100))

 

{{output}}

[22526, 23291, 23564, 23881, 24596, 24768, 25631, 26037, 26255, 27219]

</pre>

 

=={{header|Pascal}}==

real 1932m34,698s => 1d8h12m35</pre>

//compiling with /usr/lib/fpc/3.2.0/ppcx64.2 -MDelphi -O4 -al "%f"

{$CODEALIGN proc=8,loop=4 }

writeln;

END.

{{Out}}

<pre>Allocated memory 2014024

 

=={{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:

 

=={{header|Phix}}==

{{out}}

<pre>

=={{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:

===Functional===

{{Works with|Python|3.7}}

 

from itertools import (islice)

 

if __name__ == '__main__':

{{Out}}

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

 

(Computation time c. 27 ms)</pre>

 

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

end /*i*/

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

end /*t*/

/*stick a fork in it, we're all done. */

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

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

<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|Swift}}==

{{trans|Go}}

 

var mc = Array(repeating: 0, count: n)

var ls = [2: true]

 

print("First 30 terms in sequence are: \(Array(seq.prefix(30)))")

 

{{out}}

 

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