Wednesday, 4 February 2009

Project Euler, Problem 27

Had a bit of a slump in doing these, as I had more or less reached the limit of what I could do with the skills that I had in C++. Then had a look back through the notes that I made about the problems that I was looking at, and noticed that there was one which I could probably work on further.

Problem 27
Euler published the remarkable quadratic formula n^2 + n + 41. It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39.
Using computers, the incredible formula n^2 − 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, −79 and 1601, is −126479.
Considering quadratics of the form:
n^2 + an + b, where |a| <>
find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.

There's a lot of possible quadratic expressions to be considered for this, but a bit of thought soon lets you realise that b has to be positive, and has to be a prime. I had a reasonable suspicion as well that the magnitude of a has to be smaller than b, but I didn't put that in the routine that I put together.

After this it was just a case of putting something together that would check and see if the various expressions produced primes. I decided that putting in lots of loops and checks to find the expression that produced the longest sequence of primes was going to be quite time-consuming, so I started generating if statements to weed out those expressions which would be more likely to be the right answer (basically by looking at what elements generated primes for various values of n). Analysing the few that remained from this gave me the final answer.

Again, this one wasn't the most elegant solution, but it felt good to be using my analytical skills to do it rather than just brute-forcing something without any consideration.

Onwards and upwards!

No comments: