Skip to content

Instantly share code, notes, and snippets.

/FragilePrime
Created Nov 22, 2014

Embed
What would you like to do?
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.MathContext;
import java.util.ArrayDeque;
import java.util.Iterator;
public class FragilePrime {
private static final char CANDIDATES[] = { '0', '1', '4', '6', '8', '9' };
private static final BigInteger MAX_TRIAL_DIVISION = BigInteger.valueOf( 10000 );
private static final int MAX_ZEROS_LENGTH = 10000;
private static final int FIRST_PRIMES[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 };
private static final BigDecimal BD_TWO = BigDecimal.valueOf( 2 );
private static final BigInteger BI_TWO = BigInteger.valueOf( 2 );
private static final BigInteger BI_THREE = BigInteger.valueOf( 3 );
private static final BigInteger BI_FOUR = BigInteger.valueOf( 4 );
private static final BigInteger BI_FIVE = BigInteger.valueOf( 5 );
private static final int DEFAULT_RETURN_PRECISION = 58;
private static final int DEFAULT_CALC_PRECISION = 78;
private static final BigDecimal EPSILON = BigDecimal.valueOf( 1, DEFAULT_CALC_PRECISION );
private static final MathContext DEFAULT_CALC_CONTEXT = new MathContext( DEFAULT_CALC_PRECISION );
private static final MathContext DEFAULT_RETURN_CONTEXT = new MathContext( DEFAULT_RETURN_PRECISION );
public static class RightTree {
public char c;
public RightTree parent;
public RightTree( RightTree parent, char c ) {
this.parent = parent;
this.c = c;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
RightTree current = this;
while ( current != null ) {
sb.append( current.c );
current = current.parent;
}
return sb.toString();
}
}
public static class RightComposites implements Iterable< String > {
private String left;
private RightIterator iterator;
public RightComposites() {
}
public RightComposites( String left ) {
this.left=left;
}
@Override
public Iterator< String > iterator() {
return iterator = new RightIterator( left, '1', '9' );
}
private void remove( String prefix ) {
iterator.remove( prefix );
}
}
public static class RightIterator implements Iterator< String > {
private final ArrayDeque< RightTree > queue = new ArrayDeque<>();
private String left;
public RightIterator( String left, char... roots ) {
this.left = left;
for ( char root : roots )
if ( !checkPrime( left, true, String.valueOf( root ), true ) )
queue.addLast( new RightTree( null, root ) );
}
@Override
public boolean hasNext() {
return !queue.isEmpty();
}
@Override
public String next() {
RightTree current = queue.removeFirst();
for ( char candidate : CANDIDATES ) {
RightTree child = new RightTree( current, candidate );
String right = child.toString();
if ( !isPrime( right ) )
if ( !checkPrime( left, true, right, true ) )
queue.addLast( child );
}
return current.toString();
}
private void remove( String prefix ) {
while ( !queue.isEmpty() ) {
RightTree tree = queue.peekLast();
if ( tree.toString().endsWith( prefix ) )
queue.removeLast();
else
break;
}
}
}
public static class LeftTree {
public char c;
public LeftTree parent;
public LeftTree( LeftTree parent, char c ) {
this.parent = parent;
this.c = c;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
LeftTree current = this;
while ( current != null ) {
sb.append( current.c );
current = current.parent;
}
return sb.reverse().toString();
}
}
public static class LeftComposites implements Iterable< String > {
private String prefix;
public LeftComposites() {
}
public LeftComposites( String prefix ) {
this.prefix = prefix;
}
@Override
public Iterator< String > iterator() {
if ( prefix != null )
return new LeftIterator( prefix );
return new LeftIterator( '1', '4', '6', '8', '9' );
}
}
public static class LeftIterator implements Iterator< String > {
private final ArrayDeque< LeftTree > queue = new ArrayDeque<>();
public LeftIterator( char... roots ) {
for ( char root : roots )
queue.addLast( new LeftTree( null, root ) );
}
public LeftIterator( String prefix ) {
LeftTree parent = null;
for ( char c : prefix.toCharArray() )
parent = new LeftTree( parent, c );
if ( parent != null )
queue.addLast( parent );
}
@Override
public boolean hasNext() {
return !queue.isEmpty();
}
@Override
public String next() {
LeftTree current = queue.removeFirst();
for ( char candidate : CANDIDATES ) {
LeftTree child = new LeftTree( current, candidate );
if ( !isPrime( child.toString() ) )
queue.addLast( child );
}
return current.toString();
}
}
private static boolean isPrime( String number ) {
if ( number.isEmpty() )
return false;
BigInteger bi = new BigInteger( number );
if ( bi.bitLength() < 64 )
return passesMiller( bi.longValue() );
if ( !passesTrialDivision( bi ) )
return false;
return passesBailliePSW( bi );
}
public static boolean passesTrialDivision( BigInteger n ) {
n = n.abs();
if ( !n.testBit( 0 ) )
return n.equals( BI_TWO );
if ( n.remainder( BI_THREE ).signum() == 0 )
return n.equals( BI_THREE );
boolean switch42 = false;
for ( BigInteger i = BI_FIVE; i.compareTo( MAX_TRIAL_DIVISION ) <= 0; i = i.add( switch42 ? BI_FOUR : BI_TWO ), switch42 = !switch42 )
if ( n.remainder( i ).signum() == 0 )
return false;
return !n.equals( BigInteger.ONE );
}
public static boolean passesMiller( long n ) {
if ( n < 0L )
n = -n;
if ( ( n & 1L ) == 0L )
return n == 2L;
// Smallest odd number that requires q Miller-Rabin primality tests.
// Sloane's A006945: http://oeis.org/A006945
int q;
if ( n < 2152302898747L ) {
if ( n < 1373653L ) {
if ( n < 2047L ) {
if ( n < 9L )
return n > 1L;
else
q = 1;
} else
q = 2;
} else {
if ( n < 3215031751L )
q = n < 25326001L ? 3 : 4;
else
q = 5;
}
} else if ( n < 341550071728321L )
q = n < 3474749660383L ? 6 : 7;
else
q = n < 3825123056546413051L ? 9 : 12;
long nMinusOne = n - 1;
int s = Long.numberOfTrailingZeros( nMinusOne );
long r = nMinusOne >> s;
if ( n <= Integer.MAX_VALUE ) {
for ( int i = 0; i < q; i++ )
if ( !internalPassesMillerRabin( ( int )n, FIRST_PRIMES[ i ], ( int )nMinusOne, ( int )r, s ) )
return false;
} else {
BigInteger br = BigInteger.valueOf( r );
BigInteger bn = BigInteger.valueOf( n );
for ( int i = 0; i < q; i++ ) {
BigInteger bRemainder = BigInteger.valueOf( FIRST_PRIMES[ i ] ).modPow( br, bn );
long remainder = bRemainder.longValue();
int j = 0;
while ( ( j > 0 || remainder != 1L ) && remainder != nMinusOne ) {
if ( j > 0 && remainder == 1L )
return false;
j++;
if ( j == s )
return false;
bRemainder = bRemainder.modPow( BI_TWO, bn );
remainder = bRemainder.longValue();
}
}
}
return true;
}
private static boolean internalPassesMillerRabin( int n, int base, int nMinusOne, int m, int a ) {
int j = 0;
int z = modPow( base, m, n );
while ( ( j != 0 || z != 1 ) && z != nMinusOne ) {
if ( j > 0 && z == 1 )
return false;
j++;
if ( j == a )
return false;
z = modPow( z, 2, n );
}
return true;
}
private static boolean passesMillerRabin( int n, int base ) {
int nMinusOne = n - 1;
int a = Integer.numberOfTrailingZeros( nMinusOne );
int m = nMinusOne >> a;
return internalPassesMillerRabin( n, base, nMinusOne, m, a );
}
public static boolean passesBailliePSW( BigInteger n ) {
n = n.abs();
if ( n.bitLength() < 32 ) {
int nn = n.intValue();
if ( nn <= 1 )
return false;
if ( nn <= 3 )
return true;
if ( ( nn & 1 ) == 0 )
return false;
int sqrt = ( int )Math.sqrt( nn );
if ( sqrt * sqrt == nn )
return false;
if ( !passesMillerRabin( nn, 2 ) )
return false;
}
else {
if ( !n.testBit( 0 ) )
return false;
if ( !passesMillerRabin( n, BI_TWO ) )
return false;
if ( isInteger( sqrt( new BigDecimal( n ) ) ) )
return false;
}
return passesLucas( n );
}
public static boolean isInteger( BigDecimal x ) {
return x.stripTrailingZeros().scale() <= 0;
}
public static BigDecimal sqrt( BigDecimal n ) {
if ( n.signum() == 0 || BigDecimal.ONE.compareTo( n ) == 0 )
return n;
if ( n.signum() < 0 )
throw new ArithmeticException( "Square root of negative argument " + n + " is undefined" );
if ( n.compareTo( BigDecimal.ONE ) < 0 )
return internalDivide( BigDecimal.ONE, sqrt( internalDivide( BigDecimal.ONE, n, DEFAULT_CALC_PRECISION ) ), DEFAULT_RETURN_PRECISION );
BigDecimal guess;
try {
guess = BigDecimal.valueOf( Math.sqrt( n.doubleValue() ) );
} catch ( NumberFormatException e ) {
guess = n;
int digits = guess.precision() - guess.scale();
if ( digits > 10 ) {
BigInteger pre = guess.toBigInteger();
digits = pre.bitLength() >> 1;
if ( digits > 0 ) {
pre = pre.shiftRight( digits - 1 );
guess = new BigDecimal( pre );
}
}
}
while ( true ) {
BigDecimal newGuess = internalDivide( guess.add( internalDivide( n, guess, DEFAULT_CALC_PRECISION ) ), BD_TWO, DEFAULT_CALC_PRECISION );
BigDecimal delta = newGuess.subtract( guess );
int signum = delta.signum();
if ( signum == 0 || ( signum > 0 ? delta : delta.negate() ).compareTo( EPSILON ) <= 0 ) {
delta = newGuess.multiply( newGuess ).subtract( n ).abs();
if ( delta.signum() > 0 ) {
if ( signum >= 0 ) {
guess = newGuess.add( EPSILON );
if ( guess.multiply( guess ).subtract( n ).abs().compareTo( delta ) < 0 )
return internalRound( guess, DEFAULT_RETURN_PRECISION );
}
if ( signum <= 0 ) {
guess = newGuess.subtract( EPSILON );
if ( guess.multiply( guess ).subtract( n ).abs().compareTo( delta ) < 0 )
return internalRound( guess, DEFAULT_RETURN_PRECISION );
}
}
return internalRound( newGuess, DEFAULT_RETURN_PRECISION );
}
guess = newGuess;
}
}
private static BigDecimal internalRound( BigDecimal n, int precision ) {
if ( n.scale() <= precision )
return n.stripTrailingZeros();
return internalDivide( n, BigDecimal.ONE, precision );
}
private static BigDecimal internalDivide( BigDecimal a, BigDecimal b, int precision ) {
if ( a.scale() - a.precision() - b.scale() + b.precision() < precision )
return a.scaleByPowerOfTen( precision ).divideToIntegralValue( b ).scaleByPowerOfTen( -precision ).stripTrailingZeros();
return a.divide( b, precision == DEFAULT_CALC_PRECISION ? DEFAULT_CALC_CONTEXT : DEFAULT_RETURN_CONTEXT ).stripTrailingZeros();
}
public static int modPow( long base, long exponent, int modulus ) {
if ( modulus <= 0 )
throw new ArithmeticException( "Modulus is not positive" );
if ( exponent < 0L )
throw new ArithmeticException( "Exponent cannot be negative" );
if ( modulus == 1 )
return 0;
long number = 1L;
base %= modulus;
if ( base < 0L )
base += modulus;
while ( exponent > 0L ) {
if ( ( exponent & 1L ) == 1L )
number = ( number * base ) % modulus;
exponent >>= 1;
base = ( base * base ) % modulus;
}
return ( int )number;
}
// Standard Java BigInteger private method.
private static boolean passesMillerRabin( BigInteger n, BigInteger base ) {
BigInteger nMinusOne = n.subtract( BigInteger.ONE );
BigInteger m = nMinusOne;
int a = m.getLowestSetBit();
m = m.shiftRight( a );
return internalPassesMillerRabin( n, base, nMinusOne, m, a );
}
private static boolean internalPassesMillerRabin( BigInteger n, BigInteger base, BigInteger nMinusOne, BigInteger m, int a ) {
int j = 0;
BigInteger z = base.modPow( m, n );
while ( ( j != 0 || !z.equals( BigInteger.ONE ) ) && !z.equals( nMinusOne ) ) {
if ( j > 0 && z.equals( BigInteger.ONE ) )
return false;
j++;
if ( j == a )
return false;
z = z.modPow( BI_TWO, n );
}
return true;
}
// Standard Java BigInteger private method.
private static boolean passesLucas( BigInteger n ) {
int d = 5;
while ( jacobiSymbol( d, n ) != -1 )
d = d < 0 ? 2 - d : -( d + 2 );
BigInteger u = lucasSequence( d, n );
return u.mod( n ).signum() == 0;
}
// Standard Java BigInteger private method.
private static int jacobiSymbol( int p, BigInteger n ) {
if ( p == 0 )
return 0;
int u = 0;
byte bytes[] = n.toByteArray();
int i = bytes.length - 4;
if ( i < 0 )
i = 0;
for ( ; i < bytes.length; i++ ) {
u <<= 8;
byte b = bytes[ i ];
if ( b < 0 )
u += 256;
u += b;
}
int j = 1;
if ( p < 0 ) {
p = -p;
int n8 = u & 7;
if ( n8 == 3 || n8 == 7 )
j = -j;
}
while ( ( p & 3 ) == 0 )
p >>= 2;
if ( ( p & 1 ) == 0 ) {
p >>= 1;
if ( ( ( u ^ ( u >> 1 ) ) & 2 ) != 0 )
j = -j;
}
if ( p == 1 )
return j;
if ( ( p & u & 2 ) != 0 )
j = -j;
u = n.mod( BigInteger.valueOf( p ) ).intValue();
while ( u != 0 ) {
while ( ( u & 3 ) == 0 )
u >>= 2;
if ( ( u & 1 ) == 0 ) {
u >>= 1;
if ( ( ( p ^ ( p >> 1 ) ) & 2 ) != 0 )
j = -j;
}
if ( u == 1 )
return j;
int t = u;
u = p;
p = t;
if ( ( u & p & 2 ) != 0 )
j = -j;
u %= p;
}
return 0;
}
// Standard Java BigInteger private method.
private static BigInteger lucasSequence( int z, BigInteger n ) {
BigInteger d = BigInteger.valueOf( z );
BigInteger u = BigInteger.ONE;
BigInteger u2;
BigInteger v = BigInteger.ONE;
BigInteger v2;
BigInteger k = n.add( BigInteger.ONE );
for ( int i = k.bitLength() - 2; i >= 0; i-- ) {
u2 = u.multiply( v ).mod( n );
v2 = v.multiply( v ).add( d.multiply( u.multiply( u ) ) ).mod( n );
if ( v2.testBit( 0 ) )
v2 = v2.subtract( n );
v2 = v2.shiftRight( 1 );
u = u2;
v = v2;
if ( k.testBit( i ) ) {
u2 = u.add( v ).mod( n );
if ( u2.testBit( 0 ) )
u2 = u2.subtract( n );
u2 = u2.shiftRight( 1 );
v2 = v.add( d.multiply( u ) ).mod( n );
if ( v2.testBit( 0 ) )
v2 = v2.subtract( n );
v2 = v2.shiftRight( 1 );
u = u2;
v = v2;
}
}
return u;
}
private static boolean checkPrime( String left, boolean iterateLeft, String right, boolean iterateRight ) {
StringBuilder sbLeft = new StringBuilder( left );
StringBuilder sbRight = new StringBuilder( right );
for ( int i = iterateLeft ? sbLeft.length() : 1; i > 0; i-- ) {
for ( int j = iterateRight ? sbRight.length() : 1; j > 0; j-- ) {
if ( isPrime( sbLeft.toString() + sbRight ) )
return true;
if ( j > 0 )
sbRight.deleteCharAt( 0 );
}
if ( i > 0 )
sbLeft.deleteCharAt( i - 1 );
}
return false;
}
public static void main( String args[] ) {
for ( String left : args.length == 0 ? new LeftComposites() : new LeftComposites( args[ 0 ] ) ) {
if ( left.endsWith( "0" ) )
continue;
RightComposites rightComposites = new RightComposites( left );
for ( String right : rightComposites ) {
if ( right.startsWith( "0" ) )
continue;
if ( new BigInteger( left + right ).mod( BI_THREE ).signum() == 0 )
continue;
StringBuilder zeros = new StringBuilder( MAX_ZEROS_LENGTH );
for ( int length = 0; length < MAX_ZEROS_LENGTH; length++ ) {
String number = left + zeros + right;
if ( isPrime( number ) ) {
rightComposites.remove( right );
if ( !checkPrime( left + zeros, false, right.substring( 1 ), true ) ) {
if ( !checkPrime( left.substring( 0, left.length() - 1 ), true, zeros + right, false ) ) {
System.out.println( number );
System.out.println( "Len: " + number.length() );
if ( number.length() > 7000 )
System.out.println( "GOTCHA!" );;
}
}
break;
}
zeros.append( '0' );
}
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.