Christian Goldbach

Thanks to everyone who submitted entries to this coding challenge. Amazingly, even though the challenge was open to all languages, every entry was in Python. I was also amazed to see how consistent most answers were in their methods – perhaps that’s what I get for proposing a challenge that included prime-checking and simple math, or perhaps you are all just good programmers and gravitate towards nice, clean, direct code.

Anyway, I chose Eric’s entry as the winner because he provided code that was easy to read, answered the problem elegantly AND also supplied documentation that made it easy to follow the method he was taking.

—Please note that I have changed the winner for this competition. I initially mis-attributed Eric’s work to another entrant. To rectify this, both Eric and Russel (whose solution was also very good and similar in approach, but not printed below) have been awarded the prize. —

Here’s his code. Copy and paste it into your favorite method of running python programs (I stick to codecademy labs for the most part because I haven’t figured out how to run python reliably anywhere else). Russel has won a free copy of my zombie fractions book, ‘In Parts’ which he can donate to the fraction- and zombie- loving person in his life.

1. # Goldbach’s Conjecture

2. # Eric

3. from math import sqrt,ceil

5. max = 400

7. def primeSieve(max):

8.     “””Lists primes upto ~10,000,000 fairly quickly”””

9.     quickList = [True for i in range (max-1)]

10.     # highest possible prime

11.     maxCheck = ceil(sqrt(max))

13.     i = 2

14.     while i != maxCheck:

15.         # if i is prime

16.         if quickList[i-2] == True:

17.             # k keeps track of looper

18.             k = i

19.             while i + k <= max:

20.                 quickList[i+k-2] = False

21.                 k += i

22.             i += 1

23.         else:

24.             i += 1

26.     primeList = [iNum+2 for iNum,i in enumerate(quickList) if i == True]

27.     return primeList

29. primes = primeSieve(max)

31. # list of even numbers from 4 – max

32. evens = [2*i+4 for i in range((max-2)/2)]

34. # cycle through combinations of sums of primes, record what works

35. sums = []

36. def expressAsSum(target):

37.     for i in primes:

38.         for j in primes:

39.             if i+j == target:

40.                 sums.append(i)

41.                 sums.append(j)

42.                 return True

43.     # if no solutions are found, we’ve found a disclaimer for the conjecture!

44.     return False

46. #for each element in list of evens

47. for i in evens:

48.     if expressAsSum(i) == False:

49.         print (str(i) + “fails Goldbach’s Conjecture”)

50.         break

52. for iNum,i in enumerate(evens):

53.     print (“%d = %d + %d” % (i, sums[2*iNum], sums[2*iNum+1]))