I attempted the problem myself before reading your solution. My strategy is bit different: for every N>285, I check whether there exists a positive integer solution n to two equations T_N=P_n and T_N=H_n. Using basic algebra and quadratic formula, it boils down to checking whether the quantities 1+12(NN+N) and 1+4(NN+N) are perfect squares. If they are perfect squares, denote their squares by x and y. The next step is to check if 1+x is divisible by 6 and if 1+y is divisible by 4. They are easy using % operator.
from math import sqrt
def isPerfectSquare(n):
sr = int(sqrt(n))
return sr * sr == n
for N in range(1, 10000000000):
foo = 1 + 12*(N*N + N)
bar = 1 + 4*(N*N + N)
if isPerfectSquare(foo) and isPerfectSquare(bar):
x, y = int(sqrt(foo)), int(sqrt(bar))
if (1+x)%6 == 0 and (1+y)%4 == 0:
print(f'Candidate found: N={N}, T_N={N*(N+1)/2}')
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.
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
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.
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.
I attempted the problem myself before reading your solution. My strategy is bit different: for every N>285, I check whether there exists a positive integer solution n to two equations T_N=P_n and T_N=H_n. Using basic algebra and quadratic formula, it boils down to checking whether the quantities 1+12(NN+N) and 1+4(NN+N) are perfect squares. If they are perfect squares, denote their squares by x and y. The next step is to check if 1+x is divisible by 6 and if 1+y is divisible by 4. They are easy using % operator.
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]).
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.Same algorithm in Rust finds 2172315626468283465 in about 3 seconds on my M1 Pro.
Runs on the Rust Playground too: https://play.rust-lang.org/?version=stable&mode=release&edit...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.
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.
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.
The mask hides the whole sentence except the answer. Lol.
To help debug - which browser are you using and on which OS?
iOS Safari