Problem #46 involves a disproved conjecture by the famous mathematician Christian Goldbach. The problem reads:
Project Euler Problem 46: Goldbach's other conjecture
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?
As usual, my solution involves brute force. The solution could be simplified by using a sieve to list all primes up to an upper bound, but unless the first exception is known, it is difficult to establish an upper bound. Thus, I used the naive method of determining whether numbers were prime.
Solution #1: Brute Force Approach
We simply iterate through all the odd composites and check every possible square number less than half of the odd composite to see if it satisfies Goldbach’s Conjecture. If no squares in this range satisfy the conjecture, then the odd composite is a counterexample. Here is an implementation of this method in Python 2.7:
'''
Author: Walker Kroubalkian
Brute Force Approach to Project Euler Problem #46
'''
import time
from math import sqrt
from math import ceil
def isPrime(n):
if(n<=1):
return False
if(n<4):
return True
if(n%2==0):
return False
c = 3
while(c<=sqrt(n)):
if(n%c==0):
return False
c+=2
return True
def projectEulerProblemFortySix(n):
total = 0
c = 15
current = -1
while(total<n):
if(not isPrime(c)):
a = 1
found = False
while(a<=ceil(sqrt(c/2))):
if isPrime(c-2*a*a):
found = True
break
a+=1
if not found:
total+=1
current = c
c+=2
return current
start = time.time()
print projectEulerProblemFortySix(1)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
5777
--- 0.0163691043854 seconds ---
for input of n = 1
'''
As shown above, brute force can be very effective at validating various hypotheses in the mathematical world. One point of interest is that with my program, I was only able to find the counterexamples of 5777 and 5993. According to Wikipedia, these are the only counterexamples that are known (they are also called odd composite Stern numbers). It would be interesting to prove whether the number of counterexamples is finite.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 