Project Euler 46: Find the smallest odd composite that cannot be written as the sum of a prime and twice a square
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
I love how Chris was tossing a bunch of stuff out there and then letting someone else prove him wrong, if, in fact, it really was wrong. His famous conjecture (every even integer greater than 2 can be expressed as the sum of two primes) has stood the test of time even today, but some doubt it may hold forever. Gotta love the guy.
I give it a try: If pi never repeats, then it’s infinite and represents every numerical sequence possible. This would include a digital representation of a newspaper article that mentions the discovery of a repeating pi. Therefore, pi does, at some point, repeat.
Sorry for the fill here, just needed a bit more content for this post since there’s not much to be said for explaining the solution.
Generate primes as needed (because we have no idea how many it’s going to take) using our knowledge from Problem 7 and check the proposal until a odd composite is found.
Project Euler 46 SolutionRuns < 0.001 seconds in Python 2.7.
n = 5 f = 1 primes = set() while True: if all(n % p for p in primes): primes.add(n) else: if not any((n-2*i*i) in primes for i in range(1, n)): break n += 3-f f = -f print "Project Euler 46 Solution =", nUse this link to get the Project Euler 46 Solution Python 2.7 source.