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:

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.

55545352515049484746454443424140393837363534333231302928272625242322212019181716151413121110987654321