Project Euler

Triangular Number Intersections

Let T_n = n(n+1)/2 be the n -th triangular number. Find the number of ordered pairs (a, b) with 1 <= a < b <= 10^6 such that T_a + T_b is also a triangular number.

Source sync Apr 19, 2026

Problem #0932

Level Level 11

Solved By 1,877

Languages C++, Python

Answer 72673459417881349

Length 310 words

algebramodular_arithmeticnumber_theory

For the year $2025$ \[2025 = (20 + 25)^2\] Given positive integers $a$ and $b$, the concatenation $ab$ we call a $2025$-number if $ab = (a+b)^2$.

Other examples are $3025$ and $81$.

Note $9801$ is not a $2025$-number because the concatenation of $98$ and $1$ is $981$.

Let $T(n)$ be the sum of all $2025$-numbers with $n$ digits or less. You are given $T(4) = 5131$.

Find $T(16)$.

Problem 932: Triangular Number Intersections

Mathematical Foundation

Theorem 1 (Triangular characterization). An integer $m \geq 0$ is a triangular number if and only if $8m + 1$ is a perfect square.

Proof. ( $\Rightarrow$ ) If $m = k(k+1)/2$ for some non-negative integer $k$ , then $8m + 1 = 4k^2 + 4k + 1 = (2k+1)^2$ , which is a perfect square.

( $\Leftarrow$ ) If $8m + 1 = s^2$ for some positive integer $s$ , then $s$ must be odd (since $8m + 1$ is odd), say $s = 2k + 1$ . Then $8m + 1 = 4k^2 + 4k + 1$ , giving $m = k(k+1)/2 = T_k$ . $\square$

Theorem 2 (Reduction to near-Pythagorean equation). $T_a + T_b$ is triangular if and only if $(2a+1)^2 + (2b+1)^2 - 1$ is a perfect square.

Proof. By Theorem 1, $T_a + T_b$ is triangular iff $8(T_a + T_b) + 1$ is a perfect square. Now:

8(T_a + T_b) + 1 = 8 \cdot \frac{a(a+1) + b(b+1)}{2} + 1 = 4a^2 + 4a + 4b^2 + 4b + 1 = (2a+1)^2 + (2b+1)^2 - 1.

$\square$

Lemma 1 (Parametric families). Setting $X = 2a+1$ , $Y = 2b+1$ , $Z^2 = X^2 + Y^2 - 1$ , the equation $X^2 + Y^2 - Z^2 = 1$ with $X, Y$ odd and $3 \leq X < Y$ parametrizes all valid pairs. Solutions arise from:

Pythagorean-like triples: if $(X, Y, Z)$ satisfies $X^2 + Y^2 = Z^2 + 1$ , then each solution yields $a = (X-1)/2$ , $b = (Y-1)/2$ .
Recurrence relations generated by the automorphisms of the quadratic form $X^2 + Y^2 - Z^2 = 1$ .

Proof. The substitution is direct from Theorem 2. The equation $X^2 + Y^2 - Z^2 = 1$ defines a quadric surface over $\mathbb{Z}$ , and its integer points can be enumerated via descent or parametric families derived from the group structure of the associated orthogonal group. $\square$

Editorial

Count pairs (a, b) with 1 <= a < b <= limit where T_a + T_b is itself a triangular number, i.e. T_a + T_b = T_c for some c >= 1. Key identity: T_a + T_b = a(a+1)/2 + b(b+1)/2 = (a^2 + b^2 + a + b) / 2. This equals T_c = c(c+1)/2 iff a^2 + b^2 + a + b = c(c+1), i.e. 4(a^2 + b^2 + a + b) + 1 = (2c+1)^2, so we need 2(2a+1)^2 + 2(2b+1)^2 - 1 to be a perfect square (of the form (2c+1)^2). We iterate over a from 1 to N-1.

Pseudocode

for a from 1 to N-1
for a from 1 to N-1
For each factorization K = d * e with d < e, d ≡ e (mod 2):

Complexity Analysis

Time (brute force): $O(N^2)$ with $O(1)$ integer square root test per pair.
Time (optimized): $O(N \cdot d(N))$ where $d(N)$ is the average number of divisors, approximately $O(N \log N)$ .
Space: $O(1)$ auxiliary (or $O(N)$ if precomputing divisors).

Answer

\boxed{72673459417881349}

C++ project_euler/problem_932/solution.cpp

#include <bits/stdc++.h>
using namespace std;
int main(){
    const int LIM=10000;
    set<long long> tri;
    for(long long n=1;n*(n+1)/2<=2LL*LIM*(LIM+1);n++) tri.insert(n*(n+1)/2);
    int cnt=0;
    for(int a=1;a<=LIM;a++){
        long long ta=(long long)a*(a+1)/2;
        for(int b=a+1;b<=LIM;b++){
            long long tb=(long long)b*(b+1)/2;
            if(tri.count(ta+tb)) cnt++;
        }
    }
    cout<<cnt<<endl;
    return 0;
}

Python project_euler/problem_932/solution.py

"""
Problem 932: Triangular Number Intersections

Count pairs (a, b) with 1 <= a < b <= limit where T_a + T_b is itself
a triangular number, i.e. T_a + T_b = T_c for some c >= 1.

Key identity:
  T_a + T_b = a(a+1)/2 + b(b+1)/2 = (a^2 + b^2 + a + b) / 2.
  This equals T_c = c(c+1)/2 iff a^2 + b^2 + a + b = c(c+1),
  i.e. 4(a^2 + b^2 + a + b) + 1 = (2c+1)^2, so we need
  2(2a+1)^2 + 2(2b+1)^2 - 1 to be a perfect square (of the form (2c+1)^2).

Methods:
  - solve: Build set of triangulars, iterate pairs, check membership.
  - is_triangular: Check if a number is triangular via discriminant.
  - count_pairs_formula: Use the algebraic identity to check via perfect square test.

Complexity: O(limit^2) for brute-force pair enumeration.
"""

from math import isqrt

# Helper: check if n is triangular
def is_triangular(n):
    """Check if n = k(k+1)/2 for some non-negative integer k."""
    if n < 0:
        return False
    # 8n + 1 must be a perfect square
    disc = 8 * n + 1
    s = isqrt(disc)
    return s * s == disc

def solve(limit):
    """Count pairs (a,b), 1<=a<b<=limit, where T_a + T_b is triangular."""
    tri_set = set()
    n = 1
    max_val = limit * (limit + 1)  # T_a + T_b <= T_limit + T_limit ~ limit^2
    while n * (n + 1) // 2 <= max_val:
        tri_set.add(n * (n + 1) // 2)
        n += 1
    count = 0
    pairs = []
    for a in range(1, limit + 1):
        ta = a * (a + 1) // 2
        for b in range(a + 1, limit + 1):
            tb = b * (b + 1) // 2
            if ta + tb in tri_set:
                count += 1
                if len(pairs) < 500:
                    pairs.append((a, b))
    return count, pairs

def count_pairs_formula(limit):
    """Count pairs using algebraic identity and perfect square test."""
    count = 0
    for a in range(1, limit + 1):
        for b in range(a + 1, limit + 1):
            val = a * a + b * b + a + b
            # val = c(c+1), so 4*val + 1 = (2c+1)^2
            disc = 4 * val + 1
            s = isqrt(disc)
            if s * s == disc:
                count += 1
    return count

# Verification
# T_1 + T_2 = 1 + 3 = 4 = not triangular (T_2=3, T_3=6)
assert not is_triangular(4)
# T_1 + T_5 = 1 + 15 = 16 = not triangular
assert not is_triangular(16)
# T_2 + T_3 = 3 + 6 = 9 = not triangular (T_3=6, T_4=10)
assert not is_triangular(9)

# Cross-check two methods for small limit
c1, _ = solve(50)
c2 = count_pairs_formula(50)
assert c1 == c2, f"Mismatch: {c1} vs {c2}"

# Compute answer (for visualization range)
count_small, pairs = solve(500)
print(f"Pairs found (limit=500): {count_small}")