Detailed mathematical approach

Problem Summary

The \(n\)-th triangular number is

$T_n = 1 + 2 + \cdots + n = \frac{n(n+1)}{2}.$

The task is to find the first triangular number whose number of positive divisors is greater than a threshold \(D\). The Project Euler instance uses \(D = 500\), while the implementations are written in a slightly more general form and can solve the same question for any nonnegative threshold.

A naive approach would form each \(T_n\) and factor it directly. The crucial observation is that consecutive integers are coprime, so the factorization of \(T_n\) can be split into two smaller and independent pieces before the divisor count is computed.

Mathematical Approach

The entire solution rests on three facts: triangular numbers are built from consecutive integers, the divisor-count function is multiplicative on coprime inputs, and one of \(n\) or \(n+1\) is always even.

Triangular Numbers as a Product of Two Consecutive Terms

The closed form

$T_n = \frac{n(n+1)}{2}$

already suggests how to search: for each \(n\), determine how many divisors \(T_n\) has, and stop at the first \(n\) for which that count exceeds \(D\).

The obstacle is that \(T_n\) grows quadratically, so direct factorization becomes steadily more expensive. The implementations therefore avoid treating \(T_n\) as one monolithic integer whenever possible.

Divisor Counts from Prime Exponents

If a positive integer has prime factorization

$m = \prod_{i=1}^{r} p_i^{\alpha_i},$

then every divisor of \(m\) is obtained by choosing an exponent \(0 \le \beta_i \le \alpha_i\) for each prime \(p_i\). Hence the number of divisors is

$\tau(m) = \prod_{i=1}^{r} (\alpha_i + 1).$

This is the only divisor formula the code needs. It never enumerates divisors explicitly; it only extracts the prime exponents and multiplies the corresponding \((\alpha_i + 1)\) factors.

The Key Coprime Split

Because consecutive integers share no common factor,

$\gcd(n, n+1) = 1.$

Exactly one of \(n\) and \(n+1\) is even, so the factor \(2\) in \(T_n\) can be absorbed into that even term:

$ (a,b) = \begin{cases} \left(\frac{n}{2}, n+1\right), & \text{if } n \text{ is even}, \\ \left(n, \frac{n+1}{2}\right), & \text{if } n \text{ is odd}. \end{cases} $

Then two useful identities hold at every iteration:

$ab = T_n, \qquad \gcd(a,b) = 1.$

The coprimality is easy to check. For example, if \(n\) is even and some \(d\) divides both \(n/2\) and \(n+1\), then \(d\) also divides \(n\), so \(d\) divides both \(n\) and \(n+1\); therefore \(d=1\). The odd case is identical in spirit.

Now multiplicativity applies:

$\tau(T_n) = \tau(ab) = \tau(a)\tau(b).$

This is the main invariant used by the implementations. Instead of factoring one larger triangular number, they factor two smaller coprime numbers and multiply their divisor counts.

Worked Example: Why \(28\) Appears for \(D = 5\)

Take \(n=7\). Then

$T_7 = \frac{7 \cdot 8}{2} = 7 \cdot 4.$

Here \(a=7\) and \(b=4\), which are coprime. Their prime factorizations are

$7 = 7^1, \qquad 4 = 2^2.$

Therefore

$\tau(7) = 2, \qquad \tau(4) = 3, \qquad \tau(T_7) = 2 \cdot 3 = 6.$

The earlier triangular numbers \(1, 3, 6, 10, 15,\) and \(21\) have at most \(4\) divisors, so the first triangular number with more than \(5\) divisors is \(28\). That is exactly the small checkpoint used by the implementations.

Why Trial Division Is Sufficient

Once the problem is reduced to computing \(\tau(a)\) and \(\tau(b)\), each count is obtained by trial division. The implementation removes all factors of \(2\), then tests odd candidates \(3, 5, 7, \dots\) up to the square root of the remaining value. If a residue larger than \(1\) survives, it must itself be prime and contributes one final factor of \(2\) to the divisor count.

This matches the formula for \(\tau(m)\) exactly: every time the factorization reveals an exponent \(\alpha\), the running answer is multiplied by \(\alpha+1\).

How the Code Works

Scanning the Triangular Numbers Indirectly

The C++, Python, and Java implementations iterate through \(n = 1, 2, 3, \dots\). For each \(n\), they form the pair \((a,b)\) described above rather than factorizing \(T_n\) directly. This keeps the arithmetic closer to the structure of the formula and preserves the invariant \(ab = T_n\) with \(\gcd(a,b)=1\).

Computing the Divisor Count of One Factor

For each of the two factors, the implementation first strips out the power of \(2\), recording its exponent. It then checks only odd trial divisors, counting how many times each one divides the current remainder. Every discovered exponent contributes a multiplier of the form \(\alpha+1\). If the remaining value is still greater than \(1\) after the loop, that remainder is prime and contributes one more factor of \(2\).

Combining the Two Counts and Stopping Early

After the two divisor counts are computed, the implementation multiplies them to obtain \(\tau(T_n)\). As soon as this product exceeds the requested threshold \(D\), it returns

$\frac{n(n+1)}{2}.$

All three versions include a small correctness check based on the fact that the first triangular number with more than \(5\) divisors is \(28\). The C++ version also exposes the threshold as an optional runtime parameter, while the core search strategy remains the same in every language.

Complexity Analysis

Let \(n_*\) be the first index such that \(\tau(T_{n_*}) \gt D\). On the \(n\)-th iteration, the implementation factorizes two numbers of size \(O(n)\) by trial division, so the work per iteration is \(O(\sqrt{n})\).

Summing this from \(1\) through \(n_*\) gives

$\sum_{n=1}^{n_*} O(\sqrt{n}) = O(n_*^{3/2}).$

The memory usage is \(O(1)\): the algorithm stores only a handful of integers and does not build a sieve, a divisor table, or a cache of previous factorizations.

Footnotes and References

1. Project Euler - Problem 12
2. Wikipedia - Triangular number
3. Wikipedia - Divisor function
4. Wikipedia - Fundamental theorem of arithmetic
5. Wikipedia - Trial division
6. OEIS A000217 - Triangular numbers