Sisyphus sequence: Difference between revisions
New post.
(Added C++ solution) |
(New post.) |
||
Line 342:
100000 265781 392111
1000000 8820834 4761697</syntaxhighlight>
=={{header|Java}}==
<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%13d%s%11d",
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 aLimit) {
squareRoot = (int) Math.sqrt(aLimit);
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 aSquareRoot) {
boolean[] markedPrime = new boolean[aSquareRoot + 1];
Arrays.fill(markedPrime, true);
for ( int p = 2; p * p <= aSquareRoot; p++ ) {
if ( markedPrime[p] ) {
for ( int i = p * p; i <= aSquareRoot; i += p ) {
markedPrime[i] = false;
}
}
}
for ( int p = 2; p <= aSquareRoot; 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}}==
| |||