Problem 964: Generalized Pentagonal Numbers

Mathematical Analysis

Euler’s Pentagonal Number Theorem

The generalized pentagonal numbers arise from one of Euler’s most beautiful identities:

where $\omega_k = k(3k-1)/2$. This identity is fundamental to the theory of integer partitions, as it provides a recurrence for the partition function $p(n)$.

Definition. The generalized pentagonal numbers are given by:

• For $k > 0$: $\omega_k = k(3k-1)/2 = 1, 5, 12, 22, 35, 51, \ldots$
• For $k < 0$, i.e., $k = -m$: $\omega_{-m} = m(3m+1)/2 = 2, 7, 15, 26, 40, 57, \ldots$
• $\omega_0 = 0$

Interleaving both branches: $0, 1, 2, 5, 7, 12, 15, 22, 26, 35, 40, 51, 57, 70, 77, \ldots$

Connection to Partition Function

Theorem (Euler). The partition function satisfies:

where $p(m) = 0$ for $m < 0$ and $p(0) = 1$. This gives an $O(n^{3/2})$ algorithm for computing $p(n)$.

Range Analysis

For $N = 10^7$:

• Positive branch: $k(3k-1)/2 < N$ gives $k < (\sqrt{24N+1}+1)/6 \approx 2582$.
• Negative branch: $m(3m+1)/2 < N$ gives $m < (\sqrt{24N+1}-1)/6 \approx 2581$.

Total count: approximately $2 \times 2582 + 1 = 5165$ generalized pentagonal numbers below $10^7$ (including $\omega_0 = 0$, which contributes 0 to the sum).

Growth Rate

The generalized pentagonal numbers grow quadratically: $\omega_k \sim \frac{3k^2}{2}$ for large $|k|$. Their density among positive integers decreases as $O(1/\sqrt{n})$.

Concrete Examples

Derivation

Editorial

Sum of all generalized pentagonal numbers omega_k = k(3k-1)/2 for k = 0, +/-1, +/-2, … that are below 10^7. The generalized pentagonal numbers arise in Euler’s pentagonal number theorem for the partition function. The sequence begins: 0, 1, 2, 5, 7, 12, 15, 22, 26, 35, 40, … We iterate over $k = 1, 2, \ldots$ generate $\omega_k = k(3k-1)/2$ until $\omega_k \ge N$. We then iterate over $m = 1, 2, \ldots$ generate $\omega_{-m} = m(3m+1)/2$ until $\omega_{-m} \ge N$. Finally, sum all values below $N$.

Pseudocode

For $k = 1, 2, \ldots$ generate $\omega_k = k(3k-1)/2$ until $\omega_k \ge N$
For $m = 1, 2, \ldots$ generate $\omega_{-m} = m(3m+1)/2$ until $\omega_{-m} \ge N$
Sum all values below $N$

Partial Sum Formula

Wait: $\frac{3}{2} \cdot \frac{K(K+1)(2K+1)}{6} - \frac{1}{2} \cdot \frac{K(K+1)}{2} = \frac{K(K+1)(2K+1)}{4} - \frac{K(K+1)}{4} = \frac{K(K+1) \cdot 2K}{4} = \frac{K^2(K+1)}{2}$.

Similarly $\sum_{m=1}^{M} m(3m+1)/2 = \frac{M(M+1)(2M+1)}{4} + \frac{M(M+1)}{4} = \frac{M(M+1)(M+1)}{2} = \frac{M(M+1)^2}{2}$.

But the last terms may exceed $N$, requiring truncation.

Proof of Correctness

Each generalized pentagonal number is generated exactly once. The enumeration terminates correctly at the first value exceeding $N$.

Complexity Analysis

$O(\sqrt{N})$ time and space.

Answer

/*
 * Problem 964: Generalized Pentagonal Numbers
 *
 * Sum all omega_k = k(3k-1)/2 for k = +-1, +-2, ... below 10^7.
 *
 * Complexity: O(sqrt(N)).
 */

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

int main() {
    const long long N = 10000000;
    long long total = 0;

    for (long long k = 1; ; k++) {
        long long v1 = k * (3*k - 1) / 2;
        long long v2 = k * (3*k + 1) / 2;
        if (v1 >= N && v2 >= N) break;
        if (v1 < N) total += v1;
        if (v2 < N) total += v2;
    }

    cout << total << endl;
    return 0;
}

"""
Problem 964: Generalized Pentagonal Numbers

Sum of all generalized pentagonal numbers omega_k = k(3k-1)/2
for k = 0, +/-1, +/-2, ... that are below 10^7.

The generalized pentagonal numbers arise in Euler's pentagonal number
theorem for the partition function. The sequence begins:
    0, 1, 2, 5, 7, 12, 15, 22, 26, 35, 40, ...

Key results:
    - For positive k: omega_k = k(3k-1)/2
    - For negative k (use k -> -k): omega_{-k} = k(3k+1)/2
    - Count of generalized pentagonal numbers below 10^7: ~2582
    - Complexity: O(sqrt(N))

Methods:
    1. generalized_pentagonal     — generate all gen. pentagonal numbers < N
    2. is_pentagonal              — check if a number is pentagonal
    3. pentagonal_via_formula     — direct computation for given k range
    4. cumulative_sum_analysis    — growth analysis of cumulative sum
"""

import numpy as np

def generalized_pentagonal(N):
    """Generate all generalized pentagonal numbers below N, sorted."""
    result = []
    for k in range(1, N):
        val_pos = k * (3 * k - 1) // 2
        if val_pos >= N:
            break
        result.append(val_pos)
        val_neg = k * (3 * k + 1) // 2
        if val_neg < N:
            result.append(val_neg)
    result.sort()
    return result

def is_generalized_pentagonal(n):
    """Check if n is a generalized pentagonal number."""
    # n = k(3k-1)/2 => 24n+1 = (6k-1)^2
    # n = k(3k+1)/2 => 24n+1 = (6k+1)^2
    val = 24 * n + 1
    from math import isqrt
    s = isqrt(val)
    if s * s != val:
        return False
    # s = 6k-1 or s = 6k+1 => s % 6 == 5 or s % 6 == 1
    return s % 6 in (1, 5)

def pentagonal_for_k_range(k_min, k_max):
    """Compute omega_k for each k in [k_min, k_max]."""
    result = {}
    for k in range(k_min, k_max + 1):
        result[k] = k * (3 * k - 1) // 2
    return result

def cumulative_sum_growth(nums):
    """Return cumulative sum array."""
    return np.cumsum(nums)

# Verification
# Known first generalized pentagonal numbers
known = [1, 2, 5, 7, 12, 15, 22, 26, 35, 40]
gp_small = generalized_pentagonal(50)
assert gp_small == known, f"Expected {known}, got {gp_small}"

# Verify is_generalized_pentagonal
for v in known:
    assert is_generalized_pentagonal(v), f"{v} should be generalized pentagonal"

# Non-pentagonal checks
for v in [3, 4, 6, 8, 9, 10, 11]:
    assert not is_generalized_pentagonal(v), f"{v} should NOT be gen. pentagonal"

# Compute answer
N = 10 ** 7
gp = generalized_pentagonal(N)
answer = sum(gp)
print(f"Count: {len(gp)}")
print(answer)