Problem 45: Triangular, Pentagonal, and Hexagonal

Mathematical Development

Mathematical Foundation

Theorem 1. Every hexagonal number is a triangular number. Specifically, $H_m = T_{2m-1}$ for all positive integers $m$.

Proof. Let $H_m = m(2m - 1)$. We claim $H_m = T_{2m-1}$:

$\square$

Lemma 1. The converse of Theorem 1 fails: not every triangular number is hexagonal. Specifically, $T_n$ is hexagonal if and only if $n$ is odd.

Proof. If $T_n = H_m$, then $\frac{n(n+1)}{2} = m(2m-1)$, so $n = 2m - 1$, which is odd. Conversely, if $n = 2m - 1$ is odd, then $T_n = T_{2m-1} = H_m$. $\square$

Theorem 2 (Reduction to hexagonal-pentagonal search). A number is simultaneously triangular, pentagonal, and hexagonal if and only if it is both hexagonal and pentagonal.

Proof. ($\Rightarrow$) Immediate.

($\Leftarrow$) If $v$ is hexagonal, then $v = H_m = T_{2m-1}$ by Theorem 1, so $v$ is triangular. Combined with $v$ being pentagonal, $v$ is all three. $\square$

Theorem 3 (Pentagonal number test). A positive integer $v$ is pentagonal if and only if $n = \frac{1 + \sqrt{1 + 24v}}{6}$ is a positive integer.

Proof. The equation $P_n = v$ gives $\frac{n(3n-1)}{2} = v$, i.e., $3n^2 - n - 2v = 0$. By the quadratic formula, $n = \frac{1 + \sqrt{1 + 24v}}{6}$ (taking the positive root). This is a positive integer if and only if (i) $1 + 24v$ is a perfect square and (ii) $\sqrt{1 + 24v} \equiv 5 \pmod{6}$. $\square$

Theorem 4 (Pell equation structure). The equation $H_m = P_k$, i.e., $m(2m-1) = \frac{k(3k-1)}{2}$, reduces to the generalized Pell equation $3x^2 - 2y^2 = 1$ via the substitution $x = 2k - \frac{1}{3}$ (scaled) and $y = 2m - \frac{1}{2}$ (scaled), or more precisely, to an integer recurrence.

Proof. Setting $H_m = P_k$:

Let $u = 4m - 1$ and $w = 6k - 1$. Then $m = \frac{u+1}{4}$ and $k = \frac{w+1}{6}$. Substituting and simplifying:

The equation $\frac{u(u+1)}{4} = \frac{w(w+1)}{12}$ gives $3u(u+1) = w(w+1)$, i.e., $3u^2 + 3u = w^2 + w$, or equivalently $3(2u+1)^2 - (2w+1)^2 = 2$, which is $3U^2 - W^2 = 2$ with $U = 2u + 1, W = 2w + 1$. This is a generalized Pell equation whose solutions form a recurrence:

with initial solutions generating the sequence of hexagonal-pentagonal numbers. The solutions after $(m,k) = (143, 165)$ yield $(m,k) = (27693, 31977)$. $\square$

Theorem 5. The next number after $40755$ that is simultaneously triangular, pentagonal, and hexagonal is $1533776805$.

Proof. By Theorem 2, we search hexagonal numbers $H_m$ for $m > 143$ and test pentagonality via Theorem 3. By the Pell equation structure (Theorem 4), the next solution is at $m = 27693$:

Verifying pentagonality: $n = \frac{1 + \sqrt{1 + 24 \times 1533776805}}{6} = \frac{1 + \sqrt{36810643321}}{6} = \frac{1 + 191861}{6} = \frac{191862}{6} = 31977$. Since $P_{31977} = \frac{31977 \times 95930}{2} = 1533776805$, the number is pentagonal.

Verifying triangularity: $T_{55385} = \frac{55385 \times 55386}{2} = 1533776805$. $\square$

Editorial

Since every hexagonal number is automatically triangular, it is enough to enumerate hexagonal numbers beyond the known value $H_{143} = 40755$ and test only for pentagonality. Starting from $m = 144$, we compute $H_m = m(2m-1)$ and apply the discriminant criterion for pentagonal numbers. The first hexagonal number that passes this test is therefore the next number that is simultaneously triangular, pentagonal, and hexagonal.

Pseudocode

Algorithm: Next Triangular-Pentagonal-Hexagonal Number
Require: The hexagonal sequence H_m = m(2m - 1).
Ensure: The first value after 40755 that is simultaneously triangular, pentagonal, and hexagonal.
1: Initialize m ← 144.
2: Repeat:
3:     Compute H ← m(2m - 1).
4:     If H is pentagonal, return H; otherwise update m ← m + 1.

Complexity Analysis

Time (brute-force search): We iterate hexagonal numbers from $m = 144$ to $m = 27693$, performing an $O(1)$ pentagonal test at each step. Total: $O(M)$ where $M = 27693$, i.e., $O(27550)$ iterations.

Time (Pell equation): Using the recurrence from Theorem 4, each solution is computed in $O(1)$ from the previous one, giving $O(1)$ per solution after finding the recurrence.

Space: $O(1)$.

Answer

#include <bits/stdc++.h>
using namespace std;

bool is_pentagonal(long long v) {
    if (v <= 0) return false;
    long long disc = 1 + 24 * v;
    long long s = (long long)sqrt((double)disc);
    while (s * s < disc) s++;
    while (s * s > disc) s--;
    if (s * s != disc) return false;
    return (1 + s) % 6 == 0;
}

int main() {
    // Every hexagonal number is triangular: H_m = T_{2m-1}.
    // So we just iterate hexagonal numbers and check if pentagonal.
    // Start after H_143 = 40755.
    for (long long m = 144; ; m++) {
        long long h = m * (2 * m - 1);
        if (is_pentagonal(h)) {
            cout << h << endl;
            return 0;
        }
    }
    return 0;
}

import math

def is_pentagonal(v):
    """Check if v is a pentagonal number."""
    if v <= 0:
        return False
    disc = 1 + 24 * v
    s = math.isqrt(disc)
    if s * s != disc:
        return False
    return (1 + s) % 6 == 0

def solve():
    """Find the next number after 40755 that is triangular, pentagonal,
    and hexagonal.

    Key insight: every hexagonal number H_m = m(2m-1) equals T_{2m-1},
    so all hexagonal numbers are triangular. We only need to find the
    next hexagonal number that is also pentagonal.
    """
    m = 144  # Start after H_143 = 40755
    while True:
        h = m * (2 * m - 1)
        if is_pentagonal(h):
            print(h)
            return
        m += 1

solve()