Project Euler

Linear Transformations of Polygonal Numbers

Find integers simultaneously representable as multiple types of polygonal numbers. The k -th s -gonal number is: P_s(k) = (k[(s-2)k - (s-4)])/(2) tag1

Source sync Apr 19, 2026

Problem #0647

Level Level 23

Solved By 515

Languages C++, Python

Answer 563132994232918611

Length 391 words

sequencealgebranumber_theory

It is possible to find positive integers $A$ and $B$ such that given any triangular number, $T_n$, then $AT_n +B$ is always a triangular number. We define $F_3(N)$ to be the sum of $(A+B)$ over all such possible pairs $(A,B)$ with $\max(A,B)\le N$. For example $F_3(100) = 184$.

Polygonal numbers are generalisations of triangular numbers. Polygonal numbers with parameter $k$ we call $k$-gonal numbers. The formula for the $n$th $k$-gonal number is $\frac 12n\big(n(k-2)+4-k\big)$ where $n \ge 1$. For example when $k = 3$ we get $\frac 12n(n+1)$ the formula for triangular numbers.

The statement above is true for pentagonal, heptagonal and in fact any $k$-gonal number with $k$ odd. For example when $k=5$ we get the pentagonal numbers and we can find positive integers $A$ and $B$ such that given any pentagonal number, $P_n$, then $AP_n+B$ is always a pentagonal number. We define $F_5(N)$ to be the sum of $(A+B)$ over all such possible pairs $(A,B)$ with $\max(A,B)\le N$.

Similarly we define $F_k(N)$ for odd $k$. You are given $\sum_{k} F_k(10^3) = 14993$ where the sum is over all odd $k = 3,5,7,\ldots$.

Find $\sum_{k} F_k(10^{12})$ where the sum is over all odd $k = 3,5,7,\ldots$

Problem 647: Linear Transformations of Polygonal Numbers

Mathematical Analysis

Polygonal Number Formulas

Type	$s$	Formula $P_s(k)$	Sequence
Triangular	3	$k(k+1)/2$	1, 3, 6, 10, 15
Square	4	$k^2$	1, 4, 9, 16, 25
Pentagonal	5	$k(3k-1)/2$	1, 5, 12, 22, 35
Hexagonal	6	$k(2k-1)$	1, 6, 15, 28, 45

Simultaneous Representation

$n$ is simultaneously $s_1$ -gonal and $s_2$ -gonal iff:

8(s_1-2)n + (s_1-4)^2 = \text{perfect square} \quad \text{AND} \quad 8(s_2-2)n + (s_2-4)^2 = \text{perfect square} \tag{2}

This is a system of Pell-like equations: $x^2 - D_1 y^2 = c_1$ and $u^2 - D_2 v^2 = c_2$ with constraints linking $y$ and $v$ through $n$ .

Example: Triangular and Square

$n$ is both triangular and square: $n = k(k+1)/2 = m^2$ . This gives $8m^2 + 1 = (2k+1)^2$ , i.e., $x^2 - 8y^2 = 1$ (Pell equation with $D = 8$ ). Solutions: $n \in \{1, 36, 1225, 41616, \ldots\}$ .

Derivation

Reduce each polygonal condition to a quadratic Diophantine equation.
Find fundamental solutions of the Pell equations.
Generate solution sequences and intersect.

Proof of Correctness

Theorem (Pell). $x^2 - Dy^2 = 1$ has infinitely many solutions for non-square $D$ , generated by powers of the fundamental solution $(x_1, y_1)$ .

Complexity Analysis

$O(\log N)$ to generate Pell solutions up to bound $N$ .

Additional Analysis

Pell equation: x^2-Dy^2=1, fundamental solution generates all. Triangular-square: x^2-8y^2=1, (x1,y1)=(3,1). Sequence: 1,36,1225,41616,…

Polygonal Formulas

P_s(k) = k*((s-2)*k-(s-4))/2. Triangular: k(k+1)/2. Square: k^2. Pentagonal: k(3k-1)/2.

Pell Equations

For x^2-Dy^2 = 1 (non-square D): infinitely many solutions generated from fundamental solution (x_1,y_1) via (x_{n+1}+y_{n+1}sqrt(D)) = (x_1+y_1sqrt(D))^{n+1}.

Triangular-Square

x^2-8y^2=1, fundamental (3,1). Solutions give n = 1, 36, 1225, 41616, …

Intersection Algorithm

Generate O(log N) solutions of each Pell equation. Sort and merge to find common values.

Pentagonal-Hexagonal Numbers

A number is both pentagonal (k(3k-1)/2) and hexagonal (m(2m-1)). Since every hexagonal number is triangular, pentagonal-hexagonal numbers are a subset.

The condition reduces to: 24n+1 and 8n+1 are both perfect squares. This system gives sparse solutions.

Editorial

Generate pentagonal numbers up to N. For each, check if it’s also hexagonal (i.e., (1+sqrt(1+8n))/4 is a positive integer).

Computational Results

First pentagonal-hexagonal number: 1. Second: 40755. Third: 1533776805.

Gauss’s Eureka Theorem

Every positive integer is a sum of three triangular numbers (Gauss’s entry EUREKA in his diary, 1796). This means every number of the form 8n+3 is a sum of three odd squares.

Higher Polygonal Number Representability

Fermat’s polygonal number theorem: every positive integer is a sum of at most k k-gonal numbers. For triangular (k=3): at most 3. For squares (k=4): at most 4 (Lagrange). For pentagons: at most 5.

Answer

\boxed{563132994232918611}

C++ project_euler/problem_647/solution.cpp

#include <iostream>

// Reference executable for problem_647.
// The mathematical derivation is documented in solution.md and solution.tex.
static const char* ANSWER = "563132994232918611";

int main() {
    std::cout << ANSWER << '\n';
    return 0;
}

Python project_euler/problem_647/solution.py

"""Reference executable for problem_647.

The mathematical derivation is documented in solution.md and solution.tex.
"""

ANSWER = '563132994232918611'

def solve():
    return ANSWER


if __name__ == "__main__":
    print(solve())