Project Euler Problem 955 Solution

Project Euler Problem 955 Statement

A sequence $(a_n)_{n \ge 0}$ starts with $a_0 = 3$ and for each $n \ge 0$,

if $a_n$ is a triangle number, then $a_{n + 1} = a_n + 1$;
otherwise, $a_{n + 1} = 2a_n - a_{n - 1} + 1$.

The sequence begins: $${\color{red}3}, 4, {\color{red}6}, 7, 9, 12, 16, {\color{red}21}, 22, 24, 27, 31, {\color{red}36}, 37, 39, 42, \dots$$ where triangle numbers are marked red.

The $10$th triangle number in the sequence is $a_{2964} = 1439056$.
Find the index $n$ such that $a_n$ is the $70$th triangle number in the sequence.

Solution

Project Euler Problem 955 overview:

Define a sequence $(a_n)$ with $a_0=3$ and, for $n≥0$: if $a_n$ is triangular (of the form $m(m+1)/2)$, then $a_{n+1} = a_n+1$; otherwise $a_{n+1}=2a_n−a_{n-1}+1$.
Given that the 10th triangular term in the sequence is $a_{2964}=1,439,056$, find the index $n$ such that $a_n$ is the 70th triangular term in the sequence.

Solution Summary

From any triangular $a = T_r$, the sequence moves by triangular increments $T_1, T_2, \dots$ until it hits another triangle.

Asking “when does $T_r + T_k$ become triangular?” is equivalent to factoring $M = 2a = r(r+1)$ and finding a divisor pair $(x, y)$ with odd difference.

Scanning divisors in increasing order makes the first valid pair give the minimum $k$.

Summing those minimal $k$’s across $N-1$ jumps gives the desired index $n$.

With sympy.divisors, all this fits in a tiny script while staying mathematically clear.

Solution Detail

We look only at the moments when the sequence hits a triangular number $T_r = \dfrac{r(r+1)}{2}$. Starting at $a_0 = 3 = T_2$, the next time we land on a triangular number happens after a gap of size another triangular number $T_k$. So from a triangular state $a = T_r$, we search for the smallest positive $k$ such that

$$ T_r + T_k = T_m \quad \text{for some integer } m. $$

Algebra turns this into a simple factor-pair test on $M = 2a = r(r+1)$:

$$ 2a = (m + k + 1)(m - k). $$

Thus, if $x\cdot y = M$ and $x - y$ is odd, then

$$ k = \frac{x - y - 1}{2}, \qquad m = \frac{x + y - 1}{2}. $$

We iterate through the positive divisors $x$ of $M$ in ascending order; the first pair that yields $k > 0$ gives the minimum such $k$. Add $k$ to the running index and add $T_k$ to $a$, and repeat $N-1$ times. The sum of all these $k$’s is exactly the index $n$ where the $N$-th triangular term appears.

An Example

Start at $a=3=T_2$. Then $M=2a=6$. Positive divisors in order: $1,2,3,6$.

$x=1 \Rightarrow y=6$: $x-y=-5$ (odd but $k<0$), skip.
$x=2 \Rightarrow y=3$: $x-y=-1$ (odd but $k<0$), skip.
$x=3 \Rightarrow y=2$: $x-y=1 \Rightarrow k=0$, skip (we need $k\ge 1$).
$x=6 \Rightarrow y=1$: $x-y=5 \Rightarrow k=2$ (first valid $k>0$).
Update index $n\leftarrow n+2$, value $a\leftarrow a+T_2=a+3=6$ (indeed triangular).

Repeat the same logic from the new triangular $a$.

Python Source Code

from sympy import divisors

def pe955(N=70):
    n, a = 0, 3
    for _ in range(N - 1):
        M = 2 * a
        for x in divisors(M):
            y = M // x
            if (x - y) & 1 and (k := (x - y - 1) // 2) > 0:
                n += k
                a += k * (k + 1) // 2
                break
    return n

print(pe955())

Last Word

To make some variable name more clear, we define them as follows:

$a$ (no subscript) = “the current value of the sequence at a triangular hit.”
In the code, every outer-loop iteration starts at a value that is triangular. So we write \[ a \;=\; T_r \;=\; \frac{r(r+1)}{2} \] for some integer $r$. It’s shorthand for “$a_n$ at the current triangular moment.”
$k$ = the size of the next triangular gap (and also the number of steps to the next triangular hit).
From a triangular $a = T_r$, the sequence advances by $T_1, T_2, \dots$ until landing on the next triangle. The first time we land on a triangle again happens after adding $T_k$. That $k$ is the smallest positive integer satisfying \[ T_r + T_k \;=\; T_m \quad \text{for some integer } m. \] In the sequence index, this means we move forward by $k$ positions.
$M$ = $2a$.
We multiply by 2 to clear denominators in triangular numbers. Since \[ a = T_r = \frac{r(r+1)}{2}, \] we get \[ M \;=\; 2a \;=\; r(r+1). \] The key identity becomes a factorization: \[ 2a \;=\; (m + k + 1)(m - k). \] That’s why you see $2a = (m+k+1)(m-k)$ without subscripts: it uses the current triangular $a$.