Problem 46

Problem 46

20 June 2003

It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

9 = 7 + 21²
15 = 7 + 22²
21 = 3 + 23²
25 = 7 + 23²
27 = 19 + 22²
33 = 31 + 21²

It turns out that the conjecture was false.

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?    

def fun46():
    i = 35
    while 1:
        if isPrime(i):           
            i += 2
        else:
            isOk = False
            for s in range(1, int(math.sqrt(i/2)+2)):
                t = i - 2*(s**2)
                if t <= 0:
                    isOk = True
                    break
                else:
                    if isPrime(t):
                        i += 2
                        break
            if isOk:
                break
    return i

answer is 5777
time:0.125