Project Euler Problem 45: Triangular, Pentagonal, And Hexagonal¶
The source code for this problem can be found here.
Problem Statement¶
Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:
- Triangle: \(T_n = \frac{n(n + 1)}{2} \mbox{ e.g. } T_n = 1, 3, 6, 10, 15, \dots\)
- Pentagonal: \(P_n = \frac{n(3n - 1)}{2} \mbox{ e.g. } P_n = 1, 5, 12, 22, 35, \dots\)
- Hexagonal: \(H_n = n(2n - 1) \mbox{ e.g. } H_n = 1, 6, 15, 28, 45, \dots\)
It can be verified that \(T_{285} = P_{165} = H_{143} = 40755\).
Find the next triangle number that is also pentagonal and hexagonal.
Solution Discussion¶
The first key observation is that every hexagonal number \(H_m\) is also a triangular number \(T_n\):
Let \(T_n = \frac{n \times (n + 1)}{2}\)
Let \(H_m = m \times (2 \times m - 1)\)
Let \(T_n = H_m\)
\(\Rightarrow \frac{n \times (n + 1)}{2} = m \times (2 \times m - 1)\)
\(\Rightarrow n \times (n + 1) = (2 \times m - 1) \times (2 \times m)\)
Which is satisfied if \(n = 2 \times m - 1\)
\(\therefore H_m\) is also the triangular number \(T_{2 \times m - 1}\)
Now, we need to find \(T_l = P_m = H_n\), but as shown above, we can ignore \(T_l\) since \(H_n\) will always be a triangular number (i.e. \(H_n = T_{2 * n - 1}\)). Really, we need to find the next \(P_m = H_n\) following \(P_{165} = H_{143}\).
Let \(P_m = H_n\)
\(\Rightarrow \frac{m \times (3 \times m - 1)}{2} = n \times (2 \times n - 1)\)
\(\Rightarrow 24 \times \bigg( \frac{m \times (3 \times m - 1)}{2} \bigg)\)
\(= 24 \times \bigg( n \times (2 \times n - 1) \bigg)\)
\(\Rightarrow 12 \times m \times (3 \times m - 1) = 24 \times n \times (2 \times n - 1)\)
\(\Rightarrow (6 \times m - 1)^2 - 1 = 3 \times (4 \times n - 1)^2 - 3\) (by completing the squares)
\(\Rightarrow (6 \times m - 1)^2 - 3 \times (4 \times n - 1)^2 = -2\)
\(\Rightarrow x^2 - 3 \times y^2 = -2\) (where \(x = 6 \times m - 1, y = 4 \times n - 1\))
We must find solutions \((x,y)\) to this Diophantine equation from which we can infer solutions \((m,n)\) s.t. \(P_m = H_n\).
Finally, recall we seek a solution \(P_m = H_n\) where \(m \gt 165\) and \(n \gt 143\). I’ll arbitrarily choose \(n\). We start the search on ascending values of \(n\) s.t. \(n \gt 143\). Mapping \(n\) to \(y\), this translates to searching through ascending values of \(y\) s.t. \(y \gt 4 \times 143 - 1\).
Solution Implementation¶
from itertools import count
from math import sqrt
from lib.numbertheory import is_square
from lib.sequence import Pentagonals
def solve():
""" Compute the answer to Project Euler's problem #45 """
pentagonals = Pentagonals() # used to compute the ultimate answer
# Determine the start of the search to skip over T_{285} = P_{165} = H_{143}
next_n = 143 + 1
next_y = 4 * next_n - 1
# Solve the Diophantine equations to identify T_{2 * n - 1} = P_m = H_n for some (m,n)
for y in count(next_y):
if not is_square(3 * y * y - 2):
continue
x = int(sqrt(3 * y * y - 2))
if (x + 1) % 6 == 0 and (y + 1) % 4 == 0:
m, n = (x + 1) // 6, (y + 1) // 4
return pentagonals[m]
expected_answer = 1533776805
-
solutions.problem45.
solve
()¶ Compute the answer to Project Euler’s problem #45