Project Euler Problem 915
The function s(n) is defined recursively for positive integers by s(1) = 1 and s(n+1) = big(s(n) - 1big)^3 +2 for ngeq 1
Solution
Answer: 55601924
Let
$$f(x)=(x-1)^3+2=x^3-3x^2+3x+1.$$
The sequence is defined by
$$s(1)=1,\qquad s(n+1)=f(s(n)).$$
A key identity is
$$f(x)-f(y)=(x-y)\bigl(x^2+xy+y^2-3x-3y+3\bigr).$$
From this one proves inductively that $(s(n))$ is a strong divisibility sequence:
$$\gcd(s(m),s(n))=s(\gcd(m,n)).$$
Therefore
$$\gcd!\bigl(s(s(a)),s(s(b))\bigr) =s!\left(\gcd(s(a),s(b))\right) =s!\left(s(\gcd(a,b))\right).$$
Define
$$u(n)=s(s(n)).$$
Then
$$T(N)=\sum_{a,b\le N}u(\gcd(a,b)).$$
Using the standard gcd-sum transformation,
$$T(N)=\sum_{d=1}^N u(d),C!\left(\left\lfloor\frac Nd\right\rfloor\right),$$
where
$$C(m)=#{(x,y)\le m:\gcd(x,y)=1} =2\sum_{k=1}^m\varphi(k)-1.$$
Modulo $123456789$, the sequence $s(n)$ becomes eventually periodic:
- preperiod $54$,
- period $33705$.
Reducing recursively gives that $u(n)=s(s(n))$ is periodic from $n\ge3$ with period $420$. This allows the weighted gcd sum to be evaluated in $O(\sqrt N)$ using the standard summatory totient recursion.
Carrying out the computation for $N=10^8$ gives
$$T(10^8)\equiv 26953925 \pmod{123456789}.$$
Answer: 26953925