Solving Project Euler: Problem 45

Post by cbarrick » Mon, Nov 17, 2025, 2:01 PM UTC

wenderen wrote: post #8

cbarrick wrote: post #5

Earlier quoted context omitted.

Same algorithm in Rust finds 2172315626468283465 in about 3 seconds on my M1 Pro. $ time cargo run --release Finished `release` profile [optimized] target(s) in 0.02s Running `target/release/p45` 0 1 40755 1533776805 57722156241751 2172315626468283465 cargo run --release 2.95s user 0.04s system 98% cpu 3.029 total Runs on the Rust Playground too: https://play.rust-lang.org/?version=stable&mode=release&edit...

Neat! I translated my code to Rust line-for-line and the iterator approach significantly outperforms it. Rust newbie q - why use `x.wrapping_sub()` instead of regular old `x - 1`? Seems like we're never going to underflow `usize` for any of the 3 formulae?

> why use `x.wrapping_sub()` instead of regular old `x - 1`?

Because I coded it to start at x=0, which will underflow and will panic in debug mode.

Post by cbarrick » Thu, Nov 20, 2025, 11:38 AM UTC

throwaway81523 wrote: post #9

wenderen wrote: post #8

Earlier quoted context omitted.

Neat! I translated my code to Rust line-for-line and the iterator approach significantly outperforms it. Rust newbie q - why use `x.wrapping_sub()` instead of regular old `x - 1`? Seems like we're never going to underflow `usize` for any of the 3 formulae?

I don't use Rust at all, but if compiler warnings are set to maximum, I'd want subtracting anything from a usize to give a warning unless the compiler can verify that the result is a valid usize. BTW, OEIS A014979 gives a linear recurrence for triangular-pentagonal numbers, so filtering for hexagonals gives a much faster way to do this problem. There may be a recurrence that does all three at once, not sure.

> There may be a recurrence that does all three at once, not sure.

Now that we know the start of the sequence, we can just dump it into OEIS to look up the answer! :)

The sequence is A046180 (https://oeis.org/A046180) titled "Hexagonal pentagonal numbers" with a nice and easy recurrence relation:

    a(n) = 37635*a(n-1) - 37635*a(n-2) + a(n-3).

Also, according to the comments on OEIS, all hexagonal numbers are triangular, so we could have just skipped that requirement entirely.

Re: Solving Project Euler: Problem 45

Re: Solving Project Euler: Problem 45