Euler-Problems/problem46.py at master · respectus/Euler-Problems · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
"""
Goldbach's other conjecture
Project Euler Problem #46
by Muaz Siddiqui

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 + 2×12
15 = 7 + 2×22
21 = 3 + 2×32
25 = 7 + 2×32
27 = 19 + 2×22
33 = 31 + 2×12

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?
"""
from euler_helpers import timeit, is_prime

def is_twiceSquare(n):
    test = (n/2) ** 0.5
    return test == int(test)

@timeit
def answer():
    smallest = 1
    proven = False
    primes = [2]

    while not proven:
        smallest += 2
        if is_prime(smallest):
            primes.append(smallest)
            continue
        proven = True
        for prime in primes:
            if is_twiceSquare(smallest - prime):
                proven = False
                break
    return smallest