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.
