Mian-Chowla sequence: Difference between revisions
→Sieve version: typos
(Added XPL0 example.) |
(→Sieve version: typos) |
||
| (10 intermediate revisions by 4 users not shown) | |||
Line 1,184:
=={{header|Kotlin}}==
===Translation of Go===
<syntaxhighlight lang="scala">// Version 1.3.21
Line 1,229 ⟶ 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>
Line 1,840 ⟶ 1,887:
The Mian─Chowla sequence for terms 91 ──► 100 (inclusive):
22526 23291 23564 23881 24596 24768 25631 26037 26255 27219
</pre>
=={{header|RPL}}==
{{works with|RPL|HP48-R}}
« { 2 } → n sums
« { 1 }
'''WHILE''' DUP SIZE n < '''REPEAT'''
DUP DUP SIZE GET
1 CF
'''DO''' 1 +
DUP2 ADD DUP sums + SORT ΔLIST
'''IF''' 0 POS '''THEN''' DROP '''ELSE''' 1 SF '''END'''
'''UNTIL''' 1 FS? '''END'''
OVER DUP + + 'sums' STO+ +
'''END'''
» » '<span style="color:blue">A5282</span>' STO
30 <span style="color:blue">A5282</span>
{{out}}
<pre>
1: { 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 }
</pre>
===Sieve version===
This approach is 25 times faster and uses less memory, thanks to a dynamic sieve.
« 39 DUP STWS / CEIL
« # 0b » 'x' 1 4 ROLL 1 SEQ
» '<span style="color:blue">CSV</span>' STO <span style="color:grey">''@ ( size → { sieve } )''</span>
« '''IF''' DUP2 EVAL SIZE 39 * > '''THEN'''
DUP2 EVAL SIZE SWAP 39 / CEIL 1 - '''START''' DUP #0 STO+ '''NEXT'''
'''END'''
SWAP 1 - 39 MOD LASTARG / IP 1 +
ROT SWAP DUP2 GET 2 5 ROLL ^ R→B OR PUT
» '<span style="color:blue">SSV</span>' STO <span style="color:grey">''@ ( val 'sieve' → )''</span>
« '''IF''' DUP2 EVAL SIZE 39 * > '''THEN''' DROP2 0 '''ELSE'''
SWAP 1 - 39 MOD LASTARG / IP 1 +
ROT SWAP GET 2 ROT ^ R→B AND # 0b ≠
'''END'''
» '<span style="color:blue">SVS?</span>' STO <span style="color:grey">''@ ( val 'sieve' → boolean )''</span>
« 500 <span style="color:blue">CSV</span> 'Sums' STO { 1 }
'''WHILE''' DUP2 SIZE > '''REPEAT'''
DUP DUP SIZE GET
DUP 2 * 'Sums' <span style="color:blue">SSV</span>
'''DO''' 1 +
1 SF
DUP2 ADD
1 OVER SIZE '''FOR''' j
'''IF''' DUP j GET 'Sums' <span style="color:blue">SVS?</span> '''THEN''' 1 CF SIZE 'j' STO '''END'''
'''NEXT'''
'''UNTIL''' 1 FS? '''END'''
1
1 3 PICK SIZE '''START''' GETI 'Sums' <span style="color:blue">SSV</span> '''NEXT'''
DROP2 +
'''END'''
SWAP DROP 'Sums' PURGE
» '<span style="color:blue">A5282</span>' STO
100 <span style="color:blue">A5282</span>
DUP 1 30 SUB SWAP 91 100 SUB
{{out}}
<pre>
2: { 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 }
1: { 22526 23291 23564 23881 24596 24768 25631 26037 26255 27219 }
</pre>
Line 1,902 ⟶ 2,014:
=={{header|Sidef}}==
{{trans|Go}}
<syntaxhighlight lang="ruby">var (n, sums, ts, mc) = (100, Set(
var st = Time.
for i in (1 ..^ n) {
for j in (mc[i-1]+1 .. Inf) {
Line 1,909 ⟶ 2,021:
for k in (0 .. i) {
var sum = mc[k]+j
if (sums.
ts.clear
break
Line 1,916 ⟶ 2,028:
}
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."</syntaxhighlight>
{{out}}
Line 1,933 ⟶ 2,045:
22526 23291 23564 23881 24596 24768 25631 26037 26255 27219
Computation time was
=={{header|Swift}}==
Line 2,135 ⟶ 2,247:
=={{header|Wren}}==
{{trans|C#}}
<syntaxhighlight lang="
var mc = List.filled(n, 0)
var sums = {}
| |||