Goldbach-Conjecture

173 days ago by jgdelk

Introduction:

The Goldbach Conjecture was proposed to Leonhard Euler by Christian Goldbach in a letter in 1742.  Goldbach proposed that each even number greater than two can be expressed as the sum of two prime numbers.  Even though it has been over a century since this statement has been made, it is still an unproven statement.  Although this statement has been unproven, there has been extensive research into the subject.  So far, no counter example has been found.  For this report, the conjecture will be investigated with the hope of uncovering new information that can bring a greater understanding of the problem being researched.  

Experimental Methods and Results:

The first goal of the research project is to develop a function to prove the Goldbach conjecture up to some given value, let's say $N$.  The code below does just that.

# Define an upper limit to investigate N = 100 
       

Since Goldbach's conjecture is concerned with the summation of primes, a list of primes up to $N$ would be helpful to have for the code.  A list of prime numbers is generated below.

# Generate a list of prime numbers up to N def generatePrimeList(maximum): primeList = [] for num in srange(1, maximum + 1): if num.is_prime(): primeList.append(num) return primeList # Print ever prime number up to 100 primeList = generatePrimeList(N) print([prime for prime in primeList if prime <= 100]) 
       
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
71, 73, 79, 83, 89, 97]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Now, every possible combination of these prime numbers will be generated by iterated through the list of prime numbers.

sumList = [] pairList = [] for p1 in primeList: for p2 in primeList: sumList.append(p1 + p2) pairList.append([p1, p2]) # Print sumList values up to N if they are even print(set([sum for sum in sumList if ((sum % 2 == 0) and (sum <= N))])) 
       
set([4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36,
38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72,
74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100])
set([4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100])

A quick inspection reveals that for $N = 100$, every even value is found.  Note that $2$ is ignored since $2 = 1 + 1$, and $1 is not a prime, nor is it composite.  

With this results, the points that are the sum of primes are plotted.  An interesting grid pattern is seen.  Using the methodology above, a function to validate the results for some arbitrary upper limit of $N$ will be developed.  

list_plot(pairList) 
       
# Function to validate the Goldbach conjecture up to some value of N N = 100 def validateGoldbachConjecture(maximum): goldbachConjectureHolds = False # Generate a list of primes primeList = [] for num in srange(1, maximum + 1): if num.is_prime(): primeList.append(num) # Generate a list of two prime sums sumList = [] pairList = [] for p1 in primeList: for p2 in primeList: pairList.append([p1, p2]) sumList.append(p1 + p2) # Find all the even sums less than the maximum sumSet = set([sum for sum in sumList if ((sum % 2 == 0) and (sum <= maximum))]) # Generate a set of all even numbers evenSet = set([i for i in range(3, maximum + 1) if ((i % 2 == 0) and (i <= maximum))]) if sumSet == evenSet: goldbachConjectureHolds = True print("The Goldbach conjecture holds.") return goldbachConjectureHolds, pairList, sumList # Test for N N = 1000 holds, pairs, sums = validateGoldbachConjecture(N) 
       
The Goldbach conjecture holds.
The Goldbach conjecture holds.

The function was used to generate a plot for the values that are the sum of two prime numbers.  The points are shown in the plot below for the value of $N = 100,000$

list_plot(pairs) 
       

For a larger value of $N$, a large almost plaid like shape pattern appears.  It seems to be symmetric across the line $y = x$, but there is not clear pattern as to why the lines show up where they do.  They somewhat resemble logarithmic plotting paper, but they are not an exact match by any means.  This plot raises another question. Each point represents a sum, but it is possible that the same sum is represented by multiple points.  How many ways can each even number be expressed as a sum of two primes.

The code below investigates this question, by modifying the previous function to count the number of ways each even number can be expressed as the sum of two primes.  This data can be used to generate more plots, which can provide more clues as to what should be investigated.  

# Function to validate the Goldbach conjecture up to some value of N def goldbachConjectureCounts(maximum): countList = [0 for i in range(0, maximum + 1)] retList = [] primeList = [] for num in srange(1, 2 * (maximum + 1)): if num.is_prime(): primeList.append(num) for p1 in primeList: for p2 in primeList: sum = p1 + p2 #print(p1, p2, sum) if sum <= maximum: countList[sum] += 1 for i in range(maximum + 1): if i % 2 == 0: retList.append([i, countList[i]]) return retList # Test results = goldbachConjectureCounts(100000) 
       
list_plot(results) 
       

We can analyze this for different residue classes.  For $(mod) 3$, we plot each of the residue classes in a different color.

r0 = [] r1 = [] r2 = [] for element in results: if element[0] % 3 == 0: r0.append(element) elif element[0] % 3 == 1: r1.append(element) elif element[0] % 3 == 2: r2.append(element) 
       
list_plot(r0, color='blue') + list_plot(r1, color='red') + list_plot(r2, color='green') 
       

Below, the same is done for residue classes $(mod) 5$

r0 = [] r1 = [] r2 = [] r3 = [] r4 = [] for element in results: if element[0] % 5 == 0: r0.append(element) elif element[0] % 5 == 1: r1.append(element) elif element[0] % 5 == 2: r2.append(element) elif element[0] % 5 == 3: r3.append(element) elif element[0] % 5 == 4: r4.append(element) 
       
list_plot(r0, color='blue') + list_plot(r1, color='red') + list_plot(r2, color='green') + list_plot(r3, color='orange') + list_plot(r4, color='purple') 
       

Finally, the same is done for residue classes $(mod) 7$

r0 = [] r1 = [] r2 = [] r3 = [] r4 = [] r5 = [] r6 = [] for element in results: if element[0] % 7 == 0: r0.append(element) elif element[0] % 7 == 1: r1.append(element) elif element[0] % 7 == 2: r2.append(element) elif element[0] % 7 == 3: r3.append(element) elif element[0] % 7 == 4: r4.append(element) elif element[0] % 7 == 3: r5.append(element) elif element[0] % 7 == 6: r6.append(element) 
       
list_plot(r0, color='blue') + list_plot(r1, color='red') + list_plot(r2, color='green') + list_plot(r3, color='orange') + list_plot(r4, color='purple')+ list_plot(r5, color='darkgreen') + list_plot(r6, color='black') 
       

From the plot, we see that for each modulus, the values that are congruent to zero for have more ways of being expressed as the sum of twin primes.  This makes sense because these values are divisible by more numbers, which seems to suggest that there is a relationship between the number of ways a number can be factored and the number of ways that it can be expressed as a sum of primes.  The code below will generate the Goldbach's comet plot, but vary the color based on how many prime numbers a number is divisible by.  

results = goldbachConjectureCounts(100000) del results[0]; del results[1] # Remove the first two even numbers (0 and 2) 
       
maxFactorCount = 0 for i in results: factorCount = len(factor(i[0])) if factorCount > maxFactorCount: maxFactorCount = factorCount print(maxFactorCount) print('Determining hues...') hues=[hue(1, float(len(factor(i[0]))) / maxFactorCount * 0.8, 1) for i in results] print('Generating plot...') plot = list_plot([[0,0]]) for count, color in enumerate(hues): plot += list_plot([results[count]], hue=color) show(plot) 
       
6
Determining hues...
Generating plot...
6
Determining hues...
Generating plot...
 
       

From this plot, it is apparent that the more darker data points (the ones that are divisible by the most primes) are consistently higher than lighter points, which are divisible by less primes.  Thus, there seems to be a clear relationship between the number of primes included in a number's prime factorization, and theh number of ways that it can be expressed as the sum of prime pairs.  However, there is still the stratification phenomenon that has yet to be accounted for.  The plot seems to split into groups, which was ovserved to be related to the residue class that a number belongs to.  It seems that there is a relationship between the divisibility of a number, and number of ways it can be expressed as the sum of two primes.

For the final part of the investigation, the relationship between the Goldbach conjecture and the twin prime conjecture will be studied.  It will be determined if numbers that can be expressed as a sum of twin primes have a special relationship in the plot that was generated previously.

Twin primes are primes that have a difference of two.  The cousin primes and sexy primes are a related set of prime pairs, which have a difference of four and six, respectively. The code below will generate them up to a maximum value.

def findPrimes(max): primeList = [] for i in srange(2, max + 1): if i.is_prime(): primeList.append(i) return primeList def findPrimePairs(primeList, difference): primePairList = [] for i in range(len(primeList)): for j in range(len(primeList)): if (primeList[i] - primeList[j] == difference): primePairList.append([primeList[i], primeList[j]]) return primePairList 
       
primeList = findPrimes(100000) twinPrimePairs = findPrimePairs(primeList, 2) twinPrimeSums = set() for x in twinPrimePairs: twinPrimeSums.add(x[0] + x[1]) cousinPrimePairs = findPrimePairs(primeList, 4) cousinPrimeSums = set() for x in cousinPrimePairs: cousinPrimeSums.add(x[0] + x[1]) sexyPrimePairs = findPrimePairs(primeList, 6) sexyPrimeSums = set() for x in sexyPrimePairs: sexyPrimeSums.add(x[0] + x[1]) 
       

The points that can be expressed as a sum of twin primes are shown below in a darker color.  

results = goldbachConjectureCounts(100000) del results[0]; del results[1] # Remove the first two even numbers (0 and 2) print('Determining hues...') hues = [] for i in results: if (i[0] in twinPrimeSums): hues.append(hue(0.4, 1, 1)) else: hues.append(hue(0.6, 1, 1)) print('Generating plot...') plot = list_plot([[0,0]]) for count, color in enumerate(hues): plot += list_plot([results[count]], hue=color) show(plot) 
       
Determining hues...
Generating plot...
Determining hues...
Generating plot...

The data points that can be expressed as a sum of cousin primes are shown below in a darker color.

results = goldbachConjectureCounts(100000) del results[0]; del results[1] # Remove the first two even numbers (0 and 2) print('Determining hues...') hues = [] for i in results: if (i[0] in cousinPrimeSums): hues.append(hue(0.4, 1, 1)) else: hues.append(hue(0.6, 1, 1)) print('Generating plot...') plot = list_plot([[0,0]]) for count, color in enumerate(hues): plot += list_plot([results[count]], hue=color) show(plot) 
       
Determining hues...
Generating plot...
Determining hues...
Generating plot...

The numbers that can be expressed as sum of sexy primes are shown below in a darker color.

results = goldbachConjectureCounts(100000) del results[0]; del results[1] # Remove the first two even numbers (0 and 2) print('Determining hues...') hues = [] for i in results: if (i[0] in sexyPrimeSums): hues.append(hue(0.4, 1, 1)) else: hues.append(hue(0.6, 1, 1)) print('Generating plot...') plot = list_plot([[0,0]]) for count, color in enumerate(hues): plot += list_plot([results[count]], hue=color) show(plot) 
       
Determining hues...
Generating plot...
Determining hues...
Generating plot...

The darker points are those that can be expressed as the sum of a special type of prime pairs.  This is the twin primes for the first plot, the cousine primes for the second, and the sexy primes for the third and final plot.  There is an interesting behavior seen from these plots.  Goldbach's comet has a gap in the middle, and the twin primes and cousin primes only appear to be found in the top half, while the sexy primes only appear in the bottom half.  This would suggest that there is a relationship between the intervals between the prime values that sum to a given number and the number of ways it can be expressed as the sum of two primes.

Conclusion:

While a proof for the Goldbach conjecture was not found, several interesting discoveries were made.  The first is that that values are congruent to $0 (mod 3)$ tend to have more expressions as the sum of prime numbers than number of similar value.  This led to an invesigation about the relationship between the divisibility of a number and the number of ways it can be expressed as the sum of primes.  It was found that there is a tendency for numbers that are divisible by more primes to be able to be expressed as a sum of primes in more ways than similarly valued numbers.  The final investigation was the relationship between twin, cousin, and sexy prime pairs.  It was found that twin and cousin primes seem to occur above the middle gap in Goldbach's comet, and numbers that can be expressed as the sum of sexy primes appear in the lower half.  While an explanation hasn't been found for this, perhaps further experimentation can shine a light into this phenomenon.