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.
In this article I'll be solving: Project Euler #27.
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.
