Sisyphus sequence: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
(→{{header|Perl}}: prepend ==={{header|Free Pascal}=== 36 found in ~16,5 min) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
| (6 intermediate revisions by 3 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 1,180 ⟶ 1,519:
Extreme stretch not attempted and out of reasonable reach for Wren-CLI.
<syntaxhighlight lang="
import "./fmt" for Fmt
Line 1,258 ⟶ 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
| |||