Rosetta Code

Sisyphus sequence: Difference between revisions

Page Discussion

Sisyphus sequence (view source)

Revision as of 12:17, 6 February 2024

38,602 bytes added ,  3 months ago
m
→‎{{header|Wren}}: Changed to Wren S/H
(Added Raku)
m (→‎{{header|Wren}}: Changed to Wren S/H)
 
(23 intermediate revisions by 13 users not shown)
Line 1:
{{draft task}}
 
The '''Sisyphus sequence''' is an infinite sequence of positive integers that was devised in 2022 by Eric Angelini and Carole Dubois.
Line 196:
Integers in 1..250 that occur most often ( 6 times ) up to element 10000000:
3 57 65 85 114 125 130 170 228
</pre>
 
=={{header|C++}}==
{{libheader|Primesieve}}
<syntaxhighlight lang="cpp">#include <algorithm>
#include <iomanip>
#include <iostream>
 
#include <primesieve.hpp>
 
class sisyphus_iterator {
public:
uint64_t next() {
uint64_t n = next_;
if (next_ % 2 == 0) {
next_ /= 2;
} else {
prime_ = pi_.next_prime();
next_ += prime_;
}
return n;
}
uint64_t prime() const { return prime_; }
 
private:
primesieve::iterator pi_;
uint64_t next_ = 1;
uint64_t prime_ = 0;
};
 
int main() {
std::cout.imbue(std::locale(""));
sisyphus_iterator si;
int found[250] = {};
std::cout << "The first 100 members of the Sisyphus sequence are:\n";
uint64_t count = 1;
const uint64_t limit = 100000000;
for (uint64_t n = 1000; n <= limit; ++count) {
uint64_t next = si.next();
if (next < 250)
++found[next];
if (count <= 100) {
std::cout << std::setw(3) << next << (count % 10 == 0 ? '\n' : ' ');
if (count == 100)
std::cout << '\n';
} else if (count == n) {
std::cout << std::setw(11) << n << "th member is " << std::setw(13)
<< next << " and highest prime needed is "
<< std::setw(11) << si.prime() << '\n';
n *= 10;
}
}
auto f = [&found](int n) {
bool first = true;
for (int i = 1; i < 250; ++i) {
if (found[i] == n) {
if (first)
first = false;
else
std::cout << ", ";
std::cout << i;
}
}
};
std::cout << "\nThese numbers under 250 do not occur in the first " << limit
<< " terms:\n";
f(0);
int max = *std::max_element(std::begin(found), std::end(found));
std::cout << "\n\nThese numbers under 250 occur the most in the first "
<< limit << " terms:\n";
f(max);
std::cout << " all occur " << max << " times.\n\n";
for (;; ++count) {
uint64_t next = si.next();
if (next == 36) {
std::cout << count << "th member is " << 36
<< " and highest prime needed is " << si.prime() << '\n';
break;
}
}
}</syntaxhighlight>
 
{{out}}
<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
 
1,000th member is 990 and highest prime needed is 2,273
10,000th member is 24,975 and highest prime needed is 30,727
100,000th member is 265,781 and highest prime needed is 392,113
1,000,000th member is 8,820,834 and highest prime needed is 4,761,697
10,000,000th member is 41,369,713 and highest prime needed is 55,900,837
100,000,000th member is 1,179,614,168 and highest prime needed is 640,692,323
 
These numbers under 250 do not occur in the first 100,000,000 terms:
36, 72, 97, 107, 115, 127, 144, 167, 194, 211, 214, 230, 232
 
These numbers under 250 occur the most in the first 100,000,000 terms:
7, 14, 28 all occur 7 times.
 
77,534,485,877th member is 36 and highest prime needed is 677,121,348,413
</pre>
 
=={{header|EasyLang}}==
<syntaxhighlight lang="easylang">
func isprim num .
if num mod 2 = 0 and num > 2
return 0
.
i = 3
while i <= sqrt num
if num mod i = 0
return 0
.
i += 2
.
return 1
.
prim = 1
proc nextprim . .
repeat
prim += 1
until isprim prim = 1
.
.
numfmt 0 4
n = 1
write n
for i = 2 to 100
if n mod 2 <> 0
nextprim
n += prim
else
n /= 2
.
write n
if i mod 10 = 0
print ""
.
.
</syntaxhighlight>
 
=={{header|J}}==
Simplistic implementation: <syntaxhighlight lang=J>sisyphuseq=: {{
r=. 1
P=: _1
while. y>#r do. p=. {:P
if. 2|N=. {:r do.
P=: P, p=. 1+p
r=. r,N+p:p
else.
P=: P, p
r=. r,-:N
end.
end.
}}</syntaxhighlight>
 
Task:
 
<syntaxhighlight lang=J> seq=: sisyphuseq 1e6
10 10$seq NB. first 100 members of 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
x:(,. (seq {~ <:),. P p:@{~ <:) 1e3 1e4 1e5 1e6 NB. nth elements of sequence and corresponding largest prime used
1000 990 2273
10000 24975 30713
100000 265781 392111
1000000 8820834 4761697</syntaxhighlight>
 
=={{header|Java}}==
Using a segmented prime iterator enables the extreme stretch task to be completed in approximately 70 minutes without using any external libraries.
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
 
public final class SisyphusSequence {
 
public static void main(String[] args) {
final long limit = 100_000_000;
SisyphusIterator iterator = new SisyphusIterator(1_000_000_000_000L);
System.out.println("The first 100 members of the Sisyphus sequence are:");
int[] found = new int[250];
long next = 0;
long count = 0;
int target = 1_000;
while ( target <= limit ) {
count += 1;
next = iterator.next();
if ( next < 250 ) {
found[(int) next]++;
}
if ( count <= 100 ) {
System.out.print(String.format("%3d%s", next, ( count % 10 == 0 ? "\n" : " ")));
if ( count == 100 ) {
System.out.println();
}
} else if ( count == target ) {
target *= 10;
System.out.println(String.format("%11d%s%11d%s%10d",
target, "th member is ", next, " and highest prime needed is ", iterator.getPrime()));
}
}
display(found, 0, target, "These numbers under 250 occur the most in the first ", "");
final int max = Arrays.stream(found).max().orElseThrow();
display(found, max, target,
"These numbers under 250 occur the most in the first ", "all occur " + max + " times");
while ( next != 36 ) {
count += 1;
next = iterator.next();
}
System.out.println();
System.out.println(count + "th member is " + next + " and highest prime needed is " + iterator.getPrime());
}
private static void display(int[] found, int search, int target, String prefix, String suffix) {
System.out.println();
System.out.println(prefix + target + " terms:");
for ( int i = 1; i < found.length; i++ ) {
if ( found[i] == search ) {
System.out.print(i + " ");
}
}
System.out.println(suffix);
}
 
}
 
final class SisyphusIterator {
public SisyphusIterator(long limit) {
previous = 2;
prime = 0;
primeIterator = new SegmentedPrimeIterator(limit);
}
 
public long next() {
if ( ( previous & 1 ) == 0 ) {
previous >>= 1;
} else {
prime = primeIterator.next();
previous += prime;
}
return previous;
}
public long getPrime() {
return prime;
}
 
private long previous;
private long prime;
private SegmentedPrimeIterator primeIterator;
}
 
final class SegmentedPrimeIterator {
public SegmentedPrimeIterator(long limit) {
squareRoot = (int) Math.sqrt(limit);
high = squareRoot;
smallSieve(squareRoot);
}
public long next() {
if ( index == primes.size() ) {
index = 0;
segmentedSieve();
}
return primes.get(index++);
}
 
private void segmentedSieve() {
low += squareRoot;
high += squareRoot;
 
boolean[] markedPrime = new boolean[squareRoot];
Arrays.fill(markedPrime, true);
for ( int i = 0; i < smallPrimes.size(); i++ ) {
long lowLimit = ( low / smallPrimes.get(i) ) * smallPrimes.get(i);
if ( lowLimit < low ) {
lowLimit += smallPrimes.get(i);
}
for ( long j = lowLimit; j < high; j += smallPrimes.get(i) ) {
markedPrime[(int) ( j - low )] = false;
}
}
primes.clear();
for ( long i = low; i < high; i++ ) {
if ( markedPrime[(int) ( i - low )] ) {
primes.add(i);
}
}
}
private void smallSieve(int squareRoot) {
boolean[] markedPrime = new boolean[squareRoot + 1];
Arrays.fill(markedPrime, true);
for ( int p = 2; p * p <= squareRoot; p++ ) {
if ( markedPrime[p] ) {
for ( int i = p * p; i <= squareRoot; i += p ) {
markedPrime[i] = false;
}
}
}
for ( int p = 2; p <= squareRoot; p++ ) {
if ( markedPrime[p] ) {
primes.add((long) p);
}
}
smallPrimes.addAll(primes);
}
private int index, squareRoot;
private long low, high;
private List<Long> primes = new ArrayList<Long>();
private List<Long> smallPrimes = new ArrayList<Long>();
}
</syntaxhighlight>
{{ out }}
<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 is 2273
10000th member is 24975 and highest prime needed is 30713
100000th member is 265781 and highest prime needed is 392111
1000000th member is 8820834 and highest prime needed is 4761697
10000000th member is 41369713 and highest prime needed is 55900829
100000000th member is 1179614168 and highest prime needed is 640692323
 
These numbers under 250 occur the most in the first 1000000000 terms:
36 72 97 107 115 127 144 167 194 211 214 230 232
 
These numbers under 250 occur the most in the first 1000000000 terms:
7 14 28 all occur 7 times
 
77534485877th member is 36 and highest prime needed is 677121348413
</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|Julia}}==
<syntaxhighlight lang="julia">using Counters, Formatting, Primes
 
struct Sisyphus end
 
function Base.iterate(s::Sisyphus, state = (0, 0))
n, p = state
if n == 0
return (1, 0), (1, 0)
else
if isodd(n)
p = nextprime(p + 1)
n += p
else
n ÷= 2
end
return (n, p), (n, p)
end
end
 
function test_sisyphus()
coun = Counter{Int}()
println("The first 100 members of the Sisyphus sequence are:")
for (i, (n, p)) in enumerate(Sisyphus())
if n < 250
coun[n] += 1
end
if i < 101
print(rpad(n, 4), i % 10 == 0 ? "\n" : "")
elseif i in [1000, 10000, 100_000, 1_000_000, 10_000_000, 100_000_000]
print(
rpad("\n$(format(i, commas = true))th number:", 22),
rpad(format(n, commas = true), 14),
"Highest prime needed: ",
format(p, commas = true),
)
end
if i == 100_000_000
println(
"\n\nThese numbers under 250 do not occur in the first 100,000,000 terms:",
)
println(" ", filter(j -> !haskey(coun, j), 1:249), "\n")
sorteds = sort!([(p, coun[p]) for p in coun], by = last)
maxtimes = sorteds[end][2]
println(
"These numbers under 250 occur the most ($maxtimes times) in the first 100,000,000 terms:",
)
println(" ", map(first, filter(p -> p[2] == maxtimes, sorteds)))
elseif n == 36
println("\nLocating the first entry in the sequence with value 36:")
println(
" The sequence position: ",
format(i, commas = true),
" has value $n using prime ",
format(p, commas = true),
)
break
end
end
end
 
test_sisyphus()
</syntaxhighlight>{{out}}
<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
 
1,000th number: 990 Highest prime needed: 2,273
10,000th number: 24,975 Highest prime needed: 30,713
100,000th number: 265,781 Highest prime needed: 392,111
1,000,000th number: 8,820,834 Highest prime needed: 4,761,697
10,000,000th number: 41,369,713 Highest prime needed: 55,900,829
100,000,000th number: 1,179,614,168 Highest prime needed: 640,692,323
 
These numbers under 250 do not occur in the first 100,000,000 terms:
[36, 72, 97, 107, 115, 127, 144, 167, 194, 211, 214, 230, 232]
 
These numbers under 250 occur the most (7 times) in the first 100,000,000 terms:
[28, 7, 14]
 
Locating the first entry in the sequence with value 36:
The sequence position: 77,534,485,877 has value 36 using prime 677,121,348,413
</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|Pascal}}==
==={{header|Free Pascal}}===
<syntaxhighlight lang="pascal">
program Sisyphus;
{$IFDEF FPC}
{$MODE DELPHI}{$Coperators ON}{$Optimization ON}
{$ENDIF}
{$IFDEF WINDOWS}
{$APPTYPE CONSOLE}
{$ENDIF}
uses
sysutils,
primsieve;// https://rosettacode.org/wiki/Extensible_prime_generator#Pascal
 
function CommatizeUint64(num:Uint64):AnsiString;
var
fromIdx,toIdx :Int32;
Begin
str(num,result);
fromIdx := length(result);
toIdx := fromIdx-1;
if toIdx < 3 then
exit;
 
toIdx := 4*(toIdx DIV 3)+toIdx MOD 3 +1 ;
setlength(result,toIdx);
repeat
result[toIdx] := result[FromIdx];
result[toIdx-1] := result[FromIdx-1];
result[toIdx-2] := result[FromIdx-2];
result[toIdx-3] := ',';
dec(toIdx,4);
dec(FromIdx,3);
until FromIdx<=3;
end;
 
procedure OutOne(n,count: Uint64);
Begin
write(n:5);
If count mod 10 = 0 then
writeln;
end;
 
procedure OutRes(n,count,p:Uint64);
Begin
writeln(CommatizeUint64(n):15, ' found after ',CommatizeUint64(count):12,' iterations: Max prime ',CommatizeUint64(p):12);
end;
 
procedure CheckSmall;
var
CntOccurence : array[0..255] of byte;
n,count,p,limit : Uint64;
begin
InitPrime;
writeln('The first 100 members of the Sisyphus sequence');
fillchar(CntOccurence,SizeOf(CntOccurence),#0);
n := 1;
count := 1;
Limit := 1000;
CntOccurence[n] := 1;
 
repeat
if count <= 100 then
Begin
OutOne(n,count);
if count = 100 then
writeln;
end;
 
if n AND 1 = 0 then
n := n shr 1
else
begin
p := nextprime;
n += p;
end;
count+= 1;
iF n < 255 then
inc(CntOccurence[n]);
 
if (count = Limit) then
Begin
OutRes(n,count,p);
Limit *= 10;
end;
until Limit > 100*1000*1000;
 
writeln(#10,'Not found numbers below 250 after ',CommatizeUint64(count),' iterations');
p := 0;// maximum
For n := 1 to 250 do
begin
if CntOccurence[n] = 0 then
write(n:4);
if p < CntOccurence[n] then
p := CntOccurence[n];
end;
Writeln;
 
writeln(#10,'Mostly found numbers below 250 after ',CommatizeUint64(count),' iterations');
For n := 1 to 250 do
if CntOccurence[n] = p then
write(n:4);
Writeln(' found ',p,' times');
end;
 
procedure Check;
var
n,count,target,p : Uint64;
begin
InitPrime;
n := 1;
count := 1;
Target := 36;
repeat
if n AND 1 = 0 then
n := n shr 1
else
begin
p := nextprime;
n += p;
end;
count+= 1;
if (n = target) then
Begin
OutRes(n,count,p);
BREAK;
end;
until false;
end;
 
BEGIN
CheckSmall;
writeln;
CHECK;
end.</syntaxhighlight>
{{out|@Home Ryzen 5600G 3.6 Ghz }}
<pre>
The first 100 members 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
 
990 found after 1,000 iterations: Max prime 2,273
24,975 found after 10,000 iterations: Max prime 30,713
265,781 found after 100,000 iterations: Max prime 392,111
8,820,834 found after 1,000,000 iterations: Max prime 4,761,697
41,369,713 found after 10,000,000 iterations: Max prime 55,900,829
1,179,614,168 found after 100,000,000 iterations: Max prime 640,692,323
 
Not found numbers below 250 after 100,000,000 iterations
36 72 97 107 115 127 144 167 194 211 214 230 232
 
Mostly found numbers below 250 after 100,000,000 iterations
7 14 28 found 7 times
--0.63 s
36 found after 77,534,485,877 iterations: Max prime 677,121,348,413
 
real 16m20.573s
</pre>
 
=={{header|Perl}}==
{{libheader|ntheory}}
<syntaxhighlight lang="perl" line>
use strict;
use warnings;
use feature 'say';
 
use ntheory 'next_prime';
use List::Util <any max>;
use integer;
 
sub comma { reverse ((reverse shift) =~ s/.{3}\K/,/gr) =~ s/^,//r }
sub table { my $t = 10 * (my $c = 1 + length max @_); ( sprintf( ('%'.$c.'d')x@_, @_) ) =~ s/.{1,$t}\K/\n/gr }
 
my ($exp1, $exp2, $limit1, $limit2) = (3, 8, 100, 250);
my ($n, $s0, $s1, $p, @S1, %S, %S2) = (1, 1, 0, 1, 1);
my @Nth = map { 10**$_ } $exp1..$exp2;
 
do {
$n++;
$s1 = (0 == $s0%2) ? $s0/2 : $s0 + ($p = next_prime($p));
push @S1, $s1 if $n <= $limit1;
$S2{$s1}++ if $s1 <= $limit2;
($S{$n}{'value'} = $s1 and $S{$n}{'prime'} = $p) if any { $_ == $n } @Nth;
$s0 = $s1;
} until $n == $Nth[-1];
 
say 'The first 100 members of the Sisyphus sequence are:';
say table @S1;
 
printf "%12sth member is: %13s with prime: %11s\n", comma($_), comma($S{$_}{value}), comma($S{$_}{prime}) for @Nth;
 
printf "\nNumbers under $limit2 that do not occur in the first %s terms:\n", comma $Nth[-1];
say join ' ', grep { ! defined $S2{$_} } 1..$limit2;
 
my $max = max values %S2;
printf "\nNumbers under $limit2 occur the most ($max times) in the first %s terms:\n", comma $Nth[-1];
say join ' ', sort { $a <=> $b } grep { $S2{$_} == $max } keys %S2;
</syntaxhighlight>
{{out}}
<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
 
1,000th member is: 990 with prime: 2,273
10,000th member is: 24,975 with prime: 30,713
100,000th member is: 265,781 with prime: 392,111
1,000,000th member is: 8,820,834 with prime: 4,761,697
10,000,000th member is: 41,369,713 with prime: 55,900,829
100,000,000th member is: 1,179,614,168 with prime: 640,692,323
 
Numbers under 250 that do not occur in the first 100,000,000 terms:
36 72 97 107 115 127 144 167 194 211 214 230 232
 
Numbers under 250 occur the most (7 times) in the first 100,000,000 terms:
7 14 28
</pre>
 
Line 262 ⟶ 1,196:
"12.8s"
</pre>
=== Extreme stretch (just a note about)===
{{trans|Python}}
Knowing that s(77,534,485,877)=36, a crude extrapolation of the above figures suggests it would
I found a suitable prebuilt 64-bit windows dll in the pascal bindings of primesieve (version 7.7, dated 31/12/21), so gave it a try:
need primes up to 570 billion, or about 30 billion of them, or at least 480GB of RAM, which is a
<!--<syntaxhighlight lang="phix">(notonline)-->
tad more than I have available on this machine... If, on the other hand, I could figure out how to
<span style="color: #008080;">without</span> <span style="color: #008080;">js</span>
not need quite so much ram (I believe the theoretical minimum to be 36GB), it ''might'' be achievable
<span style="color: #008080;">include</span> <span style="color: #000000;">builtins</span><span style="color: #0000FF;">/</span><span style="color: #000000;">primesieve</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> <span style="color: #000080;font-style:italic;">-- (can provide if desired, ask me on either my or this tasks talk page)</span>
in as little as between 4 and 28 hours...
<span style="color: #7060A8;">requires</span><span style="color: #0000FF;">(</span><span style="color: #004600;">WINDOWS</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">requires</span><span style="color: #0000FF;">(</span><span style="color: #000000;">64</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">(),</span> <span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">1</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">np</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">p</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">next</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">next</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">36</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">even</span><span style="color: #0000FF;">(</span><span style="color: #000000;">next</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">next</span> <span style="color: #0000FF;">/=</span> <span style="color: #000000;">2</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">primesieve_next_prime</span><span style="color: #0000FF;">()</span>
<span style="color: #000000;">next</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">p</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()></span><span style="color: #000000;">t1</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">cpc</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">count</span><span style="color: #0000FF;">/</span><span style="color: #000000;">77_534_485_877</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">100</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">ppc</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">/</span><span style="color: #000000;">677_121_348_413</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">100</span>
<span style="color: #7060A8;">progress</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"count: %,d (%2.2f%%) p: %,d (%2.2f%%)\r"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">count</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cpc</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ppc</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #7060A8;">progress</span><span style="color: #0000FF;">(</span><span style="color: #008000;">""</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;">"%,d%s member is: %,d and highest prime needed: %,d\n"</span><span style="color: #0000FF;">,</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">count</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">ord</span><span style="color: #0000FF;">(</span><span style="color: #000000;">count</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">next</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">})</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>
<!--</syntaxhighlight>-->
{{out}}
<pre>
77,534,485,877th member is: 36 and highest prime needed: 677,121,348,413
"1 hour, 53 minutes and 46s"
</pre>
Timings on an i3-2120 3.3GHz dual core. Memory use was just 9MB, about 0.1% of what I have.
 
=={{header|Python}}==
Line 372 ⟶ 1,337:
These numbers under 250 occur the most in the first 100,000,000 terms:
[28, 14, 7] all occur 7 times.
</pre>
 
===Extreme stretch===
 
Using Python bindings for the primesieve C++ library and PyPy 3.9 instead of CPython (PyPy is nearly twice as fast up to s(100,000,000)), this completed in about 1 hour and 53 minutes on a AMD Ryzen 5 1500X. Memory usage was minimal thanks to <code>primesieve.Iterator()</code>.
 
<syntaxhighlight lang="python">import primesieve
 
def sisyphus36():
primes = primesieve.Iterator()
n = 1
p = 0
i = 1
 
while True:
i += 1
if n % 2:
p = primes.next_prime()
n = n + p
else:
n = n // 2
 
if n == 36:
print(f"{i:,}, {n:,}, {p:,}")
break
 
if __name__ == "__main__":
sisyphus36()
</syntaxhighlight>
 
{{out}}
<pre>
$ time pypy3.9 sisyphus_36.py
77,534,485,877, 36, 677,121,348,413
 
real 113m2.636s
user 112m56.973s
sys 0m0.060s
</pre>
 
Line 388 ⟶ 1,391:
$n++;
$s1 = $s0 %% 2 ?? $s0 div 2 !! $s0 + ($p = $iterator.next);
push @S1,.push: $s1 if $n ≤ $limit1;
$S2.add(: $s1) if $s1 ≤ $limit2;
%S{$n}{'value', 'prime'} = $s1, $p if $n ∈ @Nth;
$s0 = $s1;
Line 395 ⟶ 1,398:
 
say "The first $limit1 members of the Sisyphus sequence are:";
say @S1.batch(10)».fmt('%4d').join("\n") ~ "\n";
printf "%12sth member is: %13s with prime: %11s\n", ($_, %S{$_}{'value'}, %S{$_}{'prime'})».&comma for @Nth;
say '';
say sprintf "%12sth member is: %13s with prime: %11s", ($_, %S{$_}{'value'}, %S{$_}{'prime'})».&comma for @Nth;
say "\nNumbers under $limit2 that do not occur in the first {comma @Nth[*-1]} terms:";
say (1..$limit2).grep: * ∉ $S2.keys;
Line 453 ⟶ 1,455:
2: (990.,2273.)
1: (24975.,30713.)
</pre>
 
=={{header|Ruby}}==
<syntaxhighlight lang="ruby">require 'prime'
 
prime_gen = Prime.each
cur_prime = nil
sisyphi = Enumerator.produce(1) {|n| n.even? ? n/2 : n += (cur_prime = prime_gen.next)}
 
sisyphi.first(100).each_slice(10){|s| puts "%4d"*s.size % s }
 
puts
prime_gen.rewind
counter = Hash.new(0)
count_until = 250
idx = 1000
limit = 100_000_000
sisyphi.with_index(1) do |n, i|
counter[n] += 1 if n < count_until
if i == idx then
puts "element %11d is %11d, with prime %11d" % [i, n, cur_prime]
break if idx >= limit
idx *= 10
end
end
 
puts "\nThese numbers under #{count_until} do not occur in the first #{limit} terms:"
puts ((1...count_until).to_a - counter.keys).join ", "
 
freq, nums = counter.group_by{|k, v| v}.max
puts "\nThese numbers under #{count_until} occur most frequent (#{freq} times) in the first #{limit} terms:"
puts nums.map(&:first).sort.join(", ")</syntaxhighlight>
{{out}}
<pre> 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
 
element 1000 is 990, with prime 2273
element 10000 is 24975, with prime 30713
element 100000 is 265781, with prime 392111
element 1000000 is 8820834, with prime 4761697
element 10000000 is 41369713, with prime 55900829
element 100000000 is 1179614168, with prime 640692323
 
These numbers under 250 do not occur in the first 100000000 terms:
36, 72, 97, 107, 115, 127, 144, 167, 194, 211, 214, 230, 232
 
These numbers under 250 occur most frequent (7 times) in the first 100000000 terms:
7, 14, 28
</pre>
 
Line 460 ⟶ 1,518:
No option here but to use a sieve as relying on the 'nextPrime' method would be far too slow to achieve the stretch goal in a reasonable time using Wren. Sieve limit found by experimentation.
 
Extreme stretch not attempted and probably out of thereasonable questionreach for Wren-CLI.
<syntaxhighlight lang="ecmascriptwren">import "./math" for Int, Nums
import "./fmt" for Fmt
 
Line 532 ⟶ 1,590:
These numbers under 250 occur the most in the first 100,000,000 terms:
[7, 14, 28] all occur 7 times.
</pre>
 
===Extreme Stretch===
{{libheader|Wren-psieve}}
The above module provides Wren bindings for the very fast C++ library ''primesieve'', used by several other languages for this task, though we need to use a special executable (written in C) to run it at the present time - it cannot be run under Wren-CLI.
 
The following script manages to find the first occurrence of the number 36 in the sequence in about 2 hours 54 minutes which (relative to Phix) is much quicker than one would normally expect. This is probably due to the heavy lifting (i.e. the prime generation) being done here in both cases by C++ though this will tempered by the need to convert unsigned 64-bit integers to doubles (Wren's only numeric type) for each prime generated.
<syntaxhighlight lang="wren">import "./psieve" for Primes
import "./fmt" for Fmt
 
var it = Primes.iter()
var n = 1
var count = 1
var prime
var target = 36
while (true) {
if (n % 2 == 1) {
prime = it.next
n = n + prime
} else {
n = n / 2
}
count = count + 1
if (n == target) {
Fmt.print("$,r member is: $d and highest prime needed: $,d", count, target, prime)
return
}
}</syntaxhighlight>
 
{{out}}
<pre>
77,534,485,877th member is: 36 and highest prime needed: 677,121,348,413
</pre>
PureFox
9,476

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/344618...358639"