Mian-Chowla sequence: Difference between revisions
m (→{{header|VBScript}}: performance enhancement for faster version) |
m (→Shorter execution time: unscrewed header) |
||
| Line 931: | Line 931: | ||
Execution time: 40 min |
Execution time: 40 min |
||
'''Shorter execution time''' |
|||
{{trans|Go}} |
{{trans|Go}} |
||
<lang vb>' Mian-Chowla sequence - VBScript - March 19th, 2019 |
<lang vb>' Mian-Chowla sequence - VBScript - March 19th, 2019 |
||
Revision as of 00:13, 20 March 2019
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:
- 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
ALGOL 68
Based on the AWK sample.
<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;
INT mc count := 0;
[ max mc ]INT mc;
INT curr size := 10 000; # initial sizes of the arrays #
INT size increment = curr size; # size to increase the arrays by #
REF[]INT sum count := HEAP[ curr size ]INT;
REF[]BOOL is mc := HEAP[ curr size ]BOOL;
FOR i TO curr size DO sum count[ i ] := 0; is mc[ i ] := FALSE OD;
FOR i WHILE mc count < max mc DO
# assume i will be part of the sequence #
BOOL is unique := TRUE;
mc count +:= 1;
mc[ mc count ] := i;
is mc[ i ] := TRUE;
# check the sums #
FOR j TO i WHILE is unique DO
IF is mc[ j ] THEN
# have a sequence element #
INT sumij = i + j;
IF sumij > curr size THEN
# the sum count and is mc arrays are too small - make them larger #
REF[]BOOL new is mc = HEAP[ curr size + size increment ]BOOL;
REF[]INT new count = HEAP[ curr size + size increment ]INT;
FOR i TO curr size DO
new is mc[ i ] := is mc [ i ];
new count[ i ] := sum count[ i ]
OD;
FOR i TO size increment DO
new is mc[ curr size + i ] := FALSE;
new count[ curr size + i ] := 0
OD;
curr size +:= size increment;
is mc := new is mc;
sum count := new count
FI;
sum count[ sumij ] +:= 1;
is unique := sum count[ sumij ] < 2;
IF NOT is unique THEN
# the sum is not unique - remove it from the sequence #
FOR k TO j DO IF is mc[ k ] THEN sum count[ i + k ] -:= 1 FI OD;
mc[ mc count ] := 0;
is mc[ i ] := FALSE;
mc count -:= 1
FI
FI
OD
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 2.75 seconds.
AWK
<lang awk># 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 \ {
FALSE = 0; TRUE = 1;
mcCount = 0;
for( i = 1; mcCount < 100; i ++ )
{
# assume i will be part of the sequence
isUnique = TRUE;
mcCount ++;
mc[ mcCount ] = i;
isMc[ i ] = TRUE;
# check the sums
for( j = 1; j <= i && isUnique; j ++ )
{
if( j in isMc )
{
sumIJ = i + j;
sumCount[ sumIJ ] += 1;
isUnique = sumCount[ sumIJ ] < 2;
if( ! isUnique )
{
# the sum is not unique - remove it from the sequence
for( k = j; k > 0; k -- )
{
if( k in isMc )
{
sumCount[ i + k ] -= 1;
} # if k in isMc
} # for k
delete mc[ mcCount ];
delete isMc[ i ];
mcCount --;
} # if isUnique
} # if j in isMc
} # for j
} # 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 2.85 seconds.
C
<lang C>#include <stdio.h>
- include <stdbool.h>
- include <time.h>
- define n 100
- 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.
C#
<lang csharp>using System; using System.Linq; using System.Collections.Generic;
static class Program {
static int[] MianChowla(int n) {
int[] mc = new int[n];
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++) {
ts.Clear(); 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)) {
sums.ExceptWith(ts); goto nxtJ;
}
sums.Add(sum); ts.Add(sum);
}
break;
nxtJ: ;
}
}
return mc;
}
static void Main(string[] args)
{
string str = " terms of the Mian-Chowla sequence are:\n";
DateTime st = DateTime.Now; int[] mc = MianChowla(100);
double et = (DateTime.Now - st).TotalSeconds;
Console.Write("The first 30{1}{2}{0}{0}Terms 91 to 100{1}{3}{0}{0}" +
"Computation time was {4} seconds.", '\n', str,
string.Join(" ", mc.Take(30)), string.Join(" ", mc.Skip(90)), 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 terms of the Mian-Chowla sequence are: 22526 23291 23564 23881 24596 24768 25631 26037 26255 27219 Computation time was 0.4796447 seconds.
C++
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;
- include <iostream>
- include <ctime>
- define n 100
- 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.
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 about 0.03 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] {
for _, x := range isx {
delete(is, x)
}
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
(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)
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
Procedural
<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]
Composition of pure functions
This turns out to execute a little faster than the procedural version above.
(About 8X faster by a simple time.time() start and end measure)
<lang python>"""Mian-Chowla series"""
from itertools import (islice)
- 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]
- 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(qds):
Predicate: only new sums created ?
ds = qds[1]
return all(d not in setSums for d in ds)
# nxt :: (Int, [Int]) -> (Int, [Int])
def nxt(qds):
Next integer, and the additional sums it would introduce.
d = 1 + qds[0]
return (d, [2 * d] + [d + x for x in xs])
q, ds = until(p)(nxt)(nxt((n, [])))
setSums.update(ds)
return (setSums, q)
return lambda preds: lambda n: go(preds, n)
- TEST ----------------------------------------------------
- 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'
)
- GENERIC -------------------------------------------------
- drop :: Int -> [a] -> [a]
- 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)
- take :: Int -> [a] -> [a]
- 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))
)
- 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.206s] (Executed in Atom editor, using Run Script)
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 1st 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.*/
- = 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
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
<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
<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 : ts.Clear()
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 sums.ExceptWith(ts) : GoTo nxtJ
sums.Add(sum) : ts.Add(sum)
Next : Exit For
nxtJ: Next : Next : Return mc
End Function
Sub Main(ByVal args As String())
Dim str As String = " terms of the Mian-Chowla sequence are:" & vbLf,
st As DateTime = DateTime.Now, mc As Integer() = MianChowla(100),
et As Double = (DateTime.Now - st).TotalSeconds
Console.Write("The first 30{1}{2}{0}{0}Terms 91 to 100{1}{3}{0}{0}" & _
"Computation time was {4} seconds.", vbLf, str,
String.Join(" ", mc.Take(30)), String.Join(" ", mc.Skip(90)), et)
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 terms of the Mian-Chowla sequence are: 22526 23291 23564 23881 24596 24768 25631 26037 26255 27219 Computation time was 0.4687451 seconds.