Mian-Chowla sequence: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
m (→{{header|Wren}}: Changed to Wren S/H) |
|||
(8 intermediate revisions by 6 users not shown) | |||
Line 67:
{{trans|C++}}
<
L(i) 0 .< ss
I sums[i] == s
Line 104:
print()
print(‘Terms 91 to 100 of the Mian-Chowla sequence are:’)
print_elements(mc[90..])</
{{out}}
Line 118:
{{works with|Ada|Ada|2012}}
<
with Ada.Containers.Hashed_Sets;
Line 177:
Ada.Text_IO.Put(term'Img);
end loop;
end Mian_Chowla_Sequence;</
{{out}}
<pre>Mian Chowla sequence first 30 terms :
Line 187:
=={{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 227:
FOR i FROM 91 TO 100 DO print( ( " ", whole( mc[ i ], 0 ) ) ) OD
END</
{{out}}
<pre>
Line 239:
=={{header|Arturo}}==
<
result: new [1]
sums: new [2]
Line 274:
print "Terms 91 to 100 of the sequence are:"
print slice seq100 90 99</
{{out}}
Line 286:
=={{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 333:
printf( "\n" );
} # BEGIN</
{{out}}
<pre>
Line 345:
===Alternate===
{{trans|Go}}Hopefully the comments help explain the algorithm.
<
#
# determine if a list is empty or not
Line 386:
} # for i
print "\n"
} # BEGIN</
{{out}}
<pre>Mian Chowla sequence elements 1..30:
Line 397:
=={{header|C}}==
{{trans|Go}}
<
#include <stdbool.h>
#include <time.h>
Line 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 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 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 523:
=={{header|C#|CSharp}}==
{{trans|Go}}
<
using System.Collections.Generic;
using System.Diagnostics;
Line 556:
string.Join(" ", mc.Skip(n - 10)), sw.ElapsedMilliseconds);
}
}</
{{out}}
<pre>The first 30 terms of the Mian-Chowla sequence are:
Line 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 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 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 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 643:
</pre>
;91 to 100
<
mC |> Seq.skip 90 |> Seq.take 10 |> Seq.iter(printf "%d ");printfn ""
</syntaxhighlight>
{{out}}
<pre>
Line 652:
=={{header|Factor}}==
<
: next ( seq sums speculative -- seq' sums' speculative' )
Line 667:
[ 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@</
{{out}}
<pre>
Line 678:
=={{header|FreeBASIC}}==
<
redim as uinteger sums(0 to 2)
mian(0) = 1 : mian(1) = 2
Line 712:
print mian(i),
next i
print</
{{out}}
<pre>
Line 722:
=={{header|Go}}==
<
import "fmt"
Line 765:
fmt.Println("\nTerms 91 to 100 of the Mian-Chowla sequence are:")
fmt.Println(mc[90:100])
}</
{{out}}
Line 777:
<br>
Quicker version (runs in less than 0.02 seconds on Celeron N3050 @1.6 GHz), output as before:
<
import "fmt"
Line 818:
fmt.Println("\nTerms 91 to 100 of the Mian-Chowla sequence are:")
fmt.Println(mc[90:100])
}</
=={{header|Haskell}}==
{{Trans|Python}}
{{Trans|JavaScript}}
<
------------------- MIAN-CHOWLA SEQUENCE -----------------
Line 846:
, "Terms 91 to 100 of the Mian-Chowla series:"
, show $ drop 90 (mianChowlas 100)
]</
{{Out}}
<pre>First 30 terms of the Mian-Chowla series:
Line 856:
=={{header|J}}==
<syntaxhighlight lang="j">
NB. http://rosettacode.org/wiki/Mian-Chowla_sequence
Line 874:
prime_q =: 1&p: NB. for fun look at prime generation suitability
</syntaxhighlight>
<pre>
Line 894:
=={{header|Java}}==
<
import java.util.Arrays;
Line 970:
}
</syntaxhighlight>
{{out}}
<pre>
Line 982:
=={{header|JavaScript}}==
{{Trans|Python}} (Functional Python version)
<
'use strict';
Line 1,092:
// MAIN ---
return main();
})();</
{{Out}}
<pre>Mian-Chowla terms 1-30:
Line 1,099:
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 1,138 ⟶ 1,175:
@time testmianchowla()
</
<pre>
...
Line 1,147 ⟶ 1,184:
=={{header|Kotlin}}==
===Translation of Go===
<syntaxhighlight lang="scala">// Version 1.3.21
fun mianChowla(n: Int): List<Int> {
Line 1,183 ⟶ 1,222:
println("\nTerms 91 to 100 of the Mian-Chowla sequence are:")
println(mc.subList(90, 100))
}</
{{output}}
Line 1,192 ⟶ 1,231:
Terms 91 to 100 of the Mian-Chowla sequence are:
[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}}==
<
tmp = {2};
Do[
Line 1,209 ⟶ 1,293:
]
Row[Take[n, 30], ","]
Row[Take[n, {91, 100}], ","]</
{{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
Line 1,215 ⟶ 1,299:
=={{header|Nim}}==
<
proc mianchowla(n: Positive): seq[int] =
Line 1,249 ⟶ 1,333:
echo ""
echo "Computation time: ", (now() - t0).inMilliseconds, " ms"</
{{out}}
Line 1,293 ⟶ 1,377:
real 1932m34,698s => 1d8h12m35</pre>
<
//compiling with /usr/lib/fpc/3.2.0/ppcx64.2 -MDelphi -O4 -al "%f"
{$CODEALIGN proc=8,loop=4 }
Line 1,447 ⟶ 1,531:
writeln;
END.
</syntaxhighlight>
{{Out}}
<pre>Allocated memory 2014024
Line 1,467 ⟶ 1,551:
=={{header|Perl}}==
<
use warnings;
use feature 'say';
Line 1,488 ⟶ 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 1,497 ⟶ 1,581:
=={{header|Phix}}==
<!--<
<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>
Line 1,538 ⟶ 1,622:
<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>
<!--</
{{out}}
<pre>
Line 1,550 ⟶ 1,634:
=={{header|Python}}==
===Procedural===
<
import time
Line 1,579 ⟶ 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,591 ⟶ 1,675:
===Functional===
{{Works with|Python|3.7}}
<
from itertools import (islice)
Line 1,698 ⟶ 1,782:
if __name__ == '__main__':
main()</
{{Out}}
<pre>First 30 terms of the Mian-Chowla series:
Line 1,707 ⟶ 1,791:
(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"
state $index = 1;
state %sums = 2 => 1;
Line 1,724 ⟶ 1,843:
put "First 30 terms in the Mian–Chowla sequence:\n", @mian-chowla[^30];
put "\nTerms 91 through 100:\n", @mian-chowla[90..99];</
{{out}}
<pre>First 30 terms in the Mian–Chowla sequence:
Line 1,738 ⟶ 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.*/
Line 1,758 ⟶ 1,877:
/*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,772 ⟶ 1,891:
=={{header|Ruby}}==
{{trans|Go}}
<
n, ts, mc, sums = 100, [], [1], Set.new
sums << 2
Line 1,796 ⟶ 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,808 ⟶ 1,927:
Or using an Enumerator:
<
mc, sums = [1], {}
1.step do |n|
Line 1,826 ⟶ 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,837 ⟶ 1,956:
for k in (0 .. i) {
var sum = mc[k]+j
if (sums.
ts.clear
break
Line 1,844 ⟶ 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,861 ⟶ 1,980:
22526 23291 23564 23881 24596 24768 25631 26037 26255 27219
Computation time was
=={{header|Swift}}==
Line 1,867 ⟶ 1,986:
{{trans|Go}}
<
var mc = Array(repeating: 0, count: n)
var ls = [2: true]
Line 1,905 ⟶ 2,024:
print("First 30 terms in sequence are: \(Array(seq.prefix(30)))")
print("Terms 91 to 100 are: \(Array(seq[90..<100]))")</
{{out}}
Line 1,913 ⟶ 2,032:
=={{header|VBScript}}==
<
Const m = 100, mm=28000
ReDim r(mm), v(mm * 2)
Line 1,957 ⟶ 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,970 ⟶ 2,089:
'''Shorter execution time'''
{{trans|Go}}
<
Function Find(x(), val) ' finds val on a pre-sorted list
Line 2,012 ⟶ 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 2,025 ⟶ 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 2,051 ⟶ 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 2,063 ⟶ 2,182:
=={{header|Wren}}==
{{trans|C#}}
<
var mc = List.filled(n, 0)
var sums = {}
Line 2,095 ⟶ 2,214:
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")</
{{out}}
Line 2,106 ⟶ 2,225:
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>
|