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

2 Responses to “Goldbach’s Other Conjecture”

  1. Zack said

    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.

  2. Paul said

    A generator in Python.

    def goldbach():
        for cand in count(3, 2):
            c, diff = cand, 2
            while not is_prime(c):
                c -= diff
                diff += 4
                if c <= 1:
                    yield cand
                    break
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: