# Project Euler #27: Quadratic primes

This article is part of a series where I'll be diving head first into the Project Euler puzzles. I want to document the challenge of solving such a puzzle and how I got to the answer. I want to prefix this by stating that I can't cheat for any of these challenges; with that I mean I can't look up any other implementations online. After the implementation, I will validate the answer by using this document or a similar sheet.

### Introduction

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. A couple of things we know:

• The quadratic notation is `n^2 + an + b`.
• The ranges of a are 1..1000.
• The ranges of b are 1..=1000.
• The ranges of n are 0 up till a value until no prime is found.

### Validating n^2 + n + 41

The puzzle states that the above method returns a maximum of 40 prime numbers. Let’s first proof that with some code. We’ll take the `is_prime` method from “Largest prime factor” and add some code around it:

``````fn max_primes(a: u64, b: u64) -> u64 {
let mut n: u64 = 0;
let mut count = 0;
loop {
let sum = n.pow(2) + (a * n) + b;

if is_prime(sum) {
count += 1;
} else {
break count;
}
n += 1;
}
}

#[test]
fn test_max_primes() {
assert_eq!(max_primes(1, 41), 40);
}
``````

40 primes seems to be correct. Let’s also try this for the other case where `a` and `b` are 79 and 1601 respectively. According to the puzzle it should return 80 primes. This is where we hit problem number #1. The 79 needs to be a -79. After switching around some `u64`’s with `i64`’s, 80 seems to be the correct number of primes:

``````fn max_primes(a: i64, b: i64) -> u64 {
let mut n: i64 = 0;
let mut count = 0;
loop {
let sum = n.pow(2) + (a * n) + b;

if is_prime(sum as u64) {
count += 1;
} else {
break count;
}
n += 1;
}
}

#[test]
fn test_max_primes() {
assert_eq!(max_primes(1, 41), 40);
assert_eq!(max_primes(-79, 1601), 80);
}
``````

Next up, the puzzle wants to know for which `a` or `b` value it returns the highest group of primes. Assuming both `a` or `b` can be negative, I have to loop from -1000 till a 1000 for `b` and -999 till 999 for `a`? This is an assumption, and I might be wrong but let’s try it out:

``````fn problem_27() -> i64 {
let mut max = 0;
let mut max_product = (0, 0);
let pos_neg = [(1, 1), (-1, 1), (1, -1), (-1, -1)];

for a in 1..1000 {
for b in 1..=1000 {
for (p1, p2) in &pos_neg {
let current_max = max_primes(a * p1, b * p2);
if current_max > max {
max = current_max;
max_product = (a, b);
}
}
}
}

max_product.0 * max_product.1
}
``````

The first problem, is that this code will run forever and ever. I’m kind of curious why it is this slow. Let’s reduce 1000 to a 100 and print out the values of `a` and `b` while we’re doing this. The first case I have, where the code seems to run forever, is: `1, -59`. Upon further investigation, it seems that casting -59 from an `i64` to a `u64` turns -59 into `18446744073709551557`, which is quite a high number to check. I believe I should use `abs()` on the result of `sum` in `max_primes()` to fix that little issue. After making that change, I get a result:

``````fn problem_27() -> i64 {
let mut max = 0;
let mut max_product = (0, 0);
let pos_neg = [(1, 1), (-1, 1), (1, -1), (-1, -1)];

for a in 1..1000 {
for b in 1..=1000 {
for (p1, p2) in &pos_neg {
let current_max = max_primes(a * p1, b * p2);
if current_max > max {
max = current_max;
max_product = (a, b);
}
}
}
}

max_product.0 * max_product.1
}

#[test]
fn test_problem_27() {
assert_eq!(problem_27(), 59231);
}
``````

Upon checking the answer, I almost got it correct, but I missed something tiny, namely to turn the factors into their negative values for `max_product`. After applying that change, it does give back the actual correct answer of -59231:

``````fn problem_27() -> i64 {
let mut max = 0;
let mut max_product = 0;
let pos_neg = [(1, 1), (-1, 1), (1, -1), (-1, -1)];

for a in 1..1000 {
for b in 1..=1000 {
for (p1, p2) in &pos_neg {
let current_max = max_primes(a * p1, b * p2);

if current_max > max {
max = current_max;
max_product = (a * p1) * (b * p2);
}
}
}
}

max_product
}

#[test]
fn test_problem_27() {
assert_eq!(problem_27(), -59231);
}
``````

The full solution is available on GitHub.