Project Euler Problem 440
We want to tile a board of length n and height 1 completely, with either 1 times 2 blocks or 1 times 1 blocks with a sin
Solution
Answer: 970746056
Using the Lucas-sequence reduction for the tiling recurrence, one gets
$$T(n)=10T(n-1)+T(n-2),\qquad T(0)=1,\ T(1)=10,$$
and identifies $T(n)=U_{n+1}$ where $U_n$ is a Lucas sequence with strong divisibility property
$$\gcd(U_m,U_n)=U_{\gcd(m,n)}.$$
This reduces
$$\gcd(T(c^a),T(c^b))$$
to a function of $\gcd(c^a+1,c^b+1)$, which depends only on whether the 2-adic valuations of $a,b$ match. After grouping exponent pairs $(a,b)$ by $\gcd(a,b)$ and parity structure, and reducing huge exponents modulo the period of the recurrence modulo $987898789$, the computation becomes feasible in roughly $O(L^2 \log M)$ time for $L=2000$. The recurrence period modulo $987898789$ is $987898788$.
The resulting value is:
Answer: 834767980