## Goldbach’s Other Conjecture

### June 7, 2016

Christian Goldbach (1690-1764) was a Prussian mathematician and contemporary of Euler. One of the most famous unproven conjectures in number theory is known as Goldbach’s Conjecture, which states that every even number greater than two is the sum of two prime numbers; for example, 28 = 5 + 23. We studied Goldbach’s Conjecture in a previous exercise.

Although it is not as well known, Goldbach made another conjecture as follows: Every odd number greater than two is the sum of a prime number and twice a square; for instance, 27 = 19 + 2 * (2 ** 2). (The conjecture is sometimes stated as every odd composite number is the sum of a prime number and twice a square, since it is trivially true with 0 as the square root for all prime numbers; alternately, it is sometimes limited so that the number being squared must be positive, in which case there are some odd primes that can be so expressed.) Sadly, it is easy to find a counter-example that disproves Goldbach’s other conjecture.

Your task is to write a program that finds the smallest number that disproves Goldbach’s other conjecture. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

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 :/ )