FragilePrime

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' );
        }
      }
    }
  }
}