Project Euler #46: Goldbach's other conjecture

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 #46.

Introduction “It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

It turns out that the conjecture was false.

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?”

Solution The loop we’re going to make is a loop that starts at 1 and skips all the prime numbers and even numbers. Each prime number we encounter, we’ll store inside a vector. For each next odd number we encounter we’ll test if that number can be written as any of those previous primes we encountered and a square, once that condition no longer holds, we’ve found our answer. The method to test for this will look something like this:

fn is_prime_and_square(
    n: u64,
    primes: &Vec<u64>,
    squares: &Vec<u64>) -> bool {

    let mut goldbachs_conjecture = false;

    'outer: for p in primes {
        let t = n - p;

        for s in squares {
            let double = s * 2;

            if t < double { continue };

            if t - double == 0 {
                goldbachs_conjecture = true;
                break 'outer;
            }
        }
    }

    goldbachs_conjecture
}

#[test]
fn test_is_prime_and_square() {
    let primes = vec![2, 3, 5, 7, 11, 13];
    let squares = vec![1, 4, 9, 16, 25, 36];

    assert_eq!(is_prime_and_square(9, &primes, &squares), true);
    assert_eq!(is_prime_and_square(15, &primes, &squares), true);
    assert_eq!(is_prime_and_square(25, &primes, &squares), true);
}

Alongside the primes, the loop will also store all the squares it encounters, and I’ll compare them with each other.

To get to the actual solution, I wrote my initial code like this:

fn problem_46() -> u64 {
    let mut start = 2;
    let mut primes = vec![];
    let mut squares = vec![1];

    loop {
        if !is_prime(start) && start % 2 == 1 {
            if !is_prime_and_square(start, &primes, &squares) {
                break start
            }
        }

        if is_prime(start) {
            primes.push(start);
        }

        squares.push(start.pow(2));

        start += 1;
    }
}

#[test]
fn test_problem_46() {
    assert_eq!(problem_46(), 5777)
}

Solved!

Improvements The code results in the correct answer, but it takes 10.38 seconds to get to that answer. The reason for that is because the squares-vector becomes absurdly large. I believe it’s faster to make the squares vector on the fly, and only make double squares up to the value of start. To do that a bit smartly, I can do something like this:

let mut squares = vec![];

for p in 1..=((start / 2) as f64).sqrt() as u64 {
    squares.push(p.pow(2) * 2));
}

If I were to f.e. take the number 645, I don’t want to create a 645 long vector with the power of 645 in there, multiplied by 2 (which is 416.025 * 2 = 832.050). The maximum number of double squares that make sense here are ~17, which is the square root of start divided by 2. If I were to take the power of 17 and multiply it by 2, I get 578 (which fits nicely within 645). If we go one number up, to 18, the number becomes 648, which no longer fits.

Obviously, I can squeeze that idea in my is_prime_and_square() method like such:

fn is_prime_and_square(n: u64, primes: &Vec<u64>) -> bool {
    let mut goldbachs_conjecture = false;
    let mut squares = vec![];

    for p in 1..=((n / 2) as f64).sqrt() as u64 {
        squares.push(p.pow(2) * 2);
    }

    'outer: for p in primes {
        let t = n - p;

        for ds in &squares {
            if t < *ds { continue };

            if t - ds == 0 {
                goldbachs_conjecture = true;
                break 'outer;
            }
        }
    }

    goldbachs_conjecture
}

#[test]
fn test_is_prime_and_square() {
    let primes = vec![2, 3, 5, 7, 11, 13];

    assert_eq!(is_prime_and_square(9, &primes), true);
    assert_eq!(is_prime_and_square(15, &primes), true);
    assert_eq!(is_prime_and_square(25, &primes), true);
}

By applying this, the problem_46() method becomes very small and very fast:

fn problem_46() -> u64 {
    let mut start = 2;
    let mut primes = vec![];

    loop {
        if start % 2 == 1 &&
           !is_prime(start) &&
           !is_prime_and_square(start, &primes) {
            break start
        }

        if is_prime(start) {
            primes.push(start);
        }

        start += 1;
    }
}

#[test]
fn test_problem_46() {
    assert_eq!(problem_46(), 5777)
}

It finishes in 0.14 seconds.


Further improvements There is room for some clean-up. Mainly I see that I can squash the “double squares”-method described above, together with the inner loop of is_prime_and_square() like such:

fn is_prime_and_square(n: u64, primes: &Vec<u64>) -> bool {
    let mut goldbachs_conjecture = false;

    'outer: for p in primes {
        let t = n - p;
        let max = ((t / 2) as f64).sqrt() as u64;

        for n in 1..=max {
            if t - (n.pow(2) * 2) == 0 {
                goldbachs_conjecture = true;
                break 'outer;
            }
        }
    }

    goldbachs_conjecture
}

#[test]
fn test_is_prime_and_square() {
    let primes = vec![2, 3, 5, 7, 11, 13];

    assert_eq!(is_prime_and_square(9, &primes), true);
    assert_eq!(is_prime_and_square(15, &primes), true);
    assert_eq!(is_prime_and_square(25, &primes), true);
}

I don’t think this can be squeezed into some any()-type of situation and resolve it in a bit more functional-programming kind of way, purely because we break the outer loop.

The full solution is available on GitHub.

55545352515049484746454443424140393837363534333231302928272625242322212019181716151413121110987654321