Sisyphus sequence: Difference between revisions
Content added Content deleted
(Added C++ solution) |
(New post.) |
||
Line 342: | Line 342: | ||
100000 265781 392111 |
100000 265781 392111 |
||
1000000 8820834 4761697</syntaxhighlight> |
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}}== |
=={{header|jq}}== |