Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
In this article, we shall be looking at the intriguing Goldbach's Conjecture, one of the best known unsolved problems in mathematics. Later on, in the article, we shall find the Goldbach pairs of all numbers that range from 1000 to 2000.
Table of contents:
- Understanding Goldbach's Conjecture
- Interesting Concepts Related to the Goldbach's Conjecture
- Goldbach's weak Conjecture
- Goldbach Function and Goldbach's comet
- Schnirelmann Density
- Other Contributions
- Algorithm to find the Goldbach Pair of an Even Number
- Implementation of our algorithm
- Space and Time Complexity
- Finding Goldbach pairs of all numbers that range from 1000 to 2000
If you want to check out another interesting conjecture check out, the twin prime conjecture
Understanding Goldbach's Conjecture
A conjecture is a statement or proposition that is widely believed to be true but of which no proof has been found. Conjectures often sound intuitive and can be shown to be true up to large numerical values but are surprisingly hard to prove.
The Goldbach conjecture given by German mathematician, Christian Goldbach states that
Every even whole number greater than 2 is the sum of two prime numbers.
It is relatively easy to check the conjecture for trivial cases: 10 = 5 + 5, 24 = 11 + 13, 36 = 29 + 7. The Goldbach conjecture has been proven to hold for all integers less than 4 * 10^18., although this approach can not solve the conjecture as we can not check for the infinite number of possibilities that exist. Hence the need for a general proof.
According to Donald Knuth,
Goldbach’s conjecture is just, sort of, true because it can’t be false. There are so many ways to represent an even number as the sum of two odd numbers, that as the numbers grow the number of representations grows bigger and bigger. Take a 101010-digit even number, and imagine how many ways there are to write that as the sum of two odd integers. For an n-bit odd number, the chances are proportional to 1/n that it’s prime. How are all of those pairs of odd numbers going to be nonprime? It just can’t happen. But it doesn’t follow that you’ll find a proof, because the definition of primality is multiplicative, while Goldbach’s conjecture pertains to an additive property. So it might very well be that the conjecture happens to be true, but there is no rigorous way to prove it.
Interesting Concepts Related to the Goldbach's Conjecture
Goldbach's weak Conjecture
The weak form of Goldbach's Conjecture states that
Every odd number greater than 5 can be expressed as the sum of three primes.
It is known as the weak Goldbach Conjecture because a proof of the stronger form(i.e Goldbach's conjecture) will implicitly prove it to be true. Goldbach's weak conjecture is much easier to find a proof for, in fact, a proof has been proposed by Harald Helfgott and is now widely accepted in the math community.
Goldbach Function and Goldbach's comet
If we have a function g(E) where E is defined for even integers greater than 2, then g(E) is defined as the number of ways E can be expressed as the sum of two primes. the function g(E) is called the Goldbach function.
For example, g(10) = 2 because 10 can only be expressed as the sum of two primes in two ways (3 + 7 and 5 + 5).
Goldbach's Comet is then the name given to the plot of the Goldbach function.
Schnirelmann Density
Lev Schnirelmann came up with a proof that says that any natural number greater than 1 can be written as the sum of not more than C prime numbers, where C is a computable constant. This has relevant implications for Goldbach conjecture, as it manages to show a weaker result that indeed every integer greater than 1 is bound by a finite number of primes.
Other Contributions
Oliver Ramare in 1995 showed that every number n >= 4 is the sum of at most 6 primes.
Chen Jingrun in 1973 showed that every sufficiently large even number can be written as the sum of either 2 primes or a prime and a semiprime.
Hugh Montogomery and Robert Charles Vaughan showed that most even numbers are expressible as the sum of two primes.
Algorithm to find the Goldbach Pair of an Even Number
In order to find a pair of primes that sum up to an even number, N. There are two steps involved:
Step 1:
We have to first find all the prime numbers up to the number N. There are a couple of ways to find prime numbers. The most naive approach involves two loops; for every number up to N, divide each by every number smaller than itself to check if it is prime. One of the most efficient methods of which we shall be using is The Sieve of Eratosthenes (runs in O(n log logn) time).
Step 2:
We then iterate through the list of primes and try to see if we can find two prime numbers (x,y) such that x is in primes and N - x = y is also in primes.
Implementation of our algorithm
def findPrimes(N):
"""
Uses The Sieve of Eratosthenes to find the first prime numbers up to N.
input: N, a natural number
returns: A set of the first prime numbers up to N
"""
# Initialise a boolean array where the index maps to a number up to n
# All the numbers are first initialised as True
# Eventually after the sieve is run, isPrime[i] will be False if i is
# composite
isPrime = [True for x in range(N + 1)]
candidate = 2
# starting from 2 iterate and mark all the multiples
while candidate ** 2 <= N:
if isPrime[candidate]:
for k in range(candidate * 2, n + 1, candidate):
isPrime[k] = False
candidate += 1
# Use boolean array to filter only the prime numbers to a new List
onlyprimes = [i for i in range(2, len(isPrime)) if isPrime[i]]
# Convert to a set for constant lookup operations and return
return set(onlyprimes)
def getGoldbachPair(n):
"""
Return the first Goldbach pair it finds from a set of prime numbers if n is even else return an empty tuple.
below implementation can be easily modified to find all the Goldbach pairs
"""
# check if the number is even
if n % 2 != 0:
return ()
primes = findPrimes(n)
for prime in primes:
other_prime = n - prime
if other_prime in primes:
return (prime, other_prime)
Space and Time Complexity
FindPrimes has a time complexity of O(n log log n) as it implements The Sieve of Eratosthenes. getGoldbachPair also has a time complexity of O(n log log n) as the findPrime call dominates the for loop that is doing n amount of work (because the primes are stored in a set, so each lookup takes contant time)
Finding Goldbach pairs of all numbers that range from 1000 to 2000
We already have all the tools we need to be able to get our answer. We can modify the above getGoldbachPair function to handle a range of numbers.
def getAllGoldbachPairsInRange(start, stop):
"""
prints the goldbach pairs of numbers in a range
"""
# get all the total primes just once
primes = findPrimes(stop)
# use to control the printing
tabcount = 1
for number in range(start, stop):
# check if even
if number % 2 != 0:
continue
for prime in primes:
other_prime = number - prime
if other_prime in primes:
print(f"({number}: {prime}, {other_prime}),", end=" ")
break
# Some printing logic, add a newline after printing every 4th result
if tabcount % 4== 0:
print()
tabcount += 1
Output:
printAllGoldbachPairsInRange(start, stop)
(1000: 3, 997), (1002: 5, 997), (1004: 7, 997), (1006: 23, 983),
(1008: 521, 487), (1010: 523, 487), (1012: 3, 1009), (1014: 5, 1009),
(1016: 3, 1013), (1018: 5, 1013), (1020: 7, 1013), (1022: 3, 1019),
(1024: 3, 1021), (1026: 5, 1021), (1028: 7, 1021), (1030: 521, 509),
(1032: 11, 1021), (1034: 3, 1031), (1036: 3, 1033), (1038: 5, 1033),
(1040: 7, 1033), (1042: 3, 1039), (1044: 5, 1039), (1046: 7, 1039),
(1048: 1031, 17), (1050: 1031, 19), (1052: 3, 1049), (1054: 3, 1051),
(1056: 5, 1051), (1058: 7, 1051), (1060: 1031, 29), (1062: 1031, 31),
(1064: 3, 1061), (1066: 3, 1063), (1068: 5, 1063), (1070: 7, 1063),
(1072: 3, 1069), (1074: 5, 1069), (1076: 7, 1069), (1078: 1031, 47),
(1080: 1033, 47), (1082: 13, 1069), (1084: 1031, 53), (1086: 1033, 53),
(1088: 1021, 67), (1090: 3, 1087), (1092: 5, 1087), (1094: 3, 1091),
(1096: 3, 1093), (1098: 5, 1093), (1100: 3, 1097), (1102: 5, 1097),
(1104: 7, 1097), (1106: 3, 1103), (1108: 5, 1103), (1110: 7, 1103),
(1112: 3, 1109), (1114: 5, 1109), (1116: 7, 1109), (1118: 1039, 79),
(1120: 3, 1117), (1122: 5, 1117), (1124: 7, 1117), (1126: 3, 1123),
(1128: 5, 1123), (1130: 7, 1123), (1132: 3, 1129), (1134: 5, 1129),
(1136: 7, 1129), (1138: 1031, 107), (1140: 1031, 109), (1142: 1033, 109),
(1144: 1031, 113), (1146: 1033, 113), (1148: 1039, 109), (1150: 1049, 101),
(1152: 521, 631), (1154: 3, 1151), (1156: 3, 1153), (1158: 5, 1153),
(1160: 7, 1153), (1162: 1031, 131), (1164: 521, 643), (1166: 3, 1163),
(1168: 5, 1163), (1170: 7, 1163), (1172: 1033, 139), (1174: 3, 1171),
(1176: 5, 1171), (1178: 7, 1171), (1180: 1031, 149), (1182: 1031, 151),
(1184: 3, 1181), (1186: 5, 1181), (1188: 7, 1181), (1190: 3, 1187),
(1192: 5, 1187), (1194: 7, 1187), (1196: 3, 1193), (1198: 5, 1193),
(1200: 7, 1193), (1202: 1039, 163), (1204: 3, 1201), (1206: 5, 1201),
(1208: 7, 1201), (1210: 1031, 179), (1212: 1031, 181), (1214: 1033, 181),
(1216: 3, 1213), (1218: 5, 1213), (1220: 3, 1217), (1222: 5, 1217),
(1224: 7, 1217), (1226: 3, 1223), (1228: 5, 1223), (1230: 7, 1223),
(1232: 3, 1229), (1234: 3, 1231), (1236: 5, 1231), (1238: 7, 1231),
(1240: 3, 1237), (1242: 5, 1237), (1244: 7, 1237), (1246: 17, 1229),
(1248: 521, 727), (1250: 523, 727), (1252: 3, 1249), (1254: 5, 1249),
(1256: 7, 1249), (1258: 1031, 227), (1260: 1031, 229), (1262: 3, 1259),
(1264: 5, 1259), (1266: 7, 1259), (1268: 1039, 229), (1270: 1031, 239),
(1272: 1031, 241), (1274: 1033, 241), (1276: 17, 1259), (1278: 521, 757),
(1280: 3, 1277), (1282: 3, 1279), (1284: 5, 1279), (1286: 3, 1283),
(1288: 5, 1283), (1290: 7, 1283), (1292: 3, 1289), (1294: 3, 1291),
(1296: 5, 1291), (1298: 7, 1291), (1300: 3, 1297), (1302: 5, 1297), ...
With this article at OpenGenus, you must have the complete idea of Goldbach's Conjecture.
