Project Euler #44: Pentagon numbers
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 #44.
Introduction
“Pentagonal numbers are generated by the formula, Pn=n(3n−1)/2. The first ten pentagonal numbers are:”
1, 5, 12, 22, 35, 51, 70, 92, 117, 145, …
In simple terms:
n | Pn
------
1 | 1
2 | 5
3 | 12
etc.
“Find the pair of pentagonal numbers, Pj and Pk, for which their sum and difference are pentagonal and D = |Pk − Pj| is minimised; what is the value of D?”
I’m not sure what they mean with ‘minimised’, but let’s start!
How to detect if a number is pentagonal?
This problem feels similar to the “Coded triangular numbers” issue with triangular numbers. How would I know that 4 isn’t a pentagonal number, but 5 is? On the Wikipedia page is a formula [1] that I can use. Implementing that method in code looks something like this:
fn is_pentagonal(i: u64) -> bool {
let n = ((((24 * i) + 1) as f64).sqrt() + 1.0) / 6.0;
n.fract() == 0.0
}
#[test]
fn test_is_pentagonal() {
assert_eq!(is_pentagonal(12), true);
assert_eq!(is_pentagonal(9), false);
}
Alongside that method, I also need one that gives a pentagonal number for a positive integer:
fn to_pentagonal_number(i: u64) -> u64 {
(i * (3 * i - 1)) / 2
}
#[test]
fn test_to_pentagonal_number() {
assert_eq!(to_pentagonal_number(4), 22);
assert_eq!(to_pentagonal_number(12), 210);
}
Writing out code for problem 44 goes something like this:
fn problem_44() -> u64 {
let mut j = 1;
let mut k = 1;
'outer: loop {
let pj = to_pentagonal_number(j);
j += 1;
if j == k {
continue
}
loop {
let pk = to_pentagonal_number(k);
if is_pentagonal(pj + pk) && is_pentagonal(pk - pj) {
break 'outer pk - pj
}
k += 1;
}
}
}
#[test]
fn test_problem_44() {
assert_eq!(problem_44(), 6004799519073081);
}
The answer I get is 6004799519073081, but the actual answer is 5482660. I made a bit of a boo-boo, and this is probably where the confusion kicks in about the minimizing. The pair of numbers I find in the code above is:
1 6004799519073081
The variable pj, in my example, never updates. There needs to be an act of balancing where the inner loop quits because some arbitrary condition is met. But what is that condition?
The first pair is (1, 6004799519073081), but what is the other number for 5? For 5 it is 24019198519188237. 24019198519188237 is way higher than 6004799519073081, so I can stop before I hit a number higher than the previous match. However, the first 20 pentagon numbers all require numbers higher than 6004799519073081, making the code painfully slow. This seems like a dead end.
On pen and paper
If I were to this on paper, I’d go something like this:
p1 p2 (p1, p2)
p1 p2 p3 (p1, p3), (p2, p3)
p1 p2 p3 p4 (p1, p4), (p2, p4), (p3, p4)
p1 p2 p3 p4 p5 (p1, p5), (p2, p5), (p3, p5), (p4, p5)
Each (px, py) is a comparison to make. The loop would go something like this:
let j = 1;
let mut k = 1;
loop {
k += 1;
for l in j..k {
println!("{} {}", l, k);
}
// Arbitrary stop
if k > 10 {
break;
}
}
After some fiddling, I get the correct answer using that loop structure:
fn problem_44() -> u64 {
let j = 1;
let mut k = 1;
loop {
k += 1;
let mut m: u64 = 0;
let pk = to_pentagonal_number(k);
for l in j..k {
let pl = to_pentagonal_number(l);
if is_pentagonal(pk + pl) && is_pentagonal(pk - pl) {
m = pk - pl;
break;
}
}
if m > 0 {
break m
}
}
}
#[test]
fn test_problem_44() {
assert_eq!(problem_44(), 5482660);
}
Sources
The full solution is available on GitHub.
