The Goldbach Conjecture states that every even integer greater than two can be expressed as a sum of two primes.
I programmed my C64 in Basic to ask the question “How many ways can a particular even integer be expressed as the sum of two primes?” So, for instance, the number 10 can be expressed as 3+7 or as 5+5, so two ways. The number 12 can be expressed as 5+7, so only one way. The number 22 can be expressed as 11+11 or as 19+3 or as 17+5, so three ways.
I left the program running for twelve hours, to calculate the Goldbach partitions of all even integers from six to one thousand. I’m very sure that there are much more efficient routines, which would run faster, but it is at least clear that it can be done.
Note that the Goldbach conjecture is not proven. The Wikipedia article here states that the conjecture has been tested by computers for numbers up to 4 x 10^18. But I only went as high as 1000.
Here is a plot of my results (not on the C64, but rather using gnuplot on Windows.
And here is the code:
50 qm = 1000 100 rem get primes up to 1000 200 dim p%(400) 220 p%(1) = 2 230 pc = 1 240 n = 3 300 for i = 1 to pc 310 w = n/p%(i) 320 if w = int(w) then 400 330 next i 340 pc = pc + 1 350 p%(pc) = n 355 print n 400 for i = 1 to 1: next i: n = n+1 410 if n < qm then goto 300 1000 rem get golbach numbers 1010 dim gb%(501) 1020 rem gb%(1) = 0 and gb%(2) = 0 1030 rem because 2 and 4 have no 1040 rem goldbach partitions 1050 gb%(1) = 0 : gb%(2) = 0 1060 q2 = int(qm/2) 1100 for m = 3 to q2 1110 n = m*2 1120 ct = 0 1130 for i = 1 to pc 1140 if p%(i) > n then goto 1200 1150 pr = n - p%(i) 1160 pf = 0 1162 for j = 1 to pc 1164 if p%(j) = pr then pf = 1:goto 1195 1166 if p%(j) > pr then goto 1200 1168 next j 1195 if pf = 1 then ct = ct + 1 1200 for j = 1 to 1:nextj:next i 1210 if (ct/2) <> int(ct/2) then ct = ct + 1 1220 ct = int(ct/2) 1250 print n,ct 1260 gb%(m) = ct 1300 next m 2000 open 2,8,2,"@:goldlist,s,w" 2010 for q = 1 to int(qm/2) 2020 print#2,q*2,gb%(q) 2030 next q 2040 close 2
Paul's Notebook 