3 ms·

I just did a dumb search with lazy lists in Haskell, inspired by the famous problem about Hamming numbers. Runtime was 0.02 seconds. About 2 more seconds to f

I just did a dumb search with lazy lists in Haskell, inspired by the famous problem about Hamming numbers. Runtime was 0.02 seconds. About 2 more seconds to fine the one after that (results: [1,40755,1533776805,57722156241751]). import Data.Ord tri n = n*(n+1)`quot`2 pent n = n*(3*n-1)`quot`2 hex n = n*(2*n-1) fs :: (Integer -> Integer)->[Integer] fs f = map f [1..] cm aas@(a:as) bbs@(b:bs) = case compare a b of EQ -> a : cm as bs GT -> cm aas bs LT -> cm as bbs tt = (fs tri) `cm` (fs pent) `cm` (fs hex) main = print . take 3 $ tt Added: the one after that is 2172315626468283465 which took about 6 minutes with the same Haskell program. I'm sure there are faster implementations and better algorithms. I didn't try to search any further.

cbarrick 11mo ago
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&edition=2024&gist=ac5c1ef7c3df05df403263b4a17a493f https://play.rust-lang.org/?version=stable&mode=release&edit...
- throwaway81523 11mo ago
  Changing the Integer to Int in the Haskell program (use machine integers instead of bignums) speeds the 6 minutes to 35 seconds, fwiw. But that was only ok to do after knowing that the result would fit in a machine int. This is on an i5-3570 which is a bit over half the speed of the M1 Pro (Passmark score 2042 vs 3799). So it scales to around 18 sec on similar hardware. Not too bad given the list-based implementation, I guess.
- wenderen 11mo ago
  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?
  - throwaway81523 11mo ago
    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.
    - cbarrick 11mo ago
      > 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 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.
  - cbarrick 11mo ago
    > 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.

cbarrick 11mo ago

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&edition=2024&gist=ac5c1ef7c3df05df403263b4a17a493f https://play.rust-lang.org/?version=stable&mode=release&edit...

throwaway81523 11mo ago
Changing the Integer to Int in the Haskell program (use machine integers instead of bignums) speeds the 6 minutes to 35 seconds, fwiw. But that was only ok to do after knowing that the result would fit in a machine int. This is on an i5-3570 which is a bit over half the speed of the M1 Pro (Passmark score 2042 vs 3799). So it scales to around 18 sec on similar hardware. Not too bad given the list-based implementation, I guess.
wenderen 11mo ago
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?
- throwaway81523 11mo ago
  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.
  - cbarrick 11mo ago
    > 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 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.
- cbarrick 11mo ago
  > 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.