Project Euler Problem 955

Solution

Answer: 6795261671274

Let the triangle numbers be

$$T_m=\frac{m(m+1)}2.$$

Suppose $a_r=T_m$ is a triangle number appearing in the sequence, and the next triangle number appearing is $a_{r+k}=T_n$.

Between two triangle numbers, the recurrence is

$$a_{j+1}-a_j=(a_j-a_{j-1})+1,$$

and immediately after a triangle number the difference resets to $1$.

Hence the successive increments are

$$1,2,3,\dots,k,$$

$$T_n-T_m = 1+2+\cdots+k = T_k.$$

Therefore

$$T_n=T_m+T_k.$$

Using $T_x=\frac{x(x+1)}2$,

$$n(n+1)=m(m+1)+k(k+1).$$

Rearrange:

$$(2n+1)^2=(2m+1)^2+(2k+1)^2-1.$$

A standard factorization trick gives

$$m(m+1)=uv,$$

with

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

Then

$$2k+1=v-u,\qquad 2n+1=u+v.$$

So for a given $m$, to get the next triangle number in the sequence we must choose the factor pair

$$uv=m(m+1)$$

with the smallest odd difference $v-u>1$. Then

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

Starting from $m=2$ (since $a_0=3=T_2$), we iterate this rule 69 times and accumulate the corresponding $k$-values (the index jumps).

A clean Python implementation is:

from math import isqrt
from sympy import divisors

def next_triangle(m):
    N = m * (m + 1)

    best = None
    for u in divisors(N):
        if u * u > N:
            break
        v = N // u
        d = v - u

        # need smallest odd difference > 1
        if d > 1 and d % 2 == 1:
            best = (u, v)

    u, v = best

    k = (v - u - 1) // 2
    n = (u + v - 1) // 2

    return n, k

m = 2          # T_2 = 3
index = 0      # a_0

for _ in range(69):   # move to the 70th triangle number
    m, jump = next_triangle(m)
    index += jump

print(index)

This yields

$$6795261671274.$$

Answer: 6795261671274