Problem 44: Pentagon Numbers

Mathematical Development

Definitions

Definition 1. The $n$-th pentagonal number is $P_n = \frac{n(3n-1)}{2}$ for $n \in \mathbb{Z}^+$.

Definition 2. A positive integer $v$ is pentagonal if $v = P_n$ for some $n \in \mathbb{Z}^+$.

Theoretical Development

Theorem 1 (Pentagonal number characterization). A positive integer $v$ is pentagonal if and only if $24v + 1$ is a perfect square $s^2$ with $s \equiv 5 \pmod{6}$.

Proof. ($\Rightarrow$) Let $v = P_n = \frac{n(3n-1)}{2}$. Then

Set $s = 6n - 1$. Since $n \geq 1$, we have $s \geq 5$ and $s = 6n - 1 \equiv -1 \equiv 5 \pmod{6}$.

($\Leftarrow$) Suppose $24v + 1 = s^2$ with $s \equiv 5 \pmod{6}$. Write $s = 6n - 1$ for some $n \in \mathbb{Z}^+$ (justified since $s \equiv 5 \pmod{6}$ and $s \geq 5$ implies $n \geq 1$). Then

Corollary 1 (Equivalent formulation). $v$ is pentagonal if and only if $n = \frac{1 + \sqrt{1 + 24v}}{6}$ is a positive integer. Equivalently, $1 + 24v$ must be a perfect square and $(1 + \sqrt{1+24v})$ must be divisible by $6$.

Proof. Solving $P_n = v$ via the quadratic formula yields $n = \frac{1 + \sqrt{1+24v}}{6}$ (positive root). Setting $s = \sqrt{1+24v}$, the condition $6 \mid (1 + s)$ is equivalent to $s \equiv 5 \pmod{6}$. $\square$

Lemma 1 (Difference formula). For $1 \leq j < k$,

Proof.

Lemma 2 (Monotonicity in $j$). For fixed $k$, the function $j \mapsto P_k - P_j$ is strictly decreasing on $\{1, 2, \ldots, k-1\}$.

Proof. We have $\frac{d}{dj}(P_k - P_j) = -P_j' = -(3j - \tfrac{1}{2}) < 0$ for all $j \geq 1$. In discrete terms, $(P_k - P_j) - (P_k - P_{j+1}) = P_{j+1} - P_j = 3j + 1 > 0$, so $P_k - P_j > P_k - P_{j+1}$. $\square$

Lemma 3 (Monotonicity in gap). For fixed gap $d = k - j \geq 1$, the difference $P_k - P_{k-d}$ is strictly increasing in $k$.

Proof. By Lemma 1, $P_k - P_{k-d} = \frac{d(6k - 3d - 1)}{2}$, which is linear in $k$ with positive coefficient $3d > 0$. $\square$

Lemma 4 (Minimum gap bound). For $k \geq 2$, the smallest difference $P_k - P_{k-1} = 3k - 2$.

Proof. $P_k - P_{k-1} = \frac{1 \cdot (3(2k-1) - 1)}{2} = \frac{6k - 4}{2} = 3k - 2$. $\square$

Theorem 2 (Search strategy and termination). The minimum pentagonal difference $D$ can be found by iterating $k = 2, 3, \ldots$ and, for each $k$, iterating $j = k-1, k-2, \ldots, 1$. Once a valid pair $(j, k)$ is found with $D = P_k - P_j$, we continue only while $P_k - P_{k-1} < D$ (by Lemma 4, no future $k$ can improve once its minimum gap exceeds the current best).

Proof. For any fixed $k' > k$, the minimum possible difference is $P_{k'} - P_{k'-1} = 3k' - 2$ (Lemma 4). Once $3k' - 2 \geq D^*$ (the current best), no pair involving $k'$ can achieve a smaller difference. This gives the termination criterion $k' \leq \frac{D^* + 2}{3}$. $\square$

Theorem 3. The minimum pentagonal difference is $D = 5482660$, achieved by $(j, k) = (1020, 2167)$.

Proof. By exhaustive search using the strategy of Theorem 2:

• $P_{1020} = \frac{1020 \cdot 3059}{2} = 1560090$
• $P_{2167} = \frac{2167 \cdot 6500}{2} = 7042750$
• $D = P_{2167} - P_{1020} = 5482660$
• $S = P_{2167} + P_{1020} = 8602840$

Verification of pentagonality:

• For $D = 5482660$: $24 \cdot 5482660 + 1 = 131583841 = 11471^2$, and $11471 = 6 \cdot 1912 - 1$, so $D = P_{1912}$.
• For $S = 8602840$: $24 \cdot 8602840 + 1 = 206468161 = 14369^2$, and $14369 = 6 \cdot 2395 - 1$, so $S = P_{2395}$.

The search terminates after confirming that no pair with smaller $D$ exists: all $k$ up to $\frac{5482660 + 2}{3} \approx 1827554$ must be checked, but in practice the inner loop terminates early (via Lemma 2) for most $k$ values. $\square$

Editorial

We iterate over the larger index $k$ in increasing order and compute $P_k$ on demand. For each fixed $k$, the smaller index $j$ is scanned downward from $k-1$, so the corresponding differences $P_k - P_j$ are examined from smallest to largest; this lets us stop the inner scan once the current difference is no better than the best solution already known. The outer loop also terminates as soon as the minimum possible gap $P_k - P_{k-1}$ exceeds the best difference, and every candidate pair is checked with the pentagonal discriminant criterion for both the sum and the difference.

Pseudocode

Algorithm: Minimum Difference of Pentagonal Pairs
Require: The pentagonal number sequence P_n = n(3n - 1) / 2.
Ensure: The least difference P_k - P_j such that both P_k - P_j and P_k + P_j are pentagonal.
1: Initialize best ← infinity.
2: For k ← 2, 3, 4, ... do:
3:     Compute P_k and, if the smallest possible difference at index k already satisfies 3k - 2 ≥ best, return best.
4:     For j from k - 1 down to 1, set Delta ← P_k - P_j; if Delta ≥ best, stop the inner scan for this k.
5:     If both Delta and P_k + P_j are pentagonal, update best ← Delta.

Complexity Analysis

Proposition (Time complexity). Let $K$ be the index of the larger pentagonal number in the optimal pair. The algorithm performs $O(K^2)$ pentagonal tests in the worst case, each costing $O(1)$. With $K = 2167$, the worst-case bound is $O(K^2) \approx 4.7 \times 10^6$.

Proof. The outer loop runs from $k = 2$ to at most $K$. The inner loop runs from $j = k-1$ down to $1$ in the worst case, giving $\sum_{k=2}^{K} (k-1) = \frac{K(K-1)}{2} = O(K^2)$ iterations. Each iteration performs two $O(1)$ pentagonal tests (via integer square root). $\square$

Proposition (Space complexity). $O(1)$: all pentagonal numbers and tests are computed on the fly.

Answer

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

long long pent(long long n) {
    return n * (3 * n - 1) / 2;
}

bool is_pentagonal(long long v) {
    // v is pentagonal iff 1+24v = s^2 with s = 5 mod 6,
    // equivalently (1 + s) % 6 == 0.
    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() {
    // Search for minimal D = P_k - P_j with both D and P_k + P_j pentagonal.
    // Terminate when minimum gap 3k-2 >= best.
    long long best = LLONG_MAX;
    for (long long k = 2; ; k++) {
        if (3 * k - 2 >= best) break;
        long long pk = pent(k);
        for (long long j = k - 1; j >= 1; j--) {
            long long pj = pent(j);
            long long diff = pk - pj;
            if (diff >= best) break;
            if (is_pentagonal(diff) && is_pentagonal(pk + pj)) {
                best = diff;
            }
        }
    }
    cout << best << endl;
    return 0;
}

import math


def pent(n):
    """Compute the n-th pentagonal number P_n = n(3n-1)/2."""
    return n * (3 * n - 1) // 2


def is_pentagonal(v):
    """Test if v is pentagonal: v = P_n iff (1 + sqrt(1+24v)) / 6 is a
    positive integer, equivalently 1+24v is a perfect square s^2 with
    s = 5 mod 6.
    """
    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 pair (P_j, P_k) with j < k such that both P_k - P_j and
    P_k + P_j are pentagonal, and D = P_k - P_j is minimised.

    Search strategy: iterate k, for each k try j = k-1 downto 1.
    Terminate outer loop when the minimum gap 3k-2 exceeds current best.
    """
    best = float('inf')
    for k in range(2, 10000):
        pk = pent(k)
        if 3 * k - 2 >= best:
            break
        for j in range(k - 1, 0, -1):
            pj = pent(j)
            diff = pk - pj
            if diff >= best:
                break
            if is_pentagonal(diff) and is_pentagonal(pk + pj):
                best = diff
    print(best)


solve()