Project Euler Problem 921

Project Euler Problem 921

Solution

Answer: 378401935

Let

$$f(x)=\frac{x(x^4+10x^2+5)}{5x^4+10x^2+1}.$$

Using the identity

$$\coth(5u)=\frac{\coth^5 u+10\coth^3 u+5\coth u}{5\coth^4 u+10\coth^2 u+1},$$

one finds that the recurrence multiplies a certain index by $5$ each step.

Starting from

$$a_0=\frac{\sqrt5+1}{2},$$

we obtain the closed form

$$a_n=\frac{F_{3\cdot 5^n}\sqrt5+2}{L_{3\cdot 5^n}},$$

where $F_k$ and $L_k$ are Fibonacci and Lucas numbers.

Hence

$$p_n=\frac{F_{3\cdot 5^n}}2,\qquad q_n=\frac{L_{3\cdot 5^n}}2,$$

and therefore

$$s(n)=p_n^5+q_n^5 =\frac{F_{3\cdot 5^n}^5+L_{3\cdot 5^n}^5}{32}.$$

We need

$$S(1618034)=\sum_{i=2}^{1618034} s(F_i).$$

The computation was then carried out modulo

$$398874989,$$

using:

• Pisano period modulo $398874989$:

$$\pi(398874989)=199437494,$$

• fast doubling for Fibonacci/Lucas evaluation,
• modular reduction of exponents via the multiplicative order of $5$.

The final computed value is

Answer: 201624674