Project Euler Problem 834
A sequence is created by starting with a positive integer n and incrementing by (n+m) at the m^{th} step.
Solution
Answer: 1254404167198752370
Let the sequence start at $a_0=n$, and at step $m$ we add $n+m$.
Then the $m$-th term is
$$a_m=n+\sum_{k=1}^m (n+k) =(m+1)\left(n+\frac m2\right) =\frac{(m+1)(2n+m)}2.$$
We need
$$n+m \mid a_m.$$
Set
$$d=n+m \qquad (m=d-n).$$
Substituting:
$$a_m=\frac{(d-n+1)(d+n)}2.$$
Expanding:
$$2a_m=d(d+1)-n(n-1).$$
Now analyze divisibility by $d$:
- If $d$ is odd, then $2$ is invertible mod $d$, so we require
$$d \mid n(n-1).$$
- If $d$ is even, write $n(n-1)=2^s q$ with $q$ odd.
The condition becomes that the full power $2^s$ must divide $d$.
Thus valid divisors are exactly those divisors $d$ of $n(n-1)$ whose 2-adic valuation is either $0$ or $s$.
For every such divisor $d>n$, the corresponding index is
$$m=d-n.$$
So:
$$T(n)=\sum_{\substack{d\mid n(n-1)\ d>n\ v_2(d)\in{0,s}}}(d-n).$$
A sieve-based divisor enumeration computes all values efficiently up to $N=1234567$.
The computation gives
$$U(1234567)=\sum_{n=3}^{1234567} T(n) =1254404167198752370.$$
Answer: 1254404167198752370