GeekDad Puzzle of the Week Solution – Euler’s Prime Polynomials

Reading Time: 2 minutes

Last week’s Prime Polynomial puzzle as presented:

euler_list2In 1772, the Swiss mathematician Leonhard Euler (pronounced “oiler”) noticed that certain polynomial functions tended to produce a higher proportion of prime numbers than expected. For example, the polynomial n2 + n + 41 produces primes for the first forty natural numbers (0…39.) This, however, is not necessarily the polynomial of the form an2 + bn + c with a=1 that produces the largest set of primes over the early natural numbers.

For your chance at this week’s $50 ThinkGeek Gift Certificate, determine the set of coefficients for the polynomial of the form f(n) = an2 + bn + c with a=1 that has the longest run of prime numbers over the natural numbers (starting with 0.) Please limit your range of b and c from -5000 to +5000, inclusive, and please take a moment or two to “brag” and describe how you went about getting your answer including any shrewd optimizations you made or observations you, um, observed.

Congratulations to Doug Williams, who not only correctly answered the puzzle, but who was drawn at random from all correct entries. To the victor go the spoils (in this case, a $50 ThinkGeek Gift certificate.)

Doug determined his correct solution of f(x) = x2-79x+1601 (a=1, b=-79, c=1601) by completely reviewing all possible polynomials with both b and c ranging from {-300 to +300.} Noting that prime strings were longest when both b and c were odd and that c would need to be both prime and positive to get past x=0, he discovered that polynomials that produced more primes followed a given polynomial themselves (c = 0.25b2+40.75.) Expanding this solution from -5000 to +5000 for b and c, he found that f(x) = x2-79x+1601 produced a stunning 80 primes ranging from 0…79.

Thanks to everyone that submitted a response. Don’t worry… this next week’s puzzle won’t be too math-related!

Get the Official GeekDad Books!