Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:
| Triangle | \(T_n=n(n+1)/2\) | \(1, 3, 6, 10, 15, \dots\) | ||
| Pentagonal | \(P_n=n(3n - 1)/2\) | \(1, 5, 12, 22, 35, \dots\) | ||
| Hexagonal | \(H_n=n(2n - 1)\) | \(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.
Note first that for all \(n\), it holds that:
\[ H_n = n(2n-1) = \frac{(2n-1)(2n)}2 = T_{2n-1} \]Therefore every hexagonal number is also a triangular number, so we only have to deal with pentagonal and hexagonal numbers.
A naïve solution would generate a list of pentagonal numbers and a list of hexagonal numbers, then see if any element is common to both lists. We can do one better by exploiting the fact that both sequences are increasing. My program keeps track of a pentagonal number \(P_m\) and a hexagonal number \(H_n\). If \(P_m < H_n\), then it increases \(m\); if \(P_m > H_n\), then it increases \(n\); and if \(P_m = H_n\), we're done.
def p45():
Pm = Hn = 40755
m, n = 165, 143
while True:
if Pm < Hn:
m += 1
Pm = m * (3*m - 1) // 2
else:
n += 1
Hn = n * (2*n - 1)
if Pm == Hn:
return Pm