Project Euler #45: Triangular, pentagonal, and hexagonal

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

Introduction Here we go: in this puzzle, we’re combining “Coded triangular numbers” and “Pentagon numbers” with something called hexagonal numbers. A hexagonal number can be made with the following formula: n(2n - 1). The puzzle states:

“It can be verified that T285 = P165 = H143 = 40755.

Find the next triangle number that is also pentagonal and hexagonal.”

Setup The first thing I’ll be doing is using is_triangular() from “Coded triangular numbers” and is_pentagonal() from “Pentagon numbers”. The next method I need is an is_hexagonal() method, which is something I can take from Wikipedia [1].

fn is_hexagonal(i: u64) -> bool {
    let h = ((((8 * i) + 1) as f64).sqrt() + 1.0) / 4.0;

    h.fract() == 0.0
}

#[test]
fn test_is_hexagonal() {
    assert_eq!(is_hexagonal(6), true);
    assert_eq!(is_hexagonal(2), false);
}

Solution The solution can be found like such:

fn problem_45() -> u64 {
    let mut n: u64 = 40755;
    loop {
        n += 1;

        if is_triangular(n) && is_pentagonal(n) && is_hexagonal(n) {
            break n
        }
    }
}

#[test]
fn test_problem_45() {
    assert_eq!(problem_45(), 1533776805);
}

Improvement Obviously, the code is slow. It takes ~27 seconds before it is finished, and I can do something clever to speed it up. Instead of moving n forward by 1, n can go forward hexagonally (if that’s a word), as that’s the method that will cause the biggest increase:

fn problem_45() -> u64 {
    let mut n: u64 = 143;
    loop {
        n += 1;

        let m = n * ((2 * n) - 1);

        if is_triangular(m) && is_pentagonal(m) {
            break m
        }
    }
}

#[test]
fn test_problem_45() {
    assert_eq!(problem_45(), 1533776805);
}

Voilà! It finished in 0.10s. Alongside that, this saves the need for an is_hexagonal() method.

Sources

[1] Hexagonal number

The full solution is available on GitHub.

55545352515049484746454443424140393837363534333231302928272625242322212019181716151413121110987654321