WARNING: The text below provides a guidance for a Project Euler problem.

• If you pride yourself in tackling problems entirely on your own, you are encouraged to exit this post right now.

• If you are simply looking for a hint for the problem, please visit the »Project Euler’s official forum«. You may find some hints here, but if you don’t want your problem spoiled, scroll cautiously.

• If you are looking for a readily available copy/paste answer, you will not find it here. All of the code snippets in the post have been stripped of some crucial lines (these are clearly marked). It is my aim that anyone able to replicate the answer based on such snippets will have to understand the solution conceptually. At that point, by virtue of learning something new, I believe he deserves it anyway.

• Guidance for future problems will not be published before 100 people have solved the problem and there are at least two more recent problems.



Two heads are better than one

Let $M$ be the random variable counting the number of times we toss an unbiased coin until we obtain two consecutive heads. Let $P(n)$ denote the probability $\mathbb P(n \text{ divides } M)$. The problem revolves about computing $P(n)$ for large values precisely.

As a helper variable, define $Q(n)$ to denote the probability that after $n$ tosses, we obtain precisely a sequence of the form $\dots, H, H$, where in the $\dots$ part (the first $n-2$ tosses) no two consecutive heads appear. Define also $R(n)$ to be the number of sequences of tosses of length $n$, such that no two consecutive heads appear. We have a clear relationship $Q(n) = \frac {R(n - 3)} {2^n}$ between $Q$ and $R$ (because the last three tosses in the sequence where we have encountered a pair of heads for the first time must be precisely $T, H, H$). We can express $P$ in terms of $R$ as

and thus we turn into reasoning about $R$ first. We can obtain a recursive relationship $R(n) = R(n - 1) + R(n - 2)$ by discerning two cases for the last coin toss in the sequence ($R(n-1)$ comes from the case where the last toss is $tails$, $R(n-2)$ from the case where the last toss is $heads$, as then the second to last toss must have necessarily been $tails$). Noticing furthermore that the first values of $R$ are $R(0) = 1, R(1) = 2$, which are precisely the second and third terms of the Fibonacci sequence, the recursive relationship $R(n) = R(n - 1) + R(n - 2)$ actually tells us that $R$ is the Fibonacci sequence $\{F_i\}$ and

The trick for being able to calculate this efficiently is to turn the expression into a geometric series! For this we may use the fact that the Fibonacci numbers can be obtained by matrix exponentiation. In particular, the $n$-th Fibonacci number is the $[0][0]$ entry of the matrix $\mathbb F^{n-1}$ where

$% $.

We may hence rewrite:

The determinant of $\frac {\mathbb F} {2}$ is smaller than one, hence the geometric series $\sum_{i=1}^\infty \left(\frac{\mathbb F^n} {2^n}\right)^i$ converges to:

Finally, we obtain:

At last, calculating $Q(P(n), 10^9+9)$ is nothing else than working out $P(n)$ using modular arithmetic. The following succinct piece of Julia code gives answer in mere $0.005$ seconds.