Euleryx Problem 27 – Quadratic Primes
My workflow:
Spoiler
Workflow:
Answer: -59231
Last Week's Favourite Solution:
Many solution well worth a look from last week, with different approaches, some removing known "loosing" records ahead of time, and streamlined iterative macros. Last weeks favourite solution goes to @AkimasaKajitani who, with a macro less solution, was able to use a generate rows and multi row formula to figure out the "surplus" on each row, until a value was repeated. Please find this solution on page one of last week's post or click here.
Mathematical Theory:
For this challenge, there were two main tricks used in the solution below, to help minimise the run time & computation. The first of these rules is simple:
As the equation states, we need to fin consecutive primes, starting with a prime value when n = 0. When n =0, the quadratic looks like this:
So in order to even start counting our consecutive primes, b must be a prime number itself, as otherwise, the quadratic wont be prime, when n = 0.
The second trick is to reduce the domain (input values) for a. We can do this by considering the cases where a,b and n are odd or even. Pairing this with facts such as “two odd numbers multiples together = odd” and “two odd numbers added together = even” we get the following table.
| N Odd | N Even |
A Odd | B Odd | So the equation is Odd + Odd + Odd = Odd | So the equation is Even + Even + Odd = Odd |
A Odd | B Even | So the equation is Odd + Odd + Even = Even | So the equation is Even + Even + Even = Even |
A Even | B Odd | So the equation is Odd + Even + Odd = Even | So the equation is Even + Even + Odd = Odd |
A Even | B Even | So the equation is Even + Even + Even = Even | So the equation is Even + Even + Even = Even |
With the exception of the number 2, we know that all prime numbers are odd. Using the table above, we know that if we want consecutive values of n, to yield prime solutions to the quadratic equation, then A and B values must be odd.
These two points together create a significantly reduced list of values to investigate, as we only need to consider pairings where a is odd, and b is prime.
Method:
1) First of all, the list of all potential A & B pairings was created. This was achieved by finding all the odd values where |A| < 1000, and appending it to the list of prime numbers where B < 1000 (created using @gawa IsPrime formula which can be found here)
2) The bulk of the work is then completed in a single generate rows tool. The tool is configured with the conditional formula, such that the quadratic equation IsPrime. This means that if the equation is prime for n=0. It will then attempt, n=1. If this too is prime, then it will try for n=2 etc… until it reaches a value for n where the quadratic isn’t prime.
3) The final step involves identifying the A & B values for the greatest value of N, and then multiplying them together.
4) Submit your answer to the Project Euler Website!
Summary:
Through analysing the equation, for 3 isolated cases (n = 0, n = even, and n = odd) we were able to conclude that all pairings had to be odd, with the additional restriction of B values being prime. This reduced a heavy computational task down to under 200k records.
Want to find out more, follow this link to our introduction post - Euleryx: Let The Games Begin.
