Mian-Chowla sequence: Difference between revisions
→Sieve version: typos
(→Sieve version: typos) |
|||
| (7 intermediate revisions by 3 users not shown) | |||
Line 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,949 ⟶ 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,956 ⟶ 2,021:
for k in (0 .. i) {
var sum = mc[k]+j
if (sums.
ts.clear
break
Line 1,963 ⟶ 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,980 ⟶ 2,045:
22526 23291 23564 23881 24596 24768 25631 26037 26255 27219
Computation time was
=={{header|Swift}}==
Line 2,182 ⟶ 2,247:
=={{header|Wren}}==
{{trans|C#}}
<syntaxhighlight lang="
var mc = List.filled(n, 0)
var sums = {}
| |||