# 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]