Prime Strings, Goldbach and his Evil Twin

The two most famous mathematical conjectures concerning primes are: The Twin Prime Conjecture and the Goldbach Conjecture. The Twin Prime Conjecture speculates that there is an infinite number of primes pairs p1 and p2 such that (p2 - p1 = 2). 

The Goldbach Conjecture stipulates that all even numbers can be written as the sum of two primes.

I am inclined to believe that both conjectures are true. But, like most proofs that involve establishing a truth for an infinite collection, the postulates are devilishly difficult to prove.

I've found that representing the primes with a binary string, makes it is easy to see the relation between the Goldbach and Twin Prime conjectures. A binary string is simply a long string of boolean characters. A boolean character has only two possible values. The boolean value is either on or off, true or false. Computer programmers often express binary strings as a series of 1s and 0s.

To represent the primes as a binary string, I simply look at each number starting with 1. If the number is prime, I record a "1". If not, I record "0". The nth value in this binary string will be 1 if n is prime, else 0.

When discussing the Twin Prime and Goldbach conjectures, I find it easiest to drop the even numbers. To create a binary string that represents the odd integers, I start with a list of dds then record if it is prime:

     1  3  5  7  9 11 13 15 17 19 21 23...
     1  1  1  1  0  1  1  0  1  1  0  1...

NOTE: The number 1 is usually not listed as a prime. When working on Golbach's conjecture, I like to include 1 in the list. Real mathematicians hate pseudo mathematicians like me.

Dropping the even numbers makes it easy to see the twin primes. The twin primes are adjacent to each other. Whenever I see two 1s next to eachother, I know I have a twin prime pair. Just examining the binary string 111101101101..., we can see that the set of twin primes is {(1,3),(3,5),(5,7),(11,13) ...}. The first break in the series of twin primes is between 7 and 9.

Computers are extremely adept at handling long binary strings. In fact, that's what they do all day long. They manipulate large quantities of on and off switches.

A long binary string of primes does not require a great deal of computer storage. In computer lingo, a single on/off switch is called a bit. A group of 8 on/off switches is called a byte. I only need one bit to indicate if a number is prime. That means I only need 125000 bytes to hold the binary string for the first million integers.

We will discuss a program to create such a string in the articles on finite prime sieves. For now, I want to talk about the Goldbach conjecture and twin primes. We will just pretend that I already have a binary string representing the primes.

To quickly generate a list of the twin primes, I can take my long binary string, bit shift it to the right then take the bitand of the two strings (a bitand returns true if both values are true, otherwise it returns false):

    Primes:    111101101101001100111...
    Bit Shift: .111101101101001100111...
    bitand:    .11100101100000100011...

The resulting string is basically a list of all twin primes. To see if a particular number (n) is the first member of a twin, I simply need to find the index of (n+1)/2. If this number is a 1, it is the start of a twin prime. If it is 0; it is not the start of a twin prime.

Essentially, the twin prime conjecture stipulates that the binary string created from the list of twin primes is an infinite non-repeating string. The string does not simply end in with an infinite number of zeros.

We can attack Goldbach's conjecture with a similar technique. Goldbach's conjecture stipulates that all even numbers can be written as the sum of two primes. To test an individual even number x, we can take the string of all primes less than x, invert it and take the bit and with the original string. For example the binary string representing all the primes (including 1) less than 20 is 1111011011. We can simple invert this string and take the bit and of the two strings as follows:

     position         0000011111
                      1357913579

     Prime String:    1111011011
     Inverted String: 1101101111
     bit and:         1101001011

Perhaps the following table is clearer.

P 20-p binary
string
inverted
string
and
1 19 1 1 1
3 17 1 1 1
5 15 1 0 0
7 13 1 1 1
9 11 0 1 0
11 9 1 0 0
13 7 1 1 1
15 5 0 1 0
17 3 1 1 1
19 1 1 1 1

As you see, instead of actually performing addition to check Goldbach's conjecture, I simply check the indices of the prime numbers of two strings to see if they match. This is significantly faster than performing the addition. Understanding how binary strings work can make computer programs that scream.

Sharp students will noticed that the result of bitand is symmetrical. The resulting string is a palindrome. The result reads the same forwards and backwards. If you are writing a computer program to test Goldbach's conjecture, you will find that you only need to do the bit and on the first half of the string. Discovering symmetries can help you optimize your computer code.

You can imagine writing a program that validates Goldbach's Conjecture for the first n integers. The program would create a binary string indicating which digits are prime. It would then curse through through the first n segments of the binary string, doing a bit and with the string and its inverse, to see if the program returns a binary string equal to 0.

I leave this exercise to your imagination and programming skills.

Putting the Two Together

We can see that binary strings help us write programs to check the twin prime and Goldbach conjectures. Playing with the conjectures, it is easy to see how the two conjectures are related.

In the following table, I start with the list of odd primes, I then add multiple rows where I bit shift each item one space. (NOTE: since I do not list the even numbers, I am actually shifting each rows two spaces.)

odd                1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4
numbers  1 3 5 7 9 1 3 5 7 9 1 3 5 7 9 1 3 5 7 9 1 3 5 7 9 ...
------------------------------------------------------------
primes   1 1 1 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 ...
shift 2    1 1 1 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 ...
shift 4      1 1 1 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 ...
shift 6        1 1 1 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 ...
shift 8          1 1 1 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 ...
shift 10           1 1 1 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 1 0 ...
shift 12             1 1 1 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 1 ...
shift 14               1 1 1 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 ...
shift 18                 1 1 1 1 0 1 1 0 1 1 0 1 0 0 1 1 0 ...
shift 20                   1 1 1 1 0 1 1 0 1 1 0 1 0 0 1 1 ...

In the second step, I take the bitand of the shifted rows with the first row. The new string in shift 2 should now show all of the twin primes, the rows in the row labeled shift 4 shows all of the primes that differ by four, the string in the row labeled shift 6 shows the primes that are 6 apart, etc..

(NOTE: I call the row with the primes in it shift 0, taking the bitand of the prime stream and itself yeilds itself.)

odd                1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 ...
numbers  1 3 5 7 9 1 3 5 7 9 1 3 5 7 9 1 3 5 7 9 1 3 5 7 9 ...
------------------------------------------------------------
shift 0  1 1 1 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 ...
shift 2    1 1 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 ...
shift 4      1 1 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 ...
shift 6        1 0 1 1 0 1 1 0 1 1 0 0 0 0 0 1 0 0 1 0 1 0 ...
shift 8          0 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 ...
shift 10           1 1 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 ...
shift 12             1 0 1 1 0 1 1 0 0 1 0 0 0 0 1 1 0 0 0 ...
shift 14               0 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 ...
shift 16                 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 ...
shift 18                   1 0 1 1 0 0 1 0 0 1 0 1 0 0 1 0 ...

The twin prime conjecture says that the string in row shift 2 does not terminate as an infinite string of zeros. My personal speculation is that none of the shifted rows terminate in an infinite string of zeros. I like to think of this statement as the n-prime conjecture. Basically the n-prime conjecture says that there is an infinite number of primes that are n digits apart where n is a positive even number. Of course, people don't need another wild conjecture, they want to know about the Goldbach conjecture.

Well, if you look closely, you can see the Goldbach conjecture in the above table. This is one of those things that is easy to show on a chalk board, but difficult to show in print. You will have to use your imagination to translate the 1s and 0s into information. The items in shift row one show what happens when you add a row to itself. Row two is what happens when you add n and n-2, etc.. 

odds     1   3   5   7   9  11  13  15  17...
--------------------------------------------
shift 0  2   6  10  14  18  22  26  30  34...
shift 2      4   8  12  16  20  24  28  32...
shift 4          6  10  14  18  22  26  30...
shift 6              8  12  16  20  24  28...
shift 8                 10  14  18  22  26...
shift 10                    12  16  20  24...
shift 12                        14  18  22...
shift 14                            16  20...
shift 16                                18...

Pulling some funky magic and shifting this table back a half row, I can realign the table so that each column sums to a particular even number.

odds     1   3   5   7   9  11  13  15  17...
-------------------------------------
primes   2   6  10  14  18  22  26  30  34...
shift 2    4   8  12  16  20  24  28  32  ...
shift 4      6  10  14  18  22  26  30  34...
shift 6        8  12  16  20  24  28  32  ...
shift 8         10  14  18  22  26  30  34...
shift 10          12  16  20  24  28  32  ...
shift 12            14  18  22  26  30  34...
shift 14              16  20  24  28  32  ...
shift 16                18  22  26  30  34...
==========================================
Sum      2 4 6 810121416182022242628303234...

The next table shows just the binary strings.

odd                          1   1   1   1   1   2   2   2 ...
numbers  1   3   5   7   9   1   3   5   7   9   1   3   5 ...
------------------------------------------------------------
primes   1   1   1   1   0   1   1   0   1   1   0   1   0 ...
shift 2    1   1   1   0   0   1   0   0   1   0   0   0   ...
shift 4      1   1   0   1   0   0   1   0   0   1   0   0 ...
shift 6        1   0   1   1   0   1   1   0   1   1   0   ...
shift 8          0   1   1   0   0   1   0   0   1   0   0 ...
shift 10           1   1   0   1   0   0   1   0   0   0   ...
shift 12             1   0   1   1   0   1   1   0   0   1 ...
shift 14               0   1   1   0   0   1   0   0   1   ...
shift 16                 1   1   0   1   0   0   0   0   0 ...
shift 18                   1   0   1   1   0   0   1   0   ...
        ==================================================
sum:     2 4 6 8 1 1 1 2 2 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5 6 
                 0 2 4 6 8 0 2 4 6 8 0 2 4 6 8 0 2 4 6 8 0

Basically, we can now see the relation between the n-prime and Goldbach conjectures. The twin prime conjecture states that binary row in the first row is an infinite decimal. The n-prime conjecture would extends the twin prime conjecture—speculating that all of the rows are infinite decimals.

The Goldbach conjecture states that none of the columns in the table turn into zero valued strings.

We will look more into the process of generating algorithms to create a large prime binary string in the article titled Prime Patterns.

© Kevin Delaney
Index ~ Descriptive Mathematics ~ Next

Record of Revisions
Date Description
6/4/2003 Uploaded.