I bought the book Uncle Petros and Goldbach’s Conjecture by Apostolos Doxiadis in my twenties and immediately shared it with my father. The book tells with great charm the story of an elderly and isolated mathematical genius who tries to solve the puzzle that has eluded so many: Goldbach’s conjecture. It seems so simple: “every even number greater than 2 is the sum of two prime numbers” (for example: 3+7 = 10, 13+11 = 24, and so on). This is Goldbach’s conjecture, as he proposed it, as many have tried to prove, and as Uncle Petros undermines his life in his failed attempts to prove one of the most famous unsolved puzzles in number theory.
The book is highly recommended for math enthusiasts, but not exclusively, and it is written with great emotion and evokes identification with its protagonist, the black sheep of the family who tries in vain to gain glory and fears the inevitable decline of his mind.
Unfortunately, Python can’t assist us in proving or disproving Goldbach’s conjecture, but it can demonstrate how to represent any even number between 4 and a specific value, like 200, as the sum of two prime numbers as a programming challenge. As always on this blog, the program isn’t striving to be highly efficient, just simple. There are many optimizations that could be implemented to make the program faster, but again, the preference is to write concise code that gets the job done.
It’s Python time
from itertools import *
sieve = [x for x in range(201)] # originally all the numbers are candidates
sieve[1] = 0 # 1 is not a prime number
for x in range(2,201): # go over all the numbers from 2 to 200
for composite in range(2*x,201,x): # keep the current candidate and eliminate its multiples...
sieve[composite] = 0 # ... by setting them to 0
primes = [x for x in sieve if x != 0] # select all the numbers which were not eliminated
ppairs = combinations_with_replacement(primes, 2) # create a list of prime numbers pairs, with repeated elements
gold = {a+b:(a,b) for (a,b) in ppairs if a+b <= 200 and (a+b) % 2 == 0}
print(sorted(gold.items()))
Output
[(4, (2, 2)), (6, (3, 3)), (8, (3, 5)), (10, (5, 5)), (12, (5, 7)), (14, (7, 7)), (16, (5, 11)), (18, (7, 11)), (20, (7, 13)), (22, (11, 11)), (24, (11, 13)), (26, (13, 13)), (28, (11, 17)), (30, (13, 17)), (32, (13, 19)), (34, (17, 17)), (36, (17, 19)), (38, (19, 19)), (40, (17, 23)), (42, (19, 23)), (44, (13, 31)), (46, (23, 23)), (48, (19, 29)), (50, (19, 31)), (52, (23, 29)), (54, (23, 31)), (56, (19, 37)), (58, (29, 29)), (60, (29, 31)), (62, (31, 31)), (64, (23, 41)), (66, (29, 37)), (68, (31, 37)), (70, (29, 41)), (72, (31, 41)), (74, (37, 37)), (76, (29, 47)), (78, (37, 41)), (80, (37, 43)), (82, (41, 41)), (84, (41, 43)), (86, (43, 43)), (88, (41, 47)), (90, (43, 47)), (92, (31, 61)), (94, (47, 47)), (96, (43, 53)), (98, (37, 61)), (100, (47, 53)), (102, (43, 59)), (104, (43, 61)), (106, (53, 53)), (108, (47, 61)), (110, (43, 67)), (112, (53, 59)), (114, (53, 61)), (116, (43, 73)), (118, (59, 59)), (120, (59, 61)), (122, (61, 61)), (124, (53, 71)), (126, (59, 67)), (128, (61, 67)), (130, (59, 71)), (132, (61, 71)), (134, (67, 67)), (136, (53, 83)), (138, (67, 71)), (140, (67, 73)), (142, (71, 71)), (144, (71, 73)), (146, (73, 73)), (148, (59, 89)), (150, (71, 79)), (152, (73, 79)), (154, (71, 83)), (156, (73, 83)), (158, (79, 79)), (160, (71, 89)), (162, (79, 83)), (164, (67, 97)), (166, (83, 83)), (168, (79, 89)), (170, (73, 97)), (172, (83, 89)), (174, (73, 101)), (176, (79, 97)), (178, (89, 89)), (180, (83, 97)), (182, (79, 103)), (184, (83, 101)), (186, (89, 97)), (188, (79, 109)), (190, (89, 101)), (192, (89, 103)), (194, (97, 97)), (196, (89, 107)), (198, (97, 101)), (200, (97, 103))]
Using the sieve of Eratosthenes, the code initially identifies all prime numbers from 2 to 200. Then, it utilizes the combinations_with_replacement()
function to generate a list of prime number pairs, including repeated elements.
Following that, a concise dictionary comprehension command maps each even number between 2 and 200 to a pair of prime numbers. Dictionary comprehension in Python functions similarly to list comprehension but constructs a dictionary based on a defined set of rules, eliminating the need for lengthy code.
Both combinations_with_replacement()
and dictionary comprehension exemplify Python’s building blocks for concise and powerful code.