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