package patn;
import java.util.HashMap;
import java.util.Map;
/**
* This class demonstrates functions and concepts found at
* <A href="http://www.rankyouragent.com/primes/primes.htm">http://www.rankyouragent.com/primes/primes.htm</A> and
* <A href="http://www.rankyouragent.com/primes/primes_simple.htm">http://www.rankyouragent.com/primes/primes_simple.htm</A>
*
* See program output @ <A href="http://www.rankyouragent.com/primes/patn.java.output.txt">patn.java.output.txt</A>
* It was written for readability, not for speed.
* Please don't judge my programming ability by this example. :)
* @author Martin Winer
*
* NOTE: please provide -Xmx756M -XX:MaxPermSize=512M to the java vm
*/
public class PatN {
// this is a representation of a bitstring of infinite zeros
public static final boolean[] INFINITE_ZEROS = new boolean[0];
// an interface for f(n) found on the website
public static interface FOfN {
public int f( int n );
public String getDescription();
}
// an implementation of f(n) where f(n) = 2n+1
public static class TwoNPlusOne implements FOfN {
public int f( int n ) {
return ( 2 * n ) + 1;
}
public String getDescription() {
return "2n+1";
}
}
// finds the first zero in the bitString and returns the 1 based index
public static int FindFirstZero( boolean[] bitString ) {
int firstZero = 1;
for ( int i = 0; i < bitString.length; i++ )
if ( !bitString[i] ) return i + 1;
return firstZero;
}
// generates an elemental which is a bit string of 1 followed by fOfN(firstZero)-1 0's
public static boolean[] Elemental( FOfN fOfN, int firstZero ) {
int elementalSize = fOfN.f( firstZero );
boolean[] elemental = new boolean[elementalSize];
for ( int i = 0; i < elemental.length; i++ )
if ( i == 0 )
elemental[i] = true;
else
elemental[i] = false;
return elemental;
}
// merges the lhsPattern with the rhsPattern by finding the first zero
// in lhsPattern and merging it with the rhsPattern (elemental)
// merge aligns the first 1 of the rhsPattern with the first zero of
// the lhsPattern and then iteratively OR's the entries producing a
// merged pattern of size = size(lhsPattern)*size(rhsPattern)
// Note 0... MERGE anyPattern = anyPattern
public static boolean[] Merge( boolean[] lhsPattern, boolean[] rhsPattern ) {
// Note 0... MERGE anyPattern = anyPattern
if ( lhsPattern == INFINITE_ZEROS ) return rhsPattern;
int firstZeroLhsPattern = FindFirstZero( lhsPattern );
int mergedPatternSize = lhsPattern.length * rhsPattern.length;
boolean[] mergedPattern = new boolean[mergedPatternSize];
for ( int i = 0; i < mergedPattern.length; i++ ) {
boolean currLhsBit = false;
boolean currRhsBit = false;
currLhsBit = lhsPattern[i % ( lhsPattern.length )];
// rhs pattern is shifted to align with first zero in LHS pattern
currRhsBit = rhsPattern[Math.abs( ( i + 1 - firstZeroLhsPattern ) ) % rhsPattern.length];
// or the result to produce the merged pattern
mergedPattern[i] = currLhsBit || currRhsBit;
}
return mergedPattern;
}
//store for later display;
private static Map<Long,String> elementals = new HashMap<Long,String>();
// Pat(f(n),n)
// Pat(f(n),0) = 0...
// Pat(f(n),n) = Pat(f(n),n-1) MERGE Elemental(f(n),firstZeroLhsPattern)
// eg, let f(n) = 2n+1
// Pat(2n+1,1) = 100...
// Pat(2n+1,2) = 110100100101100...
public static boolean[] Pat( FOfN fOfN, long n ) {
if ( n == 0 )
return INFINITE_ZEROS;
else {
int firstZeroLhsPattern = FindFirstZero( Pat( fOfN, n - 1 ) );
boolean[] elemental = Elemental( fOfN, firstZeroLhsPattern );
elementals.put(new Long(n),bitStringToDisplayString(elemental));
return Merge( Pat( fOfN, n - 1 ), elemental );
}
}
// a basic implementation of isPrime
public static boolean isPrime( long n ) {
boolean prime = true;
for ( long i = 3; i <= Math.sqrt( n ); i += 2 )
if ( n % i == 0 ) {
prime = false;
break;
}
if ( ( n % 2 != 0 && prime && n > 2 ) || n == 2 ) {
return true;
}
else {
return false;
}
}
// return curr prime note I consider P(1) = 3
public static long P( int n ) {
long currPrime = 0;
for ( int i = 3; i < Integer.MAX_VALUE; i += 2 ) {
if ( isPrime( i ) ) {
currPrime++;
}
if ( currPrime == n ) return i;
}
return 1;
}
// returns the number of zeros in Pat(f(n),n)
public static long zeros( int n ) {
if ( n == 1 ) return 2;
return zeros( n - 1 ) * ( P( n ) - 1 );
}
// returns the number of 00's in Pat(f(n),n)
public static long twins( int n ) {
if ( n == 1 ) return 1;
return twins( n - 1 ) * ( P( n ) - 2 );
}
// returns the number of 0010's in Pat(f(n),n)
public static long triplets( int n ) {
if ( n == 2 ) return 2;
return triplets( n - 1 ) * ( P( n ) - 3 );
}
// returns the number of 00100's in Pat(f(n),n)
public static long quadruplets( int n ) {
if ( n == 2 ) return 1;
return quadruplets( n - 1 ) * ( P( n ) - 4 );
}
// returns the number of ones in Pat(f(n),n)
public static long ones( int n ) {
if ( n == 1 ) return 1;
return ( ones( n - 1 ) * P( n ) ) + zeros( n - 1 );
}
// a utility to display a bitstring
public static String bitStringToDisplayString( boolean[] in ) {
StringBuffer buff = new StringBuffer();
for ( int i = 0; i < in.length; i++ ) {
buff.append( in[i] ? '1' : '0' );
if ( i % 100 == 0 && i != 0 ) buff.append( '\n' );
}
return buff.toString();
}
// #P[P(n)->P(n)^2] = [zeros(n-1) * (P(n)^2 - P(n))] / P(n-1)#
// #P_Corrected[P(n)->P(n)^2] = {[zeros(n-1) * (P(n)^2 - P(n))] / P(n-1)#} + 2 ^ (#P[P(n)->P(n)^2] / 100)
// this is the number of primes between P(n) and P(n)^2
public static long numberPrimesBetweenPnAndPnSquared(int n, boolean addCorrection)
{
if(n<2)
return -1; //error
long Pn = P(n);
long PnSquared = Pn*Pn;
int primorialIndex = n-1;
double result = ((double)(zeros(n-1) * (PnSquared-Pn)));
// divide through by the primorial(n-1)
while(primorialIndex>0)
{
result /=P(primorialIndex);
primorialIndex--;
}
// my P(n) function omits 2 so we'll add it back into the primorial here
result /= 2;
if(addCorrection)
{
double nDouble = (double)n;
double correction = Math.log10(nDouble)*0.145348;
nDouble *= correction;
double nDoubleSquared = nDouble*nDouble;
long nDoubleSquaredLong = Math.round(nDoubleSquared);
result -= nDoubleSquaredLong;
}
return Math.round(result);
}
public static long numberPrimesBetweenPnMinusOneSquaredAndPnSquared(int n, boolean correct)
{
if(n<2)
return -1; //error
long Pn = P(n);
long PnSquared = Pn*Pn;
long PnMinusOne = P(n-1);
long PnMinusOneSquared = PnMinusOne * PnMinusOne;
int primorialIndex = n;
double result = ((double)(zeros(n) * (PnSquared-PnMinusOneSquared)));
// divide through by the primorial(n-1)
while(primorialIndex>0)
{
result /=P(primorialIndex);
primorialIndex--;
}
// my P(n) function omits 2 so we'll add it back into the primorial here
result /= 2;
if(correct)
{
double nDouble = (double)n;
double correction = Math.log10(nDouble)*0.145348;
nDouble *= correction;
double nDoubleSquared = nDouble*nDouble;
long nDoubleSquaredLong = Math.round(nDoubleSquared);
result -= nDoubleSquaredLong;
}
return Math.round(result);
}
public static long numberTwinsBetweenPnAndPnSquared(int n, boolean addCorrection)
{
if(n<2)
return -1; //error
long Pn = P(n);
long PnSquared = Pn*Pn;
int primorialIndex = n-1;
double result = ((double)(twins(n-1) * (PnSquared-Pn)));
// divide through by the primorial(n-1)
while(primorialIndex>0)
{
result /=P(primorialIndex);
primorialIndex--;
}
// my P(n) function omits 2 so we'll add it back into the primorial here
result /= 2;
if(addCorrection)
{
double nDouble = (double)n;
double correction = Math.log10(nDouble)*0.058652;
nDouble *= correction;
double nDoubleSquared = nDouble*nDouble;
long nDoubleSquaredLong = Math.round(nDoubleSquared);
result -= nDoubleSquaredLong;
}
return Math.round(result);
}
public static long numberTripletsBetweenPnAndPnSquared(int n, boolean addCorrection)
{
if(n<3)
return -1; //error
long Pn = P(n);
long PnSquared = Pn*Pn;
int primorialIndex = n-1;
double result = ((double)(triplets(n-1) * (PnSquared-Pn)));
// divide through by the primorial(n-1)
while(primorialIndex>0)
{
result /=P(primorialIndex);
primorialIndex--;
}
// my P(n) function omits 2 so we'll add it back into the primorial here
result /= 2;
if(addCorrection)
{
double nDouble = (double)n;
double correction = Math.log10(nDouble)*0.02881;
nDouble *= correction;
double nDoubleSquared = nDouble*nDouble;
long nDoubleSquaredLong = Math.round(nDoubleSquared);
result -= nDoubleSquaredLong;
}
return Math.round(result);
}
public static long numberQuadrupletsBetweenPnAndPnSquared(int n, boolean addCorrection)
{
if(n<3)
return -1; //error
long Pn = P(n);
long PnSquared = Pn*Pn;
int primorialIndex = n-1;
double result = ((double)(quadruplets(n-1) * (PnSquared-Pn)));
// divide through by the primorial(n-1)
while(primorialIndex>0)
{
result /=P(primorialIndex);
primorialIndex--;
}
// my P(n) function omits 2 so we'll add it back into the primorial here
result /= 2;
if(addCorrection)
{
double nDouble = (double)n;
double correction = Math.log10(nDouble)*0.00718;
nDouble *= correction;
double nDoubleSquared = nDouble*nDouble;
long nDoubleSquaredLong = Math.round(nDoubleSquared);
result -= nDoubleSquaredLong;
}
return Math.round(result);
}
public static long numPrimePnMinusOneSquaredToPnSquared(int n)
{
if(n<2)
return -1; //error
long Pn = P(n);
long PnSquared = Pn*Pn;
long PnMinusOne = P(n-1);
long PnMinusOneSquared = PnMinusOne * PnMinusOne;
long numPrime = 0;
for (long i=PnMinusOneSquared+2; i<PnSquared; i+=2)
if(isPrime(i))
numPrime++;
return numPrime;
}
//NOTE: please provide -Xmx756M -XX:MaxPermSize=512M to the java vm
public static void main( String[] args ) {
long start = System.currentTimeMillis();
// set f(n) = 2n+1
FOfN fOfN = new TwoNPlusOne();
// current iteration
long n = 1;
// number of iterations
final int iterations = 8; // above 8 exceeds Integer.MAX_VALUE
// current Pat(f(n),n)
boolean[] patN = null;
// statistics
long numberOnes = 0;
long numberZeros = 0;
long singletonCandidates = 0;
long twinCandidates = 0;
// iterate generating Pat(f(n),n)'s and displaying statistics
for ( int x = 0; x < iterations; x++ ) {
n = x + 1;
patN = Pat( fOfN, n );
numberOnes = 0;
numberZeros = 0;
singletonCandidates = 0;
twinCandidates = 0;
for ( int i = 0; i < patN.length; i++ ) {
// ones and zeros
if ( patN[i] )
numberOnes++;
else
numberZeros++;
//singleton candidates
if ( ( !patN[i] ) && ( patN[i - 1] ) && ( patN[i + 1 % patN.length] ) ) singletonCandidates++;
//twin candidates
if ( ( !patN[i] ) && ( !patN[i - 1] ) ) twinCandidates++;
}
System.out.println( "---------------------------------------------------------" );
String elemental = elementals.get(new Long(n));
String elementalShifted = new String();
int f0 =(int)(P((int)n)-1)/2;
for(int s=0;s<elemental.length();s++)
{
if(s+1==f0)
elementalShifted+='1';
else
elementalShifted+='0';
}
System.out.println( "Elemental(2f0+1,f0="+f0+") = " + elemental + " -- shifted to align with f0 --> "+elementalShifted );
if ( x < 5 )
System.out.println( "Pat(" + fOfN.getDescription() + ",n=" + n + ") = " + bitStringToDisplayString( patN ) );
else
System.out.println( "Pat(" + fOfN.getDescription() + ",n=" + n + ") = TOO BIG!" );
System.out.println( "Size = " + patN.length );
System.out.println( "Number of 1's = " + numberOnes + "; " + numberOnes + "/" + patN.length + " = " + ( (double)numberOnes / (double)patN.length ) );
System.out.println( "Number of 0's = " + numberZeros + "; " + numberZeros + "/" + patN.length + " = " + ( (double)numberZeros / (double)patN.length ) );
System.out.println( "Total Candidates= " + ( singletonCandidates + twinCandidates ) );
System.out.println( "Singleton Candidates = " + singletonCandidates + "; " + singletonCandidates + "/"
+ ( singletonCandidates + twinCandidates ) + " = "
+ ( (double)singletonCandidates / (double) ( singletonCandidates + twinCandidates ) ) );
System.out.println( "Twin Candidates = " + twinCandidates + "; " + twinCandidates + "/"
+ ( singletonCandidates + twinCandidates ) + " = "
+ ( (double)twinCandidates / (double) ( singletonCandidates + twinCandidates ) ) );
System.out.println( "---------------------------------------------------------" );
}// for
// examine the ones(n) and zeros(n) functions
System.out.println( "IT IS ALSO POSSIBLE TO ALGORITHMICALLY DETERMINE THE # OF ONES AND ZEROS AS OUTLINED ON MY WEBSITE." );
for ( int x = 2; x < 15; x++ ) {
long ones = ones( x );
long zeros = zeros( x );
System.out.println( "n=" + x + "; Ones->" + ones + " Zeros->" + zeros + " zeros/(ones+zeros) = "
+ ( (double)zeros ) / (double) ( ones + zeros ) );
}
System.out.println( "---------------------------------------------------------" );
// compare with actual values of primes:oddNumbers between P(n) and P(n)^2
// System.out.println("Long.MAX_VALUE="+Long.MAX_VALUE);
System.out.println( "COMPARE THE ABOVE VALUES TO THE NUMBER OF PRIMES/ODD BETWEEN P(n)->P(n)^2" );
System.out.println( "NOTE: P(n)->P(n)^2 compares to n-1 above because (Pat(n-1)) is in effect between P(n)->P(n)^2)" );
// a map to store n->numPrime for comparison later with #P[P(n)->P(n)^2]
Map<Long,Long> nToNumPrime = new HashMap<Long,Long>();
Map<Long,Long> nToNumTwin = new HashMap<Long,Long>();
Map<Long,Long> nToNumTrip = new HashMap<Long,Long>();
Map<Long,Long> nToNumQuad = new HashMap<Long,Long>();
for ( int x = 1; x < 80; x++ ) {
long thisPrime = P( x );
long thisPrimeSquared = thisPrime * thisPrime;
long numPrime, numOdd, numTwin, numTrip,numQuad;
numPrime = 0;
numTwin = 0;
numOdd = 0;
numTrip=0;
numQuad=0;
for ( long j = thisPrime + 2; j < thisPrimeSquared; j += 2 ) {
if ( isPrime( j ) ) numPrime++;
if ( isPrime( j ) && isPrime(j-2) && (j>3) ) numTwin++;
if ( isPrime( j ) && isPrime(j-4) && isPrime(j-6) && (j>5) ) numTrip++;
if ( isPrime( j ) && isPrime(j-2) && isPrime(j-6) && isPrime(j-8) && (j>9) ) numQuad++;
numOdd++;
}
nToNumPrime.put(new Long(x),new Long(numPrime));
nToNumTwin.put(new Long(x),new Long(numTwin));
nToNumTrip.put(new Long(x),new Long(numTrip));
nToNumQuad.put(new Long(x),new Long(numQuad));
System.out.println( "P(" + x + ")->P(" + x + ")^2 : " + thisPrime + "->" + thisPrimeSquared
+ " numPrime/numOdd = " + numPrime + "/" + numOdd + " = " + ( (double)numPrime / (double)numOdd ) );
}
// examining the #P[P(n)->P(n)^2] formula
System.out.println( "---------------------------------------------------------" );
System.out.println( "EXAMINING THE #P[P(n)->P(n)^2] AND #P_Corrected[P(n)->P(n)^2] FORMULAE" );
// anything more than 15 overflows double
for ( int x = 2; x < 15; x++ ) {
System.out.println( "#P[P(" + x + ")->P(" + x + ")^2] = " + numberPrimesBetweenPnAndPnSquared( x, false )
+ "; #P_Corrected[P(" + x + ")->P(" + x + ")^2] = " + numberPrimesBetweenPnAndPnSquared( x, true )
+ "; actual number primes in this interval = " + nToNumPrime.get( new Long( x ) ) );
}
// examining the #P[P(n-1)^2->P(n)^2] formula
System.out.println( "---------------------------------------------------------" );
System.out.println( "EXAMINING THE #P[P(n-1)^2->P(n)^2] FORMULA" );
// anything more than 14 overflows double
for ( int x = 2; x < 14; x++ ) {
System.out.println( "#P[P(" + (x-1) + ")^2->P(" + x + ")^2] = " + numberPrimesBetweenPnMinusOneSquaredAndPnSquared( x, false)
+ "; #P_Corrected[P(" + (x-1) + ")^2->P(" + x + ")^2] = " + numberPrimesBetweenPnMinusOneSquaredAndPnSquared( x, true)
+ "; actual number primes in this interval = " + PatN.numPrimePnMinusOneSquaredToPnSquared( x ) );
}
// 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" );
// anything more than 15 overflows double
for ( int x = 2; x < 15; x++ ) {
System.out.println( "#Twins[P(" + x + ")->P(" + x + ")^2] = " + numberTwinsBetweenPnAndPnSquared( x, false )
+ "; #Twins_Corrected[P(" + x + ")->P(" + x + ")^2] = " + numberTwinsBetweenPnAndPnSquared( x, true )
+ "; actual number twins in this interval = " + nToNumTwin.get( new Long( x ) ) );
}
// 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" );
// anything more than 15 overflows double
for ( int x = 3; x < 15; x++ ) {
System.out.println( "#Triplets[P(" + x + ")->P(" + x + ")^2] = " + numberTripletsBetweenPnAndPnSquared( x, false )
+ "; #Triplets_Corrected[P(" + x + ")->P(" + x + ")^2] = " + numberTripletsBetweenPnAndPnSquared( x, true )
+ "; actual number triplets in this interval = " + nToNumTrip.get( new Long( x ) ) );
}
// 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" );
// anything more than 15 overflows double
for ( int x = 3; x < 15; x++ ) {
System.out.println( "#Quadruplets[P(" + x + ")->P(" + x + ")^2] = " + numberQuadrupletsBetweenPnAndPnSquared( x, false )
+ "; #Quadruplets_Corrected[P(" + x + ")->P(" + x + ")^2] = " + numberQuadrupletsBetweenPnAndPnSquared( x, true )
+ "; actual number quadruplets in this interval = " + nToNumQuad.get( new Long( x ) ) );
}
long finish = System.currentTimeMillis();
System.out.println("Execution Time = "+ (finish-start)/1000+ "seconds.");
}
}