Mian-Chowla sequence: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
(Added Kotlin) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
(48 intermediate revisions by 23 users not shown) | |||
Line 1:
{{task}}
The [[wp:Mian–Chowla sequence|Mian–Chowla sequence]] is an integer sequence defined recursively.
Mian–Chowla is an infinite instance of a [[wp:Sidon sequence|Sidon sequence]], and belongs to the class known as B₂ sequences.
The sequence starts with:
Line 60 ⟶ 64:
:* [[oeis:A005282|OEIS:A005282 Mian-Chowla sequence]]
=={{header|11l}}==
{{trans|C++}}
<syntaxhighlight lang="11l">F contains(sums, s, ss)
L(i) 0 .< ss
I sums[i] == s
R 1B
R 0B
F mian_chowla()
V n = 100
V mc = [0] * n
mc[0] = 1
V sums = [0] * ((n * (n + 1)) >> 1)
sums[0] = 2
V ss = 1
L(i) 1 .< n
V le = ss
V j = mc[i - 1] + 1
L
mc[i] = j
V nxtJ = 0B
L(k) 0 .. i
V sum = mc[k] + j
I contains(sums, sum, ss)
ss = le
nxtJ = 1B
L.break
sums[ss] = sum
ss++
I !nxtJ
L.break
j++
R mc
print(‘The first 30 terms of the Mian-Chowla sequence are:’)
V mc = mian_chowla()
print_elements(mc[0.<30])
print()
print(‘Terms 91 to 100 of the Mian-Chowla sequence are:’)
print_elements(mc[90..])</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Ada}}==
{{works with|Ada|Ada|2012}}
<syntaxhighlight lang="ada">with Ada.Text_IO;
with Ada.Containers.Hashed_Sets;
procedure Mian_Chowla_Sequence
is
type Natural_Array is array(Positive range <>) of Natural;
function Hash(P : in Positive) return Ada.Containers.Hash_Type is
begin
return Ada.Containers.Hash_Type(P);
end Hash;
package Positive_Sets is new Ada.Containers.Hashed_Sets(Positive, Hash, "=");
function Mian_Chowla(N : in Positive) return Natural_Array
is
return_array : Natural_Array(1 .. N) := (others => 0);
nth : Positive := 1;
candidate : Positive := 1;
seen : Positive_Sets.Set;
begin
while nth <= N loop
declare
sums : Positive_Sets.Set;
terms : constant Natural_Array := return_array(1 .. nth-1) & candidate;
found : Boolean := False;
begin
for term of terms loop
if seen.Contains(term + candidate) then
found := True;
exit;
else
sums.Insert(term + candidate);
end if;
end loop;
if not found then
return_array(nth) := candidate;
seen.Union(sums);
nth := nth + 1;
end if;
candidate := candidate + 1;
end;
end loop;
return return_array;
end Mian_Chowla;
length : constant Positive := 100;
sequence : constant Natural_Array(1 .. length) := Mian_Chowla(length);
begin
Ada.Text_IO.Put_Line("Mian Chowla sequence first 30 terms :");
for term of sequence(1 .. 30) loop
Ada.Text_IO.Put(term'Img);
end loop;
Ada.Text_IO.New_Line;
Ada.Text_IO.Put_Line("Mian Chowla sequence terms 91 to 100 :");
for term of sequence(91 .. 100) loop
Ada.Text_IO.Put(term'Img);
end loop;
end Mian_Chowla_Sequence;</syntaxhighlight>
{{out}}
<pre>Mian Chowla sequence first 30 terms :
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 terms 91 to 100 :
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
Line 103 ⟶ 227:
FOR i FROM 91 TO 100 DO print( ( " ", whole( mc[ i ], 0 ) ) ) OD
END</
{{out}}
<pre>
Line 112 ⟶ 236:
</pre>
elapsed time approx 0.25 seconds on my Windows 7 system (note under Windows, A68G runs as an interpreter only).
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">mianChowla: function [n][
result: new [1]
sums: new [2]
candidate: 1
while [n > size result][
fit: false
'result ++ 0
while [not? fit][
candidate: candidate + 1
fit: true
result\[dec size result]: candidate
loop result 'val [
if contains? sums val + candidate [
fit: false
break
]
]
]
loop result 'val [
'sums ++ val + candidate
unique 'sums
]
]
return result
]
seq100: mianChowla 100
print "The first 30 terms of the Mian-Chowla sequence are:"
print slice seq100 0 29
print ""
print "Terms 91 to 100 of the sequence are:"
print slice seq100 90 99</syntaxhighlight>
{{out}}
<pre>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 sequence are:
22526 23291 23564 23881 24596 24768 25631 26037 26255 27219</pre>
=={{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
Line 162 ⟶ 333:
printf( "\n" );
} # BEGIN</
{{out}}
<pre>
Line 174 ⟶ 345:
===Alternate===
{{trans|Go}}Hopefully the comments help explain the algorithm.
<
#
# determine if a list is empty or not
Line 215 ⟶ 386:
} # for i
print "\n"
} # BEGIN</
{{out}}
<pre>Mian Chowla sequence elements 1..30:
Line 226 ⟶ 397:
=={{header|C}}==
{{trans|Go}}
<
#include <stdbool.h>
#include <time.h>
Line 270 ⟶ 441:
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:
Line 281 ⟶ 452:
===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>
Line 330 ⟶ 501:
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:
Line 352 ⟶ 523:
=={{header|C#|CSharp}}==
{{trans|Go}}
<
using System.Collections.Generic;
using System.Diagnostics;
Line 385 ⟶ 556:
string.Join(" ", mc.Skip(n - 10)), sw.ElapsedMilliseconds);
}
}</
{{out}}
<pre>The first 30 terms of the Mian-Chowla sequence are:
Line 398 ⟶ 569:
{{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>
Line 442 ⟶ 613:
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:
Line 454 ⟶ 625:
=={{header|F_Sharp|F#}}==
===The function===
<
// Generate Mian-Chowla sequence. Nigel Galloway: March 23rd., 2019
let mC=let rec fN i g l=seq{
Line 461 ⟶ 632:
yield b; yield! fN (l::i) (a|>List.filter(fun n->n>b)) b}
seq{yield 1; yield! fN [] [] 1}
</syntaxhighlight>
===The Tasks===
;First 30
<
mC |> Seq.take 30 |> Seq.iter(printf "%d ");printfn ""
</syntaxhighlight>
{{out}}
<pre>
Line 472 ⟶ 643:
</pre>
;91 to 100
<
mC |> Seq.skip 90 |> Seq.take 10 |> Seq.iter(printf "%d ");printfn ""
</syntaxhighlight>
{{out}}
<pre>
22526 23291 23564 23881 24596 24768 25631 26037 26255 27219
</pre>
=={{header|Factor}}==
<syntaxhighlight lang="factor">USING: fry hash-sets io kernel math prettyprint sequences sets ;
: next ( seq sums speculative -- seq' sums' speculative' )
dup reach [ + ] with map over dup + suffix! >hash-set pick
over intersect null?
[ swapd union [ [ suffix! ] keep ] dip swap ] [ drop ] if
1 + ;
: mian-chowla ( n -- seq )
[ V{ 1 } HS{ 2 } [ clone ] bi@ 2 ] dip
'[ pick length _ < ] [ next ] while 2drop ;
100 mian-chowla
[ 30 head "First 30 terms of the Mian-Chowla sequence:" ]
[ 10 tail* "Terms 91-100 of the Mian-Chowla sequence:" ] bi
[ print [ pprint bl ] each nl nl ] 2bi@</syntaxhighlight>
{{out}}
<pre>
First 30 terms of 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-100 of the Mian-Chowla sequence:
22526 23291 23564 23881 24596 24768 25631 26037 26255 27219
</pre>
=={{header|FreeBASIC}}==
<syntaxhighlight lang="freebasic">redim as uinteger mian(0 to 1)
redim as uinteger sums(0 to 2)
mian(0) = 1 : mian(1) = 2
sums(0) = 2 : sums(1) = 3 : sums(2) = 4
dim as uinteger n_mc = 2, n_sm = 3, curr = 3, tempsum
while n_mc < 101
for i as uinteger = 0 to n_mc - 1
tempsum = curr + mian(i)
for j as uinteger = 0 to n_sm - 1
if tempsum = sums(j) then goto loopend
next j
next i
redim preserve as uinteger mian(0 to n_mc)
mian(n_mc) = curr
redim preserve as uinteger sums(0 to n_sm + n_mc)
for j as uinteger = 0 to n_mc - 1
sums(n_sm + j) = mian(j) + mian(n_mc)
next j
n_mc += 1
n_sm += n_mc
sums(n_sm-1) = 2*curr
loopend:
curr += 1
wend
print "Mian-Chowla numbers 1 through 30: ",
for i as uinteger = 0 to 29
print mian(i),
next i
print
print "Mian-Chowla numbers 91 through 100: ",
for i as uinteger = 90 to 99
print mian(i),
next i
print</syntaxhighlight>
{{out}}
<pre>
Mian-Chowla numbers 1 through 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 numbers 91 through 100: 22526 23291 23564 23881 24596 24768 25631 26037 26255 27219</pre>
=={{header|Go}}==
<
import "fmt"
Line 523 ⟶ 765:
fmt.Println("\nTerms 91 to 100 of the Mian-Chowla sequence are:")
fmt.Println(mc[90:100])
}</
{{out}}
Line 535 ⟶ 777:
<br>
Quicker version (runs in less than 0.02 seconds on Celeron N3050 @1.6 GHz), output as before:
<
import "fmt"
Line 576 ⟶ 818:
fmt.Println("\nTerms 91 to 100 of the Mian-Chowla sequence are:")
fmt.Println(mc[90:100])
}</
=={{header|Haskell}}==
{{Trans|Python}}
{{Trans|JavaScript}}
<syntaxhighlight lang="haskell">import Data.Set (Set, fromList, insert, member)
------------------- MIAN-CHOWLA SEQUENCE -----------------
mianChowlas :: Int -> [Int]
mianChowlas =
reverse . snd . (iterate nextMC (fromList [2], [1]) !!) . subtract 1
nextMC :: (Set Int, [Int]) -> (Set Int, [Int])
nextMC (sumSet, mcs@(n:_)) =
(foldr insert sumSet ((2 * m) : fmap (m +) mcs), m : mcs)
where
valid x = not $ any (flip member sumSet . (x +)) mcs
m = until valid succ n
--------------------------- TEST -------------------------
main :: IO ()
main =
(putStrLn . unlines)
[ "First 30 terms of the Mian-Chowla series:"
, show (mianChowlas 30)
, []
, "Terms 91 to 100 of the Mian-Chowla series:"
, show $ drop 90 (mianChowlas 100)
]</syntaxhighlight>
{{Out}}
<pre>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]</pre>
=={{header|J}}==
<syntaxhighlight lang="j">
NB. http://rosettacode.org/wiki/Mian-Chowla_sequence
NB. Dreadfully inefficient implementation recomputes all the sums to n-1
NB. and computes the full addition table rather than just a triangular region
NB. However, this implementation is sufficiently quick to meet the requirements.
NB. The vector head is the next speculative value
NB. Beheaded, the vector is Mian-Chowla sequence.
Until =: conjunction def 'u^:(0 = v)^:_'
unique =: -:&# ~. NB. tally of list matches that of set
next_mc =: [: (, {.) (>:@:{. , }.)Until(unique@:((<:/~@i.@# #&, +/~)@:(}. , {.)))
prime_q =: 1&p: NB. for fun look at prime generation suitability
</syntaxhighlight>
<pre>
NB. generate sufficient terms of sequence
A =: (next_mc^:108) 1 1
NB. first 30 terms
(,:prime_q)30{.}.A
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
0 1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0
NB. terms 91 through 100
(,: prime_q) A {~ 91+i.10
22526 23291 23564 23881 24596 24768 25631 26037 26255 27219
0 1 0 0 0 0 0 0 0 0
</pre>
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.util.Arrays;
public class MianChowlaSequence {
public static void main(String[] args) {
long start = System.currentTimeMillis();
System.out.println("First 30 terms of the Mian–Chowla sequence.");
mianChowla(1, 30);
System.out.println("Terms 91 through 100 of the Mian–Chowla sequence.");
mianChowla(91, 100);
long end = System.currentTimeMillis();
System.out.printf("Elapsed = %d ms%n", (end-start));
}
private static void mianChowla(int minIndex, int maxIndex) {
int [] sums = new int[1];
int [] chowla = new int[maxIndex+1];
sums[0] = 2;
chowla[0] = 0;
chowla[1] = 1;
if ( minIndex == 1 ) {
System.out.printf("%d ", 1);
}
int chowlaLength = 1;
for ( int n = 2 ; n <= maxIndex ; n++ ) {
// Sequence is strictly increasing.
int test = chowla[n - 1];
// Bookkeeping. Generate only new sums.
int[] sumsNew = Arrays.copyOf(sums, sums.length + n);
int sumNewLength = sums.length;
int savedsSumNewLength = sumNewLength;
// Generate test candidates for the next value of the sequence.
boolean found = false;
while ( ! found ) {
test++;
found = true;
sumNewLength = savedsSumNewLength;
// Generate test sums
for ( int j = 0 ; j <= chowlaLength ; j++ ) {
int testSum = (j == 0 ? test : chowla[j]) + test;
boolean duplicate = false;
// Check if test Sum in array
for ( int k = 0 ; k < sumNewLength ; k++ ) {
if ( sumsNew[k] == testSum ) {
duplicate = true;
break;
}
}
if ( ! duplicate ) {
// Add to array
sumsNew[sumNewLength] = testSum;
sumNewLength++;
}
else {
// Duplicate found. Therefore, test candidate of the next value of the sequence is not OK.
found = false;
break;
}
}
}
// Bingo! Now update bookkeeping.
chowla[n] = test;
chowlaLength++;
sums = sumsNew;
if ( n >= minIndex ) {
System.out.printf("%d %s", chowla[n], (n==maxIndex ? "\n" : ""));
}
}
}
}
</syntaxhighlight>
{{out}}
<pre>
First 30 terms of 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 of the Mian–Chowla sequence.
22526 23291 23564 23881 24596 24768 25631 26037 26255 27219
Elapsed = 220 ms
</pre>
=={{header|JavaScript}}==
{{Trans|Python}} (
<
'use strict';
// main :: IO ()
const main = () => {
const genMianChowla = mianChowlas();
console.log([
'Mian-Chowla terms 1-30:',
take(30
genMianChowla
),
'\nMian-Chowla terms 91-100:',
(
drop(60
)
)
].join('\n') + '\n');
};
Line 601 ⟶ 1,007:
function* mianChowlas() {
let
sumSet = new Set([2]),
x = 1;
while (true) {
yield x;
[sumSet, mcs, x] =
}
}
//
const
// Set of sums -> Series up to n -> Next term in series
const valid = x => {
if (setSums.has(x
return
const x = until(valid)(x => 1 +
return [
),
x
];
};
// sumList :: [Int] -> Int -> [Int]
const sumList =
// Series so far -> additional term ->
n => [2 * n].concat(xs.map(x => n + x
//
// drop :: Int -> [a] -> [a]
// drop :: Int -> Generator [a] -> Generator [a]
// drop :: Int -> String -> String
const drop =
xs => Infinity > length(xs) ? (
xs.slice(n)
) : (take(n
// length :: [a] -> Int
const length = xs =>
// 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
'GeneratorFunction' !== xs.constructor
.constructor.name ? (
xs.length
) : Infinity;
// take :: Int -> [a] -> [a]
// take :: Int -> String -> String
const take =
// The first n elements of a list,
// string of characters, or stream.
xs => 'GeneratorFunction' !== xs
.constructor.constructor.name ? (
xs.slice(0, n)
) : [].concat.apply([], Array.from({
Line 685 ⟶ 1,080:
return x.done ? [] : [x.value];
}));
// until :: (a -> Bool) -> (a -> a) -> a -> a
const until =
};
// MAIN ---
return main();
})();</
{{Out}}
<pre>Mian-Chowla terms 1-30:
Line 701 ⟶ 1,098:
Mian-Chowla terms 91-100:
22526,23291,23564,23881,24596,24768,25631,26037,26255,27219</pre>
=={{header|jq}}==
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
<syntaxhighlight lang="jq">
# Input: a bag-of-words (bow)
# Output: either an augmented bow, or nothing if a duplicate is found
def augment_while_unique(stream):
label $out
| foreach ((stream|tostring), null) as $word (.;
if $word == null then .
elif has($word) then break $out
else .[$word] = 1
end;
select($word == null) );
# For speedup, store "sums" as a hash
def mian_chowlas:
{m:[1], sums: {"1":1}}
| recurse(
.m as $m
| .sums as $sums
| first(range(1+$m[-1]; infinite) as $i
| $sums
| augment_while_unique( ($m[] | (.+$i)), (2*$i))
| [$i, .] ) as [$i, $sums]
| {m: ($m + [$i]), $sums} )
| .m[-1] ;</syntaxhighlight>
'''The Tasks'''
<syntaxhighlight lang="jq">[limit(100; mian_chowlas)]
| "First thirty: \(.[:30]);",
"91st through 100th: \(.[90:])."</syntaxhighlight>
{{out}}
<pre>
First thirty: [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];
91st through 100th: [22526,23291,23564,23881,24596,24768,25631,26037,26255,27219].
</pre>
=={{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}()
Line 745 ⟶ 1,175:
@time testmianchowla()
</
<pre>
...
Line 752 ⟶ 1,182:
0.007524 seconds (168 allocations: 404.031 KiB)
</pre>
=={{header|Kotlin}}==
===Translation of Go===
<syntaxhighlight lang="scala">// Version 1.3.21
fun mianChowla(n: Int): List<Int> {
Line 789 ⟶ 1,222:
println("\nTerms 91 to 100 of the Mian-Chowla sequence are:")
println(mc.subList(90, 100))
}</
{{output}}
Line 799 ⟶ 1,232:
[22526, 23291, 23564, 23881, 24596, 24768, 25631, 26037, 26255, 27219]
</pre>
=== Idiomatic ===
<syntaxhighlight lang="kotlin">
fun sumsRemainDistinct(candidate: Int, seq: Iterable<Int>, sums: MutableSet<Int>): Boolean {
val candidateSums = mutableListOf<Int>()
for (s in seq) {
when ((candidate + s) !in sums) {
true -> candidateSums.add(candidate + s)
false -> return false
}
}
with(sums) {
addAll(candidateSums)
add(candidate + candidate)
}
return true
}
fun mianChowla(n: Int): List<Int> {
val bufferSeq = linkedSetOf<Int>()
val bufferSums = linkedSetOf<Int>()
val sequence = generateSequence(1) { it + 1 } // [1,2,3,..]
.filter { sumsRemainDistinct(it, bufferSeq, bufferSums) }
.onEach { bufferSeq.add(it) }
return sequence.take(n).toList()
}
fun main() {
mianChowla(100).also {
println("Mian-Chowla[1..30] = ${it.take(30)}")
println("Mian-Chowla[91..100] = ${it.drop(90)}")
}
}
</syntaxhighlight>
{{output}}
<pre>
Mian-Chowla[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[91..100] = [22526, 23291, 23564, 23881, 24596, 24768, 25631, 26037, 26255, 27219]
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">n = {m} = {1};
tmp = {2};
Do[
m++;
While[ContainsAny[tmp, m + n],
m++
];
tmp = Join[tmp, n + m];
AppendTo[tmp, 2 m];
AppendTo[n, m]
,
{99}
]
Row[Take[n, 30], ","]
Row[Take[n, {91, 100}], ","]</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|Nim}}==
<syntaxhighlight lang="nim">import intsets, strutils, times
proc mianchowla(n: Positive): seq[int] =
result = @[1]
var sums = [2].toIntSet()
var candidate = 1
while result.len < n:
# Test successive candidates.
var fit = false
result.add 0 # Make room for next value.
while not fit:
inc candidate
fit = true
result[^1] = candidate
# Check the sums.
for val in result:
if val + candidate in sums:
# Failed to satisfy criterium.
fit = false
break
# Add the new sums to the set of sums.
for val in result:
sums.incl val + candidate
let t0 = now()
let seq100 = mianchowla(100)
echo "The first 30 terms of the Mian-Chowla sequence are:"
echo seq100[0..29].join(" ")
echo ""
echo "Terms 91 to 100 of the sequence are:"
echo seq100[90..99].join(" ")
echo ""
echo "Computation time: ", (now() - t0).inMilliseconds, " ms"</syntaxhighlight>
{{out}}
<pre>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 sequence are:
22526 23291 23564 23881 24596 24768 25631 26037 26255 27219
Computation time: 2 ms</pre>
=={{header|Pascal}}==
{{works with|Free Pascal}}
keep sum of all sorted.Memorizing the compare positions speeds up.
<BR>
<pre>const
deltaK = 250;
maxCnt = 25000;
Using
tElem = Uint64;
t_n_sum_all = array of tElem; //dynamic array
n mian-chowla[n] average dist runtime
250 317739 1270 429 ms// runtime setlength of 2.35 GB ~ 400ms
500 2085045 7055 589 ms
750 6265086 16632 1053 ms
..
1500 43205712 67697 6669 ms
..
3000 303314913 264489 65040 ms //2xn -> runtime x9,75
..
6000 2189067236 1019161 719208 ms //2xn -> runtime x11,0
6250 2451223363 1047116 825486 ms
..
12000 15799915996 3589137 8180177 ms //2xn -> runtime x11,3
12250 16737557137 3742360 8783711 ms
12500 17758426186 4051041 9455371 ms
..
24000 115709049568 13738671 99959526 ms //2xn -> runtime x12
24250 119117015697 13492623 103691559 ms
24500 122795614247 14644721 107758962 ms
24750 126491059919 14708578 111875949 ms
25000 130098289096 14414457 115954691 ms //dt = 4078s ->16s/per number
real 1932m34,698s => 1d8h12m35</pre>
<syntaxhighlight 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
maxCnt = 1000;
type
tElem = Uint32;
tpElem =
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,
Line 832 ⟶ 1,410:
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);
//insertion already knowning the positions
var
pElem :tpElem;
InsIdx,chkIdx,oldIdx,newIdx
Begin
newIdx := maxIdx;
oldIdx := max_SumIdx;
Line 849 ⟶ 1,428:
//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
dec(InsIdx);
dec(oldIdx);
end;
dec(InsIdx);
dec(newIdx);
//all inserted
until newIdx <=
//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
pSumAll :=
pn := @n[0];
repeat
inc(newValue);
LastCheckPos := n_LastPos[1];
i := 1;
IF LastCheckPos < n_LastPos[i] then
LastCheckPos := n_LastPos[i];
while
inc(LastCheckPos);
n_LastPos[i] :=
TestRes:= pSumAll[LastCheckPos] = newSum;
IF TestRes then
BREAK;
until i>maxIdx;
//found?
If not(TestRes) then
BREAK;
until false;
InsertNew_sum(
end;
var
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 :=
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
Line 918 ⟶ 1,526:
writeln;
writeln;
writeln('The terms
For i :=
write(n[i],' ');
writeln;
END.
</syntaxhighlight>
{{Out}}
<pre>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
=={{header|Perl}}==
<
use warnings;
use feature 'say';
Line 966 ⟶ 1,572:
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]);</
{{out}}
<pre>First 30 terms in the Mian–Chowla sequence:
Line 974 ⟶ 1,580:
22526 23291 23564 23881 24596 24768 25631 26037 26255 27219</pre>
=={{header|
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">function</span> <span style="color: #000000;">mian_chowla</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">mc</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
<span style="color: #000000;">is</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">}</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">len_is</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">s</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">isx</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">j</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mc</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">1</span>
<span style="color: #000000;">mc</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mc</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mc</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mc</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">j</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">s</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">len_is</span> <span style="color: #008080;">and</span> <span style="color: #000000;">is</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">isx</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">isx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">isx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">isx</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">isx</span><span style="color: #0000FF;">[$]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">></span><span style="color: #000000;">len_is</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">is</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">-</span><span style="color: #000000;">len_is</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">len_is</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">is</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">isx</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">is</span><span style="color: #0000FF;">[</span><span style="color: #000000;">isx</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">j</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">mc</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">j</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">mc</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">mc</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mian_chowla</span><span style="color: #0000FF;">(</span><span style="color: #000000;">100</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The first 30 terms of the Mian-Chowla sequence are:\n %V\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">mc</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">30</span><span style="color: #0000FF;">]})</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Terms 91 to 100 of the Mian-Chowla sequence are:\n %V\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">mc</span><span style="color: #0000FF;">[</span><span style="color: #000000;">91</span><span style="color: #0000FF;">..</span><span style="color: #000000;">100</span><span style="color: #0000FF;">]})</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"completed in %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)})</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
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
{22526
completed in 0.1s
</pre>
=={{header|Python}}==
===Procedural===
<
import time
Line 1,027 ⟶ 1,663:
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")</
{{out}}
<pre>The first 30 terms of the Mian-Chowla sequence are:
Line 1,037 ⟶ 1,673:
Computation time was 53.58004570007324 ms</pre>
===Functional===
{{Works with|Python|3.7}}
<syntaxhighlight lang
from itertools import (islice)
from time import time
# mianChowlas ::
def mianChowlas():
'''Mian-Chowla series - Generator constructor
mcs = [1]
sumSet = set([2])
x = 1
while True:
yield x
(sumSet, mcs, x) =
#
def
'''(Set of sums
(updated sum set, updated series, next term)
'''
for m in
return False
return True
x =
[x + y for
)
Line 1,082 ⟶ 1,716:
'''Tests'''
start = time()
genMianChowlas = mianChowlas()
print(
Line 1,092 ⟶ 1,727:
take(10)(genMianChowlas),
'\n'
)
print(
'(Computation time c. ' + str(round(
1000 * (time() - start)
)) + ' ms)'
)
# GENERIC -------------------------------------------------
# drop :: Int -> [a] -> [a]
Line 1,111 ⟶ 1,751:
#
def
'''
return
Line 1,148 ⟶ 1,782:
if __name__ == '__main__':
main()</
{{Out}}
<pre>First 30 terms of the Mian-Chowla series:
Line 1,154 ⟶ 1,788:
Terms 91 to 100 of the Mian-Chowla series:
[22526, 23291, 23564, 23881, 24596, 24768, 25631, 26037, 26255, 27219]
(Computation time c. 27 ms)</pre>
=={{header|Quackery}}==
<syntaxhighlight lang="quackery"> [ stack ] is makeable ( --> s )
[ temp put
1 bit makeable put
' [ 1 ] 1
[ true temp put
1+
over witheach
[ over + bit
makeable share & if
[ false temp replace
conclude ] ]
temp take if
[ dup dip join
over witheach
[ over + bit
makeable take
| makeable put ] ]
over size temp share = until ]
makeable release
temp release
drop ] is mian-chowla ( n --> [ )
100 mian-chowla
30 split swap echo cr
-10 split nip echo</syntaxhighlight>
{{out}}
<pre>[ 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 ]
</pre>
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku" line>my @mian-chowla = 1, |(2..Inf).map: -> $test {
state $index = 1;
state %sums = 2 => 1;
my $next;
my %these;
@mian-chowla[^$index].map: { ++$next and last if %sums{$_ + $test}:exists; ++%these{$_ + $test} };
next if $next;
++%sums{$test + $test};
%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];</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|REXX}}==
Line 1,162 ⟶ 1,857:
do j=i to t; ···
but the 1<sup>st</sup> 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 t=1 until #=HI;
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
end /*j*/
end /*i*/
#= # + 1 /*bump the counter of terms in the list*/
if #>=LO
end /*t*/
/*stick a fork in it, we're all done. */
say 'The Mian─Chowla sequence for terms ' LO "──►" HI ' (inclusive):'
say strip($) /*ignore the leading superfluous blank.*/</
{{out|output|text= when using the default inputs:}}
<pre>
Line 1,196 ⟶ 1,891:
=={{header|Ruby}}==
{{trans|Go}}
<
n, ts, mc, sums = 100, [], [1], Set.new
sums << 2
Line 1,220 ⟶ 1,915:
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."</
{{out}}
<pre>The first 30 terms of the Mian-Chowla sequence are:
Line 1,232 ⟶ 1,927:
Or using an Enumerator:
<
mc, sums = [1], {}
1.step do |n|
Line 1,250 ⟶ 1,945:
puts "The first 30 terms#{s}#{res[0,30].join(' ')}\n
Terms 91 to 100#{s}#{res[90,10].join(' ')}"
</syntaxhighlight>
=={{header|Sidef}}==
{{trans|Go}}
<
var st = Time.
for i in (1 ..^ n) {
for j in (mc[i-1]+1 .. Inf) {
Line 1,261 ⟶ 1,956:
for k in (0 .. i) {
var sum = mc[k]+j
if (sums.
ts.clear
break
Line 1,268 ⟶ 1,963:
}
if (ts.len > 0) {
sums |=
break
}
}
}
var et = (Time.
var s = " of the Mian-Chowla sequence are:\n"
say "The first 30 terms#{s}#{mc.
say "Terms 91 to 100#{s}#{mc.
say "Computation time was #{et} seconds."</
{{out}}
<pre>The first 30 terms of the Mian-Chowla sequence are:
Line 1,285 ⟶ 1,980:
22526 23291 23564 23881 24596 24768 25631 26037 26255 27219
Computation time was
=={{header|Swift}}==
{{trans|Go}}
<syntaxhighlight lang="swift">public func mianChowla(n: Int) -> [Int] {
var mc = Array(repeating: 0, count: n)
var ls = [2: true]
var sum = 0
mc[0] = 1
for i in 1..<n {
var lsx = [Int]()
jLoop: for j in (mc[i-1]+1)... {
mc[i] = j
for k in 0...i {
sum = mc[k] + j
if ls[sum] ?? false {
lsx = []
continue jLoop
}
lsx.append(sum)
}
for n in lsx {
ls[n] = true
}
break
}
}
return mc
}
let seq = mianChowla(n: 100)
print("First 30 terms in sequence are: \(Array(seq.prefix(30)))")
print("Terms 91 to 100 are: \(Array(seq[90..<100]))")</syntaxhighlight>
{{out}}
<pre>First 30 terms in 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 are: [22526, 23291, 23564, 23881, 24596, 24768, 25631, 26037, 26255, 27219]</pre>
=={{header|VBScript}}==
<
Const m = 100, mm=28000
ReDim r(mm), v(mm * 2)
Line 1,332 ⟶ 2,076:
wscript.echo "The Mian-Chowla sequence for elements 91 to 100:"
wscript.echo s2
wscript.echo "Computation time: "& Int(Timer-t0) &" sec"</
{{out}}
<pre>
Line 1,345 ⟶ 2,089:
'''Shorter execution time'''
{{trans|Go}}
<
Function Find(x(), val) ' finds val on a pre-sorted list
Line 1,387 ⟶ 2,131:
If i < 30 or i >= 90 Then wscript.stdout.write(mc(i) & " ")
Next
wscript.echo vblf & vbLf & "Computation time: "& Timer - st &" seconds."</
{{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.
Line 1,400 ⟶ 2,144:
=={{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),
Line 1,426 ⟶ 2,170:
String.Join(" ", mc.Take(30)), String.Join(" ", mc.Skip(n - 10)), sw.ElapsedMilliseconds)
End Sub
End Module</
{{out}}
<pre>The first 30 terms of the Mian-Chowla sequence are:
Line 1,435 ⟶ 2,179:
Computation time was 18ms.</pre>
=={{header|Wren}}==
{{trans|C#}}
<syntaxhighlight lang="wrent">var mianChowla = Fn.new { |n|
var mc = List.filled(n, 0)
var sums = {}
var ts = {}
mc[0] = 1
sums[2] = true
for (i in 1...n) {
var j = mc[i-1] + 1
while (true) {
mc[i] = j
for (k in 0..i) {
var sum = mc[k] + j
if (sums[sum]) {
ts.clear()
break
}
ts[sum] = true
}
if (ts.count > 0) {
for (key in ts.keys) sums[key] = true
break
}
j = j + 1
}
}
return mc
}
var start = System.clock
var mc = mianChowla.call(100)
System.print("The first 30 terms of the Mian-Chowla sequence are:\n%(mc[0..29].join(" "))")
System.print("\nTerms 91 to 100 of the Mian-Chowla sequence are:\n%(mc[90..99].join(" "))")
System.print("\nTook %(((System.clock - start)*1000).round) milliseconds")</syntaxhighlight>
{{out}}
<pre>
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
Took 32 milliseconds
</pre>
=={{header|XPL0}}==
{{trans|C}}
Takes about 1.5 seconds on RPi-4.
<syntaxhighlight lang "XPL0">define N = 100;
define NN = (N * (N+1)) >> 1;
func Contains(Lst, Item, Size);
int Lst, Item, Size, I;
[for I:= Size-1 downto 0 do
if Item = Lst(I) then return true;
return false;
];
int MC(N);
proc MianChowla;
int Sums(NN), Sum, LE, SS, I, J, K;
[MC(0):= 1;
Sums(0):= 2;
SS:= 1;
for I:= 1 to N-1 do
[LE:= SS;
J:= MC(I-1) + 1;
MC(I):= J;
K:= 0;
loop [Sum:= MC(K) + J;
if Contains(Sums, Sum, SS) then
[SS:= LE;
J:= J+1;
MC(I):= J;
K:= 0;
]
else
[Sums(SS):= Sum;
SS:= SS+1;
K:= K+1;
if K > I then quit;
];
];
];
];
int I;
[MianChowla;
Text(0, "The first 30 terms of the Mian-Chowla sequence are:^m^j");
for I:= 0 to 30-1 do
[IntOut(0, MC(I)); ChOut(0, ^ )];
Text(0, "^m^j^m^jTerms 91 to 100 of the Mian-Chowla sequence are:^m^j");
for I:= 90 to 100-1 do
[IntOut(0, MC(I)); ChOut(0, ^ )];
CrLf(0);
]</syntaxhighlight>
{{out}}
<pre>
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
</pre>
|