Sisyphus sequence: Difference between revisions
Created Nim solution.
(→{{header|Wren}}: Added extreme stretch goal.) |
(Created Nim solution.) |
||
Line 311:
</pre>
=={{header|Nim}}==
Only task and stretch task. The program runs in 4.7 seconds.
<syntaxhighlight lang="Nim">import std/[bitops, math, strformat, strutils, tables]
# Sieve which uses only one bit for odd integers.
type Sieve = object
data: seq[byte]
func `[]`(sieve: Sieve; idx: Positive): bool =
## Return value of element at index "idx".
let idx = idx shr 1
let iByte = idx shr 3
let iBit = idx and 7
result = sieve.data[iByte].testBit(iBit)
func `[]=`(sieve: var Sieve; idx: Positive; val: bool) =
## Set value of element at index "idx".
let idx = idx shr 1
let iByte = idx shr 3
let iBit = idx and 7
if val: sieve.data[iByte].setBit(iBit)
else: sieve.data[iByte].clearBit(iBit)
func initSieve(lim: Positive): Sieve =
## Initialize a sieve from 2 to "lim".
result.data = newSeq[byte]((lim + 16) shr 4)
result[1] = true
for n in countup(3, sqrt(lim.toFloat).int, 2):
if not result[n]:
for k in countup(n * n, lim, 2 * n):
result[k] = true
func isPrime(sieve: Sieve; n: int): bool =
## Return true if "n" is prime.
result = if (n and 1) == 0: n == 2 else: not sieve[n]
let sieve = initSieve(700_000_000)
func nextPrime(sieve: Sieve; n: int): int =
## Return next prime greater than "n".
result = n
while true:
inc result
if sieve.isPrime(result):
return
var p = 0 # Current prime (none for now).
var count = 0 # Count of elements in sequence.
var n = 1 # Last element of sequence.
var counts: CountTable[int] # Count of occurrences for value < 250.
echo "First 100 terms of the Sisyphus sequence:"
while count < 100_000_000:
# Process current number.
inc count
if count <= 100:
stdout.write &"{n:3}"
stdout.write if count mod 10 == 0: '\n' else: ' '
if count == 100: echo()
elif count in [1_000, 10_000, 100_000, 1_000_000, 10_000_000, 100_000_000]:
echo &"The {insertSep($count)}th term is {insertSep($n)} " &
&"and the highest prime needed is {insertSep($p)}."
# Update count table.
if n < 250: counts.inc(n)
# Find next term of the sequence.
if (n and 1) == 0:
n = n shr 1
else:
p = sieve.nextPrime(p)
inc n, p
echo()
echo "Numbers under 250 which don’t occur in the first 100_000_000 terms:"
for n in 1..249:
if n notin counts:
stdout.write " ", n
echo '\n'
echo "Numbers under 250 which occur the most in the first 100_000_000 terms:"
counts.sort()
let largest = counts.largest[1]
for (n, count) in counts.pairs:
if count == largest:
stdout.write " ", n
else:
# No more value with the largest number of occurrences.
echo()
break
</syntaxhighlight>
{{out}}
<pre>First 100 terms of the Sisyphus sequence:
1 3 6 3 8 4 2 1 8 4
2 1 12 6 3 16 8 4 2 1
18 9 28 14 7 30 15 44 22 11
42 21 58 29 70 35 78 39 86 43
96 48 24 12 6 3 62 31 92 46
23 90 45 116 58 29 102 51 130 65
148 74 37 126 63 160 80 40 20 10
5 106 53 156 78 39 146 73 182 91
204 102 51 178 89 220 110 55 192 96
48 24 12 6 3 142 71 220 110 55
The 1_000th term is 990 and the highest prime needed is 2_273.
The 10_000th term is 24_975 and the highest prime needed is 30_713.
The 100_000th term is 265_781 and the highest prime needed is 392_111.
The 1_000_000th term is 8_820_834 and the highest prime needed is 4_761_697.
The 10_000_000th term is 41_369_713 and the highest prime needed is 55_900_829.
The 100_000_000th term is 1_179_614_168 and the highest prime needed is 640_692_323.
Numbers under 250 which don’t occur in the first 100_000_000 terms:
36 72 97 107 115 127 144 167 194 211 214 230 232
Numbers under 250 which occur the most in the first 100_000_000 terms:
7 28 14
</pre>
=={{header|Perl}}==
| |||