Project Euler Problem 45

Solution

Answer: 1533776805

We are given three figurate-number sequences:

$$T_n=\frac{n(n+1)}2,\qquad P_n=\frac{n(3n-1)}2,\qquad H_n=n(2n-1)$$

and we know:

$$T_{285}=P_{165}=H_{143}=40755$$

We must find the next number that is simultaneously triangular, pentagonal, and hexagonal.

---

1. Mathematical analysis

Step 1 — Relating hexagonal and triangular numbers

Observe:

$$H_n=n(2n-1)$$

Now compare with triangular numbers:

$$T_m=\frac{m(m+1)}2$$

If we set:

$$m=2n-1$$

then

$$T_{2n-1} = \frac{(2n-1)(2n)}2 = n(2n-1) = H_n$$

So every hexagonal number is automatically triangular.

Therefore, instead of checking all three conditions, we only need to find a hexagonal number that is also pentagonal.

---

Step 2 — Pentagonal test

Suppose a number $x$ is pentagonal:

$$x=\frac{k(3k-1)}2$$

Multiply both sides by $24$:

$$24x = 12k(3k-1)$$

Add 1:

$$24x+1 = 36k^2-12k+1 = (6k-1)^2$$

Thus:

$$x \text{ is pentagonal} \iff 24x+1 \text{ is a perfect square}$$

and specifically:

$$\sqrt{24x+1}\equiv 5 \pmod 6$$

So for each hexagonal number $H_n$, we can test whether:

$$24H_n+1$$

is a perfect square.

---

Step 3 — Search after the known solution

We are told:

$$H_{143}=40755$$

So we begin checking from:

$$n=144$$

Compute:

$$H_n=n(2n-1)$$

and test whether it is pentagonal.

The first match after 40755 is:

$$1533776805$$

---

2. Python implementation

import math

def is_pentagonal(x):
    """
    Check whether x is pentagonal.

    A number x is pentagonal iff:
        24*x + 1
    is a perfect square and congruent to 5 mod 6.
    """
    d = 24 * x + 1
    s = math.isqrt(d)

    return s * s == d and (1 + s) % 6 == 0

n = 144  # Start just after H_143

while True:
    # Hexagonal number
    h = n * (2 * n - 1)

    # Since every hexagonal number is triangular,
    # only test pentagonality.
    if is_pentagonal(h):
        print(h)
        break

    n += 1

---

3. Code walkthrough

Import

import math

We use math.isqrt() for exact integer square roots.

---

Pentagonal checker

def is_pentagonal(x):

Defines a helper function.

d = 24 * x + 1

From the derivation:

$$x \text{ pentagonal} \iff 24x+1 \text{ is a square}$$

s = math.isqrt(d)

Computes the integer square root.

return s * s == d and (1 + s) % 6 == 0

Checks:

1. $d$ is a perfect square.
2. The corresponding pentagonal index is integral.

---

Main search loop

n = 144

We start immediately after the known solution $H_{143}$.

h = n * (2 * n - 1)

Computes the hexagonal number:

$$H_n=n(2n-1)$$

if is_pentagonal(h):

Because every hexagonal number is triangular, this is sufficient.

print(h)
break

Stop at the first valid solution.

---

Small-example verification

For $n=143$:

$$H_{143}=143(285)=40755$$

Check pentagonal condition:

$$24(40755)+1=978121=989^2$$

So the known example works correctly.

---

4. Final verification

The computed value is:

$$1533776805$$

Check rough scale:

• It is much larger than $40755$, as expected.
• It satisfies the hexagonal formula for some integer $n$.
• The pentagonal discriminant test succeeds exactly.

Thus the result is consistent.

---

Answer: 1533776805