Project Euler Problem 739

Solution

Answer: 711399016

Let $T$ be the operation

$$(a_1,a_2,\dots,a_n)\mapsto \left(a_2,\ a_2+a_3,\ a_2+a_3+a_4,\dots,\sum_{i=2}^n a_i\right).$$

Applying $T$ repeatedly until one term remains gives $f(n)$.

For the all-ones sequence, the coefficients that appear are the Catalan triangle numbers:

$$f(n)=\sum_{k=2}^{n} \frac{k-1}{n-1}\binom{2n-k-2}{n-2}a_k.$$

In this problem,

$$a_k=L_k,$$

the Lucas numbers ($1,3,4,7,\dots$).

Using the generating function of the Catalan triangle and the Lucas generating function,

$$\sum_{k\ge1} L_k x^k=\frac{x(1+3x)}{1-x-x^2},$$

one obtains an algebraic generating function for $f(n)$.

From this, a holonomic recurrence can be derived and evaluated modulo

$$M=1,000,000,007$$

using fast linear-recurrence methods (binary splitting / Bostan–Mori), which allows computation for $n=10^8$.

The computation gives

$$f(10^8)\equiv 711399016 \pmod{1,000,000,007}.$$

(Checks: the method reproduces $f(8)=2663$ and $f(20)=742296999$ modulo $10^9+7$.)

Answer: 711399016