139 lines
3.6 KiB
Java
139 lines
3.6 KiB
Java
import java.util.ArrayList;
|
|
import java.util.Arrays;
|
|
import java.util.Collections;
|
|
import java.util.List;
|
|
|
|
public final class OrmistonTriples {
|
|
|
|
public static void main(String[] aArgs) {
|
|
final long limit = 10_000_000_000L;
|
|
SegmentedPrimeIterator primes = new SegmentedPrimeIterator(limit);
|
|
List<Long> ormistons = new ArrayList<Long>();
|
|
long lowerLimit = limit / 10;
|
|
int count = 0;
|
|
List<Integer> counts = new ArrayList<Integer>();
|
|
long p1 = 0, p2 = 0, p3 = 0;
|
|
|
|
while ( p3 < limit ) {
|
|
p1 = p2; p2 = p3; p3 = primes.next();
|
|
|
|
if ( ( p2 - p1 ) % 18 != 0 || ( p3 - p2 ) % 18 != 0 ) {
|
|
continue;
|
|
}
|
|
|
|
if ( ! haveSameDigits(p1, p2) ) {
|
|
continue;
|
|
}
|
|
|
|
if ( haveSameDigits(p2, p3) ) {
|
|
if ( count < 25 ) {
|
|
ormistons.add(p1);
|
|
}
|
|
if ( p1 >= lowerLimit ) {
|
|
counts.add(count);
|
|
lowerLimit *= 10;
|
|
}
|
|
count += 1;
|
|
}
|
|
}
|
|
counts.add(count);
|
|
|
|
System.out.println("The smallest member of the first 25 Ormiston triples:");
|
|
for ( int i = 0; i < ormistons.size(); i++ ) {
|
|
System.out.print(String.format("%10d%s", ormistons.get(i), ( i % 5 == 4 ? "\n" : "" )));
|
|
}
|
|
System.out.println();
|
|
|
|
lowerLimit = limit / 10;
|
|
for ( int i = 0; i < counts.size(); i++ ) {
|
|
System.out.println(counts.get(i) + " Ormiston triples less than " + lowerLimit);
|
|
lowerLimit *= 10;
|
|
}
|
|
|
|
}
|
|
|
|
private static boolean haveSameDigits(long aOne, long aTwo) {
|
|
return digits(aOne).equals(digits(aTwo));
|
|
}
|
|
|
|
private static List<Integer> digits(long aNumber) {
|
|
List<Integer> result = new ArrayList<Integer>();
|
|
while ( aNumber > 0 ) {
|
|
result.add((int) ( aNumber % 10 ));
|
|
aNumber /= 10;
|
|
}
|
|
Collections.sort(result);
|
|
return result;
|
|
}
|
|
|
|
}
|
|
|
|
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 static int index, squareRoot;
|
|
private static long low, high;
|
|
private static List<Long> primes = new ArrayList<Long>();
|
|
private static List<Long> smallPrimes = new ArrayList<Long>();
|
|
|
|
}
|