Goldbach’s Other Conjecture
June 7, 2016
Although there are other ways to do this, we solve the problem by generating the double-squares, then checking if the difference to the target number is prime. The sequence of double-squares is 0, 2, 8, 18, 32, …, so starting from 0 we walk through the sequence by adding 1*2, 3*2, 5*2, 7*2, …:
(define (goldbach n) (let loop ((dsq 0) (k 1)) (if (< n dsq) (list) (if (prime? (- n dsq)) (list (- n dsq) (sqrt (/ dsq 2))) (loop (+ dsq k k) (+ k 2))))))
Then, to find all the numbers that refute Goldbach’s other conjecture, we write:
> (do ((n 3 (+ n 2))) (#f) (let ((g (goldbach n))) (when (null? g) (display n) (newline)))) 5777 5993
That program quickly produces the two results you see above, then it will run for a long time producing no further results, since it is now conjectured that those are the only two counter-examples to the conjecture. See A060003 for more information, and especially the link given there to the paper by Hodges.
You can run the program at http://ideone.com/88RZja.
function Goldbach(x::Int64) # x is odd
P = primes(x)
for p in P
z = sqrt(x – p)
if z == round(z)
return true
end
end
return false
end
function main(n::Int64 = 1000)
for i = 1:n
x = 2 * round(Int64, 10000*rand()) + 1
if !Goldbach(x)
return x
end
end
return -1
end
It would be interesting to see how this is implemented in other languages.
A generator in Python.
June 7th, 2016.c:
Output:
On an Apple Power Mac G4 (AGP Graphics) (450MHz processor, 1GB memory) to run the solution took:
approximately twenty-two seconds on Mac OS 9.2.2 (International English) (the solution interpreted using Leonardo IDE 3.4.1);
approximately one second on Mac OS X 10.4.11 (the solution compiled using Xcode 2.2.1).
(I’m just trying to solve the problems posed by this ‘site whilst I try to get a job; I’m well aware that my solutions are far from the best – but, in my defence, I don’t have any traditional qualifications in computer science :/ )