Prime Patterns

The title "prime pattern" is a misnomer. Prime numbers, by their nature, have no pattern. A prime number is simply a number that is not a composite. A prime number is defined as a positive integer that is divisible only by itself and one. The set of prime numbers is what remains after you remove the composites from the set of natural numbers.

Primes are more of an anti-pattern than a pattern. I made the illusion earlier that prime numbers are transcendental. Mathematicians use the word transcendental to refer to numbers like pi and Euler's constant. Like irrational numbers, transcendental numbers cannot be expressed as a ratio between two integers. Even more amazing, transcendental numbers cannot be expressed with a finite algebraic equation.

Now, I suspect that the prime numbers have this same behavior. I doubt anyone will ever find a finite algebraic equation to generate the primes. Any equation made with a finite number of exponents, additions and multiplications would involve a repetition at some finite level. The primes, however, transcend such repetitious behavior.

To create a list primes, we create a program called a sieve. Sieves calculate composites. We assume the remainder to be prime. Prime sieves are self-referential. A prime sieve needs to look at the previous iterations of the sieve to determine which numbers are prime. Prime sieve programs often include recursive loops.

In retrospect, I should have called this chapter "Composite Patterns," but I have already referred to the name Prime Patterns in two places. I am simply too lazy to fix my arrows. In any case, the title "Prime Patterns" has a nice ring, and is more likely to be the subject of an internet search.

Infinite Sieves

The easiest sieve to discuss is the infinite sieve. To create an infinite sieve you first remove all the multiples of 2, then remove all the multiples of 3, then remove all the multiples 5, etc.. Infinite sieves have the one disadvantage of being impossible to execute. It is impossible to do an infinite number of things.

The next easiest way to create a sieve is to define a maximum number, then remove all the multiples of 2, 3, 5 ... that are between 1 and the maximum number. Since you can chose the size of the sieve, I call this an arbitrarily large sieve.

The problem with an arbitrarily large sieve is that it is finite by nature. I want a sieve that executes in finite steps but is potentially infinite. So, I created the Prime Pattern Sieve that I discuss below. The prime pattern sieve calculates a finite sets of composites with each iteration. The sieve is efficient in that it never calculates the same composite number twice. The most interesting thing is that it creates interesting patterns that we can use to discuss the distribution of the primes, the Goldbach conjecture and the twin prime conjectures.

The sieve gets large quickly; when programming the sieve, it is still best to indicate a maximum number; however, mathematicians can imagine the sieve executing forever.

Euler and the Zeta Function

The most famous infinite sieve is credited to Euler. Euler started with the zeta function. The zeta function lists the reciprocals of the integers to the s power. I display a brief overview below (I use the carat ^ as the power operator. x^a means x to the power of a):


zeta(s) = 1 + 1/2^s + 1/3^s + 1/4^s + 1/5^s + 1/6^  + 1/7^ + 1/8^s + 1/9^s + ... + 1/x^s ....

Euler found a clever trick where he could decompose the zeta function into a function involving primes. He starts with the zet function then subtracts 1/2^s times the zeta function. From this he would subtract 1/3^s times the remainder. He would repeat the process for all of the primes. This method for decomposing the zeta function looks like (the nth row is produced by multiply the n-1 row by 1/p^s, where is the nth prime.):


row1 zeta(s)      = 1 + 1/2^s + 1/3^s + 1/4^s + 1/5^s + 1/6^  + 1/7^ + 1/8^s + 1/9^s + 1/10^s ...
row2 1/2^s*row1=        1/2^s +         1/4^2 +         1/6^2          1/8^s +         1/10^2 ...
row3 1/3^s*row2=                1/3^s +                                        1/9^2 +        ...
row4 1/5^s*row3=                                1/5^s + ...
...     

The method is clearer if you just look at the exponents:

Row Prime  Extension
1   1      1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 ...
2   2         2     4     6     8    10    12    14    16 ...
3   3            3                 3                15
4   5                  5                                  ... 25 ...
5   7                        7                            ... 49 ... 
...

Euler's sieve decomposes the zeta function. Performing the demcomposition multiple times, you end up with an equation that looks something like:

[(1 - 1/2^s)*(1 - 1/3^s)*(1 - 1/5^s) ... (1 - 1/p^s)* ...] * zeta(s) = 1

To clean up the equation, divide both sides of the equation by [(1 - 1/2^s)*(1 - 1/3^s)*(1 - 1/5^s) ... (1 - 1/p^s)* ...] and you edn up with a handy representation.

zeta(s) = 1/[(1 - 1/2^s)*(1 - 1/3^s)*(1 - 1/5^s) ... (1 - 1/p^s)* ...]

This function is interesting in that it shows a relation between the zeta function and the primes.

Prime Pattern Sieve

In this article, I discuss creating a Java program for the sieve. You can also create this sieve with pencil and paper. For that matter, I think the pencil and paper result gives students a better idea of how prime numbers works. The goal of the sieve is to mark out composites. The algorithm for the sieve is simple. It repeats the pattern" 

Step A: Find next highest Prime Number
Step B: Make p copies of the pattern.
Step C: Mark all the multiples of p as prime (Note, I only need to mark numbers that are a multiple of p and and number greater than p.
Loop Back to Step A.

In this pattern, I am interested in creating a large binary string that indicates if a number is a composite. If the nth number is a composite, the nth digit in the string is a 1, otherwise it is 0. I start with the integer 1. It is not a composite, so I leave it marked as 0. 0 is the first pattern.

0

The next prime number is 2. I repeat the pattern 0 twice. This gives me 00. I mark the second item as a multiple of 2. The pattern 01 indicates that the first entry is not a composite. The second entry is a multiple of 2.

01

The next prime after 2 is 3. I repeat the pattern 01 three time. This yields: 010101. I mark out the multiples of three. The pattern is now 011101. The next number is five. I repeat the pattern 5 times. Notice that I only have to mark the numbers 1*5 and 5*5 from the pattern.

123456
011101

The table below shows the progression of the first three patterns.

p pattern
1 0
2 0X
3 01X101
5 0111X1 011101 011101 011101 X11101

The next prime is 7. I copy the pattern 7 times. Then remove the multiples of 7. Notice that I only need to mark out the multiples of 7 and the numbers marked as zero in the prior iteration of the pattern (011111 011101 011101 011101 011101 111101). This is the iteration for 7:

011111 X11101 011101 011101 111101
011111 011101 011101 X11101 111101
011111 011101 0111X1 011101 111101
X11111 011101 011101 011101 1111X1
011111 011101 X11101 011101 111101
011111 0111X1 011101 011101 111101
011111 011101 011101 0111X1 111101

n = nth prime, 
p=value of prime, 
size =size of the sieve.

n p size
1 2  2
2 3  6
3 5  30
4 7  210
5 11 2310
6 13 30030
7 17 510510
As you can see the prime sieve gets big quickly. If we have a handy list of prime numbers, it is easy to calculate the size of each iteration of the sieve. The size of the nth iteration of the sieve is the first n prime numbers multiplied together. Multiplying primes together is similar to the factorial. So, I call this function primeFactorial(n)

 I invite the reader to create the first 5 iterations of the sieve by hand on a piece of paper. As you create the sieve, you will start noticing interesting things about the sieves. For one thing, the sieve is essentially symmetrical. If you start the sieve with a one, you will notice that each iteration of the sieve creates a palindrome. The pattern is the same forward and backwards as we see below (I've bolded the center, and show only the center of iteration 7.):

                  1
                 101
               1011101
   1011111011101011101011101111101
 ...11111101110101110101110111111...

The sieve shows us that there are often large blocks of consecutive composites. Notice that each iteration of the sieve seems begins with a 0 followed by a solid block of 1s and ends with a solid block of 1s followed by a 01. The reason for this is simple. The pattern begins with a block of 1s because we remove the primes in order.

The last item in each pattern is a composite. You calculate the value of the nth iteration of the si It's value is primeFactorial(n). It is the first n primes multiplied together. primeFactorial(n) - 1 is a potentially prime since it cannot be divided by the first n primes. Likewise, it is preceded by a block of p composites (where p is the value of the nth prime). All of these numbers are necessarily divisible by a number between 2 and p.

The junctions between patterns always follow the form:

 ... 0, p 1s, 0, 1, 0, p1s, 0 ...

Twin Candidates

But people don't care about the pattern. They want to know about the twin primes. The junction between each prime pattern creates a potential twin prime. Neither  primeFactorial(n) - 1 nor primeFactorial(n) + 1 are divisible by the first n primes. The junction between patterns creates a twin prime candidate. Not only that, each iteration of the the pattern copies the twin prime candidates from the previous iteration. You can extend the patterns indefinitely; so we see that there is a mechanism that produces an infinite number of twin candidates. Unfortunately, not all of the candidates are primes. Additional iterations of the pattern could invalidate the 

If you can show that some of the twin primes survive subsequent iterations of the sieve, then you would prove the conjecture. To disprove the conjecture, you would need to show that candidates get eliminates. As the prime numbers themselves avoid discernible patterns, I suspect the conjecture to be true, but either case is devilishly difficult to prove.

There is reason to think the conjecture is true. The nth iteration of sieve not only creates one new twin prime candidate. The next iteration of the pattern creates immediately creates p-1 replicas of the candidate, only two of which get eliminated in the multiplication step. The prime pattern iteration creates twin prime candidates faster than it destroys them.

I believe that the most promising method to proving the twin prime conjecture is to study the creation and invalidation of these twin prime candidates.

Being lazy, I tend to want to pick low lying fruits before tempting the difficult stuff.

Sizing the Sieve

We can easily calculate the size of the sieve, and the distribution of each iteration of the sieve. The following table shows the first n primes, the size of the sieve and the number of potential candidates. As you see, each row depends on the values of the previous row.

n p size removed candidates dist twins
0 0          
1 1 1        
2 2 2 1 1 0.5  
3 3 6 1 2 0.3333...  
4 5 30 2 8 0.2666...  
5 7 210 8 48 0.2285...  
6 11 2310 48 480 0.2077...  
7 13 30030 480 5760 0.1918...  
8 17 510510 5760 92160 0.1805...  
9 19 9699690 92160 1658880 0.1710...  
10 23 223092870 1658880 36495360 0.1635...  
n p p-factorial zero(n-1) see below    

The table lists the first 10 iterations of the prime pattern sieve. The column labeled p shows the first 10 primes. The column labeled "size" shows the first n primes multiplied together. 

The column labeled "remove" shows the number of prime candidates removed with the iteration. This column is equal to the number candidates in the previous row.

The column marked candidates is the number of zeros in the binary string representing the nth prime pattern. It is equal to (p-1) times the candidates in the previous row.

The length of the the nth prime pattern is equal to the first n primes multiplied together (p1 * p2 * p3 * p4 * ... * pn). You calculate the number of prime candidates by subtracting one from each of the first n primes and multiplying the results together. (p1-1) *  (p2-1) * (p3-1) * (p4-1) * ... * (pn-1).

This prime candidate sieve is easy to program. 

I will be adding the Java program for this section after I get java installed on this new computer.