Detailed mathematical approach

Problem Summary

Let \(T_r=\frac{r(r+1)}2\) be the \(r\)-th triangular number, with \(T_0=0\). The implementations start from \(T_2=3\) and repeatedly look for the next nontrivial identity of the form

$T_n-T_w=T_m,$

where \(n>m\) and \(w>0\). At each hit, the solver chooses the smallest possible later index \(n\), adds the corresponding offset \(w\) to the running search position, replaces \(m\) by \(n\), and continues. The required output is the accumulated position of the 70th hit, not the triangular value itself.

A naive search would test huge numbers of pairs \((n,w)\) for every current \(m\). The local solutions avoid that completely by turning the existence of such a triangle identity into a divisor problem for \(m(m+1)\), so each step becomes: factor two consecutive integers, enumerate divisors, and jump directly to the next valid state.

Mathematical Approach

Rewriting a triangular difference as a factorization

Start from

$T_n-T_w=\frac{n(n+1)-w(w+1)}2=T_m=\frac{m(m+1)}2.$

Multiplying by 2 and factoring the left-hand side gives

$n(n+1)-w(w+1)=(n-w)(n+w+1)=m(m+1).$

Define

$P=m(m+1),\qquad u=n-w,\qquad v=n+w+1.$

Then every nontrivial hit corresponds to a divisor pair

$uv=P.$

Because \(u+v=2n+1\), the sum \(u+v\) must be odd. Conversely, if \(u\) and \(v\) are divisors of \(P\) with odd sum, then they reconstruct integers \(n\) and \(w\).

Recovering the next triangular state

Solving the two linear equations for \(n\) and \(w\) gives

$n=\frac{u+v-1}{2},\qquad w=\frac{v-u-1}{2}.$

The condition \(w>0\) is exactly

$v>u+1.$

This matters because the divisor pair \((u,v)=(m,m+1)\) always exists and gives \(n=m,\ w=0\), which is only the trivial identity \(T_m-T_0=T_m\). The implementations deliberately reject that case and keep only genuinely later hits.

Why the largest admissible divisor gives the nearest hit

For fixed \(P\) and \(u\le \sqrt{P}\), we have \(v=P/u\), so

$n(u)=\frac{u+P/u-1}{2}.$

On the interval \(1\le u\le \sqrt{P}\), increasing \(u\) decreases \(P/u\), and \(n(u)\) becomes smaller. Therefore the smallest later triangle index \(n\) is obtained by taking the largest admissible divisor \(u\) not exceeding \(\sqrt{P}\). That is exactly what the depth-first divisor search is tracking.

The factorization itself is also simplified by the identity

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

So instead of factoring the large product \(P\) directly, the implementations factor \(m\) and \(m+1\) separately and merge their prime exponents.

Worked example: from \(T_6\) to the next hit

Take \(m=6\). Then

$T_6=21,\qquad P=m(m+1)=42.$

The divisor pairs with \(u\le\sqrt{42}\) are

$ (1,42),\ (2,21),\ (3,14),\ (6,7). $

All four pairs have odd sum, but \((6,7)\) gives \(w=0\), so it is the trivial representation and is discarded. Among the remaining pairs, the largest admissible \(u\) is \(u=3\), with \(v=14\). Hence

$n=\frac{3+14-1}{2}=8,\qquad w=\frac{14-3-1}{2}=5.$

Indeed,

$T_8-T_5=36-15=21=T_6.$

The other admissible pairs would produce later hits such as \(T_{11}-T_9\) and \(T_{21}-T_{20}\), but the algorithm wants the nearest one, so it keeps \(n=8\).

How the Code Works

Factoring \(m\) and \(m+1\)

Each iteration begins with the current triangular index \(m\). The implementations factor \(m\) and \(m+1\) separately using deterministic Miller-Rabin primality checks for 64-bit inputs together with Pollard-Rho for composite splitting. This is much faster than scanning divisors naively, and it exploits the coprimality of consecutive integers.

Enumerating admissible divisor pairs

Once the prime exponents are known, a recursive divisor generator enumerates every divisor \(u\) of \(P=m(m+1)\). Only candidates with \(u\le\sqrt{P}\) are needed, because the partner divisor is \(v=P/u\). For each candidate, the code tests the two number-theoretic conditions already derived:

$u+v\equiv 1\pmod{2},\qquad v>u+1.$

The best divisor is simply the largest \(u\) that passes both tests. After that, the code converts \((u,v)\) into the next state \((w,n)\) via the closed formulas above.

Updating the hit chain

The running answer is advanced by the offset \(w\), and the current triangular index is replaced by \(n\). Repeating this step-by-step jump avoids any brute-force scan through failed candidates. The C++, Python, and Java implementations all follow the same mathematics; they differ only in low-level integer handling. They also check a common validation point: the 10th hit occurs at accumulated position \(2964\) and lands on \(T_{1696}=1{,}439{,}056\).

Complexity Analysis

If \(H\) hits are required, the total work is the sum of \(H-1\) transition costs. One transition consists of factoring two consecutive integers and then enumerating the divisors of their product. If \(\tau(P)\) is the number of divisors of \(P=m(m+1)\), the divisor search is \(O(\tau(P))\) because each divisor is generated once.

The harder part is integer factorization. Pollard-Rho is a randomized algorithm, so the cleanest statement is heuristic: in practice the runtime is dominated by a modest number of 64-bit factorizations, and the method is easily fast enough for the requested 70th hit. Memory use stays small, since the program stores only a prime-exponent map, a recursion stack for divisor generation, and a handful of wide integers for \(P\), \(\sqrt{P}\), \(n\), and \(w\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=955
2. Triangular number: Wikipedia - Triangular number
3. Integer factorization: Wikipedia - Integer factorization
4. Pollard's rho algorithm: Wikipedia - Pollard's rho algorithm
5. Miller-Rabin primality test: Wikipedia - Miller-Rabin primality test