Sisyphus sequence: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
m (→{{header|Wren}}: Changed to Wren S/H) |
|||
| (8 intermediate revisions by 5 users not shown) | |||
Line 197:
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}}==
Line 232 ⟶ 381:
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}}==
Line 557 ⟶ 896:
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>
Line 976 ⟶ 1,482:
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
Line 1,001 ⟶ 1,507:
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:
Line 1,013 ⟶ 1,519:
Extreme stretch not attempted and out of reasonable reach for Wren-CLI.
<syntaxhighlight lang="
import "./fmt" for Fmt
Line 1,091 ⟶ 1,597:
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="
import "./fmt" for Fmt
| |||