Sisyphus sequence: Difference between revisions
→{{header|jq}}
Line 197:
3 57 65 85 114 125 130 170 228
</pre>
=={{header|jq}}==
'''Adapted from [[#Wren|Wren]]'''
{{works with|jq}}
The following program follows the Wren entry in using a prime sieve, but the primeSieve function is quite slow for large sieves. Since calling task(N) with N equal to 1e7 is sufficient to achieve the primary tasks, larger values of N have not been tried.
The following program also works with gojq, the Go implementation of jq,
but the memory requirements become increasingly extravagent as the sieve
size increases. For example, the "peak memory footprint" for task(1e4) was
approximately 1.66 GB on one machine.
'''Generic Functions'''
<syntaxhighlight lang="jq">
# The def of _nwise can be omitted if using the C implementation of jq.
def _nwise($n):
def n: if length <= $n then . else .[0:$n] , (.[$n:] | n) end;
n;
def lpad($len): tostring | ($len - length) as $l | (" " * $l) + .;
# tabular print
def tprint(columns; wide):
reduce _nwise(columns) as $row ("";
. + ($row|map(lpad(wide)) | join(" ")) + "\n" );
# Input: a positive integer
# Output: an array, $a, of length .+1 such that
# $a[$i] is $i if $i is prime, and false otherwise.
def primeSieve:
# erase(i) sets .[i*j] to false for integral j > 1
def erase($i):
if .[$i] then
reduce (range(2*$i; length; $i)) as $j (.; .[$j] = false)
else .
end;
(. + 1) as $n
| (($n|sqrt) / 2) as $s
| [null, null, range(2; $n)]
| reduce (2, 1 + (2 * range(1; $s))) as $i (.; erase($i)) ;
</syntaxhighlight>
'''The task'''
<syntaxhighlight lang="jq">
# $limit is the target number of Sisyphus numbers to find and should be at least 100
def task($limit):
((7 * $limit) | primeSieve | map(select(.))) as $primes
| { under250: [0, 1],
sisyphus: [1],
prev: 1,
nextPrimeIndex: 0,
specific: 1000,
count:1 }
| while(.count <= $limit;
.emit = null
| if .prev % 2 == 0 then .next = .prev/2
else .next = .prev + $primes[.nextPrimeIndex]
| .nextPrimeIndex += 1
end
| .count += 1
| if .count <= 100 then .sisyphus += [.next] else . end
| if .next < 250 then .under250[.next] += 1 else . end
| if .count == 100
then .emit = "The first 100 members of the Sisyphus sequence are:\n" + (.sisyphus | tprint(10;3))
elif .count == .specific
then $primes[.nextPrimeIndex-1] as $prime
| .emit = "\(.count|lpad(8))th member is: \(.next|lpad(10)) and highest prime needed: \($prime|lpad(10))"
| .specific *= 10
else .
end
| .prev = .next )
# The results:
| select(.emit).emit,
if .count == $limit
then .under250 as $u
| [range(1;250) | select( $u[.] == null)] as $notFound
| ($u|max) as $max
| [range(1;250) | select($u[.] == $max)] as $maxFound
| "\nThese numbers under 250 do not occur in the first \(.count) terms:",
" \($notFound)",
"\nThese numbers under 250 occur the most in the first \(.count) terms:",
" \($maxFound) all occur \($max) times."
else empty
end;
task(1e7)
</syntaxhighlight>
{{output}}
<pre>
The first 100 members of the Sisyphus sequence are:
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
1000th member is: 990 and highest prime needed: 2273
10000th member is: 24975 and highest prime needed: 30713
100000th member is: 265781 and highest prime needed: 392111
1000000th member is: 8820834 and highest prime needed: 4761697
10000000th member is: 41369713 and highest prime needed: 55900829
These numbers under 250 do not occur in the first 10000000 terms:
[36,72,97,107,115,127,144,167,194,211,214,223,230,232]
These numbers under 250 occur the most in the first 10000000 terms:
[3,57,65,85,114,125,130,170,228] all occur 6 times.
</pre>
=={{header|Perl}}==
| |||