import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.MathContext;
import java.util.HashMap;
import java.util.Map;

public class Twins {
    private static BigDecimal getRoot(BigDecimal value) {
        BigDecimal ZERO = new BigDecimal(0.0);
        BigDecimal ONE = new BigDecimal(1.0);
        BigDecimal TWO = new BigDecimal(2.0);
        if (value.compareTo(ZERO) <= 0) return null;
        BigDecimal approx = getApproximation(value);
        BigDecimal last = ZERO;
        BigDecimal guess = new BigDecimal(approx.toString());
        BigDecimal error = ZERO;

        int iterations = 0;
        int maxIterations = 100;
        int scale = 40;
        boolean more = true;

        while (more) {
            last = guess;
            guess = value.divide(guess, scale, BigDecimal.ROUND_HALF_UP);
            guess = guess.add(last);
            guess = guess.divide(TWO, scale, BigDecimal.ROUND_HALF_UP);
            error = value.subtract(guess.multiply(guess));
            if (++iterations >= maxIterations) {
                more = false;
            }
            else if (last.equals(guess)) {
                more = error.abs().compareTo(ONE) >= 0;
            }
        }
        return guess;
    }

    private static BigDecimal getApproximation(BigDecimal value) {
        BigDecimal ONE = new BigDecimal(1.0);
        BigInteger bInt = value.toBigInteger();
        int length = bInt.toString().length();
        if ((length % 2) == 0) {
            length--;
        }
        length/=2;
        BigDecimal guess = ONE.movePointRight(length);
        return guess;
    }

    private static Map<BigInteger,Boolean>isPrimeCache = new HashMap<BigInteger,Boolean>();
    public static boolean isPrime(BigInteger test)
    {
        Boolean cachedResult = isPrimeCache.get(test);
        if(cachedResult!=null)
          return cachedResult.booleanValue();
        BigDecimal sqrt = new BigDecimal(test);
        sqrt = getRoot(sqrt);
        sqrt = sqrt.round(MathContext.UNLIMITED);
        BigInteger sqrtInt = sqrt.toBigInteger();
        for(BigInteger i = new BigInteger("3"); sqrtInt.compareTo(i)>-1; i=i.add(new BigInteger("2")))
        {
            if(test.remainder(i).compareTo(BigInteger.ZERO)==0)
            {
              isPrimeCache.put(test,Boolean.FALSE);
              return false;
            }
        }
        isPrimeCache.put(test,Boolean.TRUE);
        return true;
    }
    // return curr prime note I consider P(1) = 3
    public static BigInteger P( BigInteger n ) {
      BigInteger currPrime = new BigInteger("0");
      for ( BigInteger i = new BigInteger("3"); ; i = i.add(new BigInteger("2")) ) {
        if ( isPrime( i ) ) {
          currPrime = currPrime.add(BigInteger.ONE);
        }
        if ( currPrime.compareTo(n)==0 ) return i;
      }
    }
    // returns the number of 0's in Pat(f(n),n)
    public static BigInteger primeCandidates( BigInteger n ) {
      if ( n.compareTo(BigInteger.ONE) == 0 ) return new BigInteger("2");
      BigInteger nMinusOne = n.subtract(BigInteger.ONE);
      BigInteger pnMinusOne = P(n).subtract(new BigInteger("1"));
      return primeCandidates( nMinusOne ).multiply(pnMinusOne);
    }
    // returns the number of 00's in Pat(f(n),n)
    public static BigInteger twinCandidates( BigInteger n ) {
      if ( n.compareTo(BigInteger.ONE) == 0 ) return BigInteger.ONE;
      BigInteger nMinusOne = n.subtract(BigInteger.ONE);
      BigInteger pnMinusTwo = P(n).subtract(new BigInteger("2"));
      return twinCandidates( nMinusOne ).multiply(pnMinusTwo);
    }

    // returns the number of 0010's in Pat(f(n),n)
    public static BigInteger tripletCandidates( BigInteger n ) {
      if ( n.compareTo(new BigInteger("2")) == 0 ) return new BigInteger("2");
      BigInteger nMinusOne = n.subtract(BigInteger.ONE);
      BigInteger pnMinusThree = P(n).subtract(new BigInteger("3"));
      return tripletCandidates( nMinusOne ).multiply(pnMinusThree);
    }

    // returns the number of 00100's in Pat(f(n),n)
    public static BigInteger quadrupletCandidates( BigInteger n ) {
      if ( n.compareTo(new BigInteger("2")) == 0 ) return new BigInteger("1");
      BigInteger nMinusOne = n.subtract(BigInteger.ONE);
      BigInteger pnMinusFour = P(n).subtract(new BigInteger("4"));
      return quadrupletCandidates( nMinusOne ).multiply(pnMinusFour);
    }
    public static BigInteger numberPrimesBetweenPnAndPnSquared(BigInteger n, boolean addCorrection)
    {
      if(n.compareTo(new BigInteger("2"))==-1)
        return BigInteger.ZERO; //error
      BigInteger Pn = P(n);
      BigInteger PnSquared = Pn.multiply(Pn);
      BigInteger primorialIndex = n.subtract(BigInteger.ONE);
      BigInteger result = primeCandidates(n.subtract(BigInteger.ONE)).multiply((PnSquared.subtract(Pn)));
      // divide through by the primorial(n-1)
      while(primorialIndex.compareTo(BigInteger.ZERO)==1)
      {
        result = result.divide(P(primorialIndex));
        primorialIndex = primorialIndex.subtract(BigInteger.ONE);
      }
      // my P(n) function omits 2 so we'll add it back into the primorial here
      result = result.divide(new BigInteger("2"));
      if(addCorrection)
      {
        double nDouble = n.doubleValue();
        double correction = Math.log10(nDouble)*0.145348;
        nDouble *= correction;
        double nDoubleSquared = nDouble*nDouble;
        long nDoubleSquaredLong = Math.round(nDoubleSquared);
        result = result.subtract(new BigInteger(String.valueOf(nDoubleSquaredLong)));
      }
      return result;
    }

    public static BigInteger numberTwinsBetweenPnAndPnSquared(BigInteger n, boolean addCorrection)
    {
      if(n.compareTo(new BigInteger("2"))==-1)
        return BigInteger.ZERO; //error
      BigInteger Pn = P(n);
      BigInteger PnSquared = Pn.multiply(Pn);
      BigInteger primorialIndex = n.subtract(BigInteger.ONE);
      BigInteger result = twinCandidates(n.subtract(BigInteger.ONE)).multiply((PnSquared.subtract(Pn)));
      // divide through by the primorial(n-1)
      while(primorialIndex.compareTo(BigInteger.ZERO)==1)
      {
        result = result.divide(P(primorialIndex));
        primorialIndex = primorialIndex.subtract(BigInteger.ONE);
      }
      // my P(n) function omits 2 so we'll add it back into the primorial here
      result = result.divide(new BigInteger("2"));
      if(addCorrection)
      {
        double nDouble = n.doubleValue();
        double correction = Math.log10(nDouble)*0.058652;
        nDouble *= correction;
        double nDoubleSquared = nDouble*nDouble;
        long nDoubleSquaredLong = Math.round(nDoubleSquared);
        result = result.subtract(new BigInteger(String.valueOf(nDoubleSquaredLong)));
      }
      return result;
    }

    public static BigInteger numberTripletsBetweenPnAndPnSquared(BigInteger n, boolean addCorrection)
    {
      if(n.compareTo(new BigInteger("3"))==-1)
        return BigInteger.ZERO; //error
      BigInteger Pn = P(n);
      BigInteger PnSquared = Pn.multiply(Pn);
      BigInteger primorialIndex = n.subtract(BigInteger.ONE);
      BigInteger result = tripletCandidates(n.subtract(BigInteger.ONE)).multiply((PnSquared.subtract(Pn)));
      // divide through by the primorial(n-1)
      while(primorialIndex.compareTo(BigInteger.ZERO)==1)
      {
        result = result.divide(P(primorialIndex));
        primorialIndex = primorialIndex.subtract(BigInteger.ONE);
      }
      // my P(n) function omits 2 so we'll add it back into the primorial here
      result = result.divide(new BigInteger("2"));
      if(addCorrection)
      {
        double nDouble = n.doubleValue();
        double correction = Math.log10(nDouble)*0.02881;
        nDouble *= correction;
        double nDoubleSquared = nDouble*nDouble;
        long nDoubleSquaredLong = Math.round(nDoubleSquared);
        result = result.subtract(new BigInteger(String.valueOf(nDoubleSquaredLong)));
      }
      return result;
    }

    public static BigInteger numberQuadrupletsBetweenPnAndPnSquared(BigInteger n, boolean addCorrection)
    {
      if(n.compareTo(new BigInteger("3"))==-1)
        return BigInteger.ZERO; //error
      BigInteger Pn = P(n);
      BigInteger PnSquared = Pn.multiply(Pn);
      BigInteger primorialIndex = n.subtract(BigInteger.ONE);
      BigInteger result = quadrupletCandidates(n.subtract(BigInteger.ONE)).multiply((PnSquared.subtract(Pn)));
      // divide through by the primorial(n-1)
      while(primorialIndex.compareTo(BigInteger.ZERO)==1)
      {
        result = result.divide(P(primorialIndex));
        primorialIndex = primorialIndex.subtract(BigInteger.ONE);
      }
      // my P(n) function omits 2 so we'll add it back into the primorial here
      result = result.divide(new BigInteger("2"));
      if(addCorrection)
      {
        double nDouble = n.doubleValue();
        double correction = Math.log10(nDouble)*0.00718;
        nDouble *= correction;
        double nDoubleSquared = nDouble*nDouble;
        long nDoubleSquaredLong = Math.round(nDoubleSquared);
        result = result.subtract(new BigInteger(String.valueOf(nDoubleSquaredLong)));
      }
      return result;
    }
    public static BigInteger numPrimePnToPnSquared(BigInteger n)
    {
      if(n.compareTo(new BigInteger("2"))==-1)
        return BigInteger.ZERO; //error
      BigInteger Pn = P(n);
      BigInteger PnSquared = Pn.multiply(Pn);
      BigInteger numPrime = BigInteger.ZERO;
      for (BigInteger i=Pn.add(new BigInteger("2")); i.compareTo(PnSquared)==-1; i = i.add(new BigInteger("2")))
        if ( isPrime( i ) ) numPrime = numPrime.add(BigInteger.ONE);
      return numPrime;
    }
    public static BigInteger numTwinPnToPnSquared(BigInteger n)
    {
      if(n.compareTo(new BigInteger("2"))==-1)
        return BigInteger.ZERO; //error
      BigInteger Pn = P(n);
      BigInteger PnSquared = Pn.multiply(Pn);
      BigInteger numTwin = BigInteger.ZERO;
      for (BigInteger i=Pn.add(new BigInteger("2")); i.compareTo(PnSquared)==-1; i = i.add(new BigInteger("2")))
        if ( isPrime( i ) && isPrime(i.add(new BigInteger("2"))) ) numTwin = numTwin.add(BigInteger.ONE);
      return numTwin;
    }

    public static BigInteger numTripletPnToPnSquared(BigInteger n)
    {
      if(n.compareTo(new BigInteger("2"))==-1)
        return BigInteger.ZERO; //error
      BigInteger Pn = P(n);
      BigInteger PnSquared = Pn.multiply(Pn);
      BigInteger numTriplet = BigInteger.ZERO;
      for (BigInteger i=Pn.add(new BigInteger("2")); i.compareTo(PnSquared)==-1; i = i.add(new BigInteger("2")))
        if ( isPrime( i ) && isPrime(i.add(new BigInteger("2"))) && isPrime(i.add( new BigInteger("6"))) ) numTriplet = numTriplet.add(BigInteger.ONE);
      return numTriplet;
    }

    public static BigInteger numQuadrupletPnToPnSquared(BigInteger n)
    {
      if(n.compareTo(new BigInteger("2"))==-1)
        return BigInteger.ZERO; //error
      BigInteger Pn = P(n);
      BigInteger PnSquared = Pn.multiply(Pn);
      BigInteger numQuadruplet = BigInteger.ZERO;
      for (BigInteger i=Pn.add(new BigInteger("2")); i.compareTo(PnSquared)==-1; i = i.add(new BigInteger("2")))
        if ( isPrime( i ) && isPrime(i.add(new BigInteger("2"))) && isPrime(i.add( new BigInteger("6"))) && isPrime(i.add( new BigInteger("8"))) ) numQuadruplet = numQuadruplet.add(BigInteger.ONE);
      return numQuadruplet;
    }

    public static void main(String[] args) {
      // examining the #Primes[P(n)->P(n)^2] formula
      System.out.println( "---------------------------------------------------------" );
      System.out.println( "EXAMINING THE #Primes[P(n)->P(n)^2] AND #Primes_Corrected[P(n)->P(n)^2] FORMULAE" );
      for ( int x = 2; x < 400; x++ ) {
        BigInteger numPrimes = numberPrimesBetweenPnAndPnSquared( new BigInteger(String.valueOf(x)), false );
        BigInteger numPrimesCorrected = numberPrimesBetweenPnAndPnSquared( new BigInteger(String.valueOf(x)), true );
        BigInteger actualPrimes = numPrimePnToPnSquared(new BigInteger(String.valueOf(x)));
        System.out.println( "#Primes[P(" + x + ")->P(" + x + ")^2] = " + numPrimes
            + "; #Primes_Corrected[P(" + x + ")->P(" + x + ")^2] = " + numPrimesCorrected
            + "; actual number primes in this interval = " + actualPrimes
            + "; (numPrimesCorrected-actualPrimes) = " + (numPrimesCorrected.longValue()-actualPrimes.longValue()));
      }
      // examining the #Twins[P(n)->P(n)^2] formula
      System.out.println( "---------------------------------------------------------" );
      System.out.println( "EXAMINING THE #Twins[P(n)->P(n)^2] AND #Twins_Corrected[P(n)->P(n)^2] FORMULAE" );
      for ( int x = 2; x < 400; x++ ) {
        BigInteger numTwins = numberTwinsBetweenPnAndPnSquared( new BigInteger(String.valueOf(x)), false );
        BigInteger numTwinsCorrected = numberTwinsBetweenPnAndPnSquared( new BigInteger(String.valueOf(x)), true );
        BigInteger actualTwins = numTwinPnToPnSquared(new BigInteger(String.valueOf(x)));
        System.out.println( "#Twins[P(" + x + ")->P(" + x + ")^2] = " + numTwins
            + "; #Twins_Corrected[P(" + x + ")->P(" + x + ")^2] = " + numTwinsCorrected
            + "; actual number twins in this interval = " + actualTwins
            + "; (numTwinsCorrected-actualTwins) = " + (numTwinsCorrected.longValue()-actualTwins.longValue()));
      }
      // examining the #Triplets[P(n)->P(n)^2] formula
      System.out.println( "---------------------------------------------------------" );
      System.out.println( "EXAMINING THE #Triplets[P(n)->P(n)^2] AND #Triplets_Corrected[P(n)->P(n)^2] FORMULAE" );
      for ( int x = 3; x < 400; x++ ) {
        BigInteger numTriplets = numberTripletsBetweenPnAndPnSquared( new BigInteger(String.valueOf(x)), false );
        BigInteger numTripletsCorrected = numberTripletsBetweenPnAndPnSquared( new BigInteger(String.valueOf(x)), true );
        BigInteger actualTriplets = numTripletPnToPnSquared(new BigInteger(String.valueOf(x)));
        System.out.println( "#Triplets[P(" + x + ")->P(" + x + ")^2] = " + numTriplets
            + "; #Triplets_Corrected[P(" + x + ")->P(" + x + ")^2] = " + numTripletsCorrected
            + "; actual number triplets in this interval = " + actualTriplets
            + "; (numTripletsCorrected-actualTriplets) = " + (numTripletsCorrected.longValue()-actualTriplets.longValue()));
      }

      // examining the #Quadruplets[P(n)->P(n)^2] formula
      System.out.println( "---------------------------------------------------------" );
      System.out.println( "EXAMINING THE #Quadruplets[P(n)->P(n)^2] AND #Quadruplets_Corrected[P(n)->P(n)^2] FORMULAE" );
      for ( int x = 3; x < 400; x++ ) {
        BigInteger numQuadruplets = numberQuadrupletsBetweenPnAndPnSquared( new BigInteger(String.valueOf(x)), false );
        BigInteger numQuadrupletsCorrected = numberQuadrupletsBetweenPnAndPnSquared( new BigInteger(String.valueOf(x)), true );
        BigInteger actualQuadruplets = numQuadrupletPnToPnSquared(new BigInteger(String.valueOf(x)));
        System.out.println( "#Quadruplets[P(" + x + ")->P(" + x + ")^2] = " + numQuadruplets
            + "; #Quadruplets_Corrected[P(" + x + ")->P(" + x + ")^2] = " + numQuadrupletsCorrected
            + "; actual number quadruplets in this interval = " + actualQuadruplets
            + "; (numQuadrupletsCorrected-actualQuadruplets) = " + (numQuadrupletsCorrected.longValue()-actualQuadruplets.longValue()));
      }
    }
}