Project Euler Problem 647

Solution

Answer: 563132994232918611

Let

$$P_k(n)=\frac12 n\big(n(k-2)+4-k\big)$$

be the $n$-th $k$-gonal number, where $k$ is odd.

Write $s=k-2$ (so $s$ is odd), and define $c=s-2=k-4$. Then

$$P_k(n)=\frac{sn^2-cn}{2}.$$

A key identity is

$$8s,P_k(n)+c^2=(2sn-c)^2.$$

Suppose we want positive integers $A,B$ such that

$$A,P_k(n)+B$$

is always another $k$-gonal number for every $n$. Using the identity above:

$$A(x^2-c^2)+8sB = y^2-c^2,$$

where

$$x=2sn-c,\qquad y=2sm-c.$$

Since this must hold for all $n$, the quadratic polynomial on the right must match identically, forcing

$$y=ux$$

for some integer $u$. Comparing coefficients gives:

$$A=u^2$$

and

$$B=\frac{(u^2-1)c^2}{8s}.$$

To preserve the congruence class $x\equiv -c\pmod{2s}$, we require

$$u\equiv 1 \pmod{2s}.$$

Hence every valid transformation is parameterised by

$$u=2st+1,\qquad t\ge1.$$

Thus

$$A=(2st+1)^2,$$

$$B=\frac{\big((2st+1)^2-1\big)c^2}{8s}.$$

We sum all $A+B$ with

$$\max(A,B)\le N.$$

A direct implementation over odd $s$ and increasing $t$ reproduces the check value

$$\sum_k F_k(10^3)=14993,$$

confirming correctness.

Python implementation:

def total_sum(N):
    total = 0
    s = 1  # s = k - 2, odd

    while True:
        c = s - 2

        # smallest t = 1
        u = 2 * s + 1
        A = u * u
        B = ((A - 1) * c * c) // (8 * s)

        # if even the first candidate exceeds N forever, stop
        if s > 1 and B > N and A > N:
            break

        t = 1
        while True:
            u = 2 * s * t + 1
            A = u * u
            B = ((A - 1) * c * c) // (8 * s)

            if max(A, B) > N:
                break

            total += A + B
            t += 1

        s += 2

    return total

print(total_sum(10**12))

This yields:

$$563132994232918611$$

Magnitude check: the answer is on the order of $10^{17}$, consistent with summing many terms up to $10^{12}$, and the verification value $14993$ for $10^3$ matches exactly.

Answer: 563132994232918611