Project Euler Problem 929

Solution

Answer: 57322484

Let

$$F(n)=#{\text{compositions of }n\text{ where every run has odd length}}.$$

We derive a generating function.

If a run has value $k$, then its allowed lengths are odd:

$$k,;k,k,k,;k,k,k,k,k,\dots$$

so the generating function for a single run of value $k$ is

$$A_k(x)=x^k+x^{3k}+x^{5k}+\cdots =\frac{x^k}{1-x^{2k}}.$$

Let $B_k(x)$ be the generating function for valid compositions ending in a run of value $k$.

A composition ending in $k$ is obtained by taking any valid composition not already ending in $k$, then appending one odd-length run of $k$:

$$B_k=A_k(1+F-B_k).$$

Solving:

$$B_k=\frac{A_k(1+F)}{1+A_k}.$$

Summing over all $k\ge1$:

$$F=(1+F)\sum_{k\ge1}\frac{A_k}{1+A_k}.$$

Since

$$\frac{A_k}{1+A_k} = \frac{x^k}{1+x^k-x^{2k}},$$

define

$$S(x)=\sum_{k\ge1}\frac{x^k}{1+x^k-x^{2k}}.$$

Then

$$F=(1+F)S \quad\Longrightarrow\quad F=\frac{S}{1-S}.$$

Now expand

$$\frac{x^k}{1+x^k-x^{2k}} = \sum_{m\ge1}(-1)^{m-1}F_m,x^{mk},$$

where $F_m$ are Fibonacci numbers.

Hence the coefficient of $x^n$ in $S(x)$ is

$$s_n=\sum_{d\mid n}(-1)^{d-1}F_d.$$

Let

$$G(x)=1+F(x)=\frac1{1-S(x)}.$$

Then $G_0=1$ and

$$G_n=\sum_{k=1}^n s_k,G_{n-k}.$$

Using an $O(n\log n)$ CDQ + NTT implementation modulo

$$1111124111,$$

we compute:

$$F(10^5)=G_{100000}.$$

The result is

Answer: 57322484