Project Euler Problem 624

Solution

Answer: 984524441

Let $M$ be the toss index when the first occurrence of two consecutive heads appears (so tosses $M-1,M$ are HH). We seek

$$P(n)=\Pr(n\mid M)$$

for $n=10^{18}$, then compute

$$Q(P(n),p) \quad\text{with}\quad p=1{,}000{,}000{,}009.$$

1. Mathematical analysis

Step 1: Distribution of $M$

To have $M=m$, the sequence:

must end in HH,
must contain no earlier HH.

The number of valid binary strings of length $m$ ending in the first HH is a Fibonacci count.

Let $A_m$ be the number of valid sequences ending at toss $m$.

If the first HH occurs at toss $m$, then toss $m-1$ and $m$ are H,H, and the first $m-2$ tosses must avoid consecutive heads and end in T.

This gives:

$$A_m = F_{m-1}$$

where $F_k$ is the Fibonacci sequence ($F_0=0,F_1=1$).

Hence

$$\Pr(M=m)=\frac{F_{m-1}}{2^m}.$$

$$P(n) = \sum_{k\ge1} \frac{F_{kn-1}}{2^{kn}}.$$

Step 2: Convert to a closed form

Using Binet’s formula:

$$F_m=\frac{\phi^m-\psi^m}{\sqrt5},$$

where

$$\phi=\frac{1+\sqrt5}{2}, \qquad \psi=\frac{1-\sqrt5}{2}.$$

Then

$$F_{kn-1} = \frac{\phi^{kn-1}-\psi^{kn-1}}{\sqrt5}.$$

Substitute into the sum:

$$P(n) = \sum_{k\ge1} \frac{1}{2^{kn}} \cdot \frac{\phi^{kn-1}-\psi^{kn-1}}{\sqrt5}.$$

Each part is geometric, so after summing and simplifying:

$$P(n) = \frac{ 2^nF_{n-1}-(-1)^n }{ 4^n-2^nL_n+(-1)^n },$$

where $L_n$ is the Lucas number:

$$L_n = F_{n-1}+F_{n+1}.$$

Check the examples:

For $n=2$:

$$P(2)=\frac{4\cdot1-1}{16-4\cdot3+1} =\frac35.$$

For $n=3$:

$$P(3)=\frac{8\cdot1-(-1)}{64-8\cdot4-1} = \frac{9}{31}.$$

Both match the statement.

Step 3: Modular interpretation

We need

$$Q!\left(P(n),p\right)$$

which is the unique residue $q$ satisfying

$$a \equiv bq \pmod p$$

for $P(n)=a/b$.

Thus

$$Q(P(n),p) = a,b^{-1}\pmod p.$$

So we only need numerator and denominator modulo $p$.

For $n=10^{18}$, compute:

$F_{n-1}\pmod p$,
$F_{n+1}\pmod p$,
$L_n=F_{n-1}+F_{n+1}\pmod p$,
$2^n\pmod p$,
$4^n\pmod p$,

using fast doubling Fibonacci in $O(\log n)$.

2. Python implementation

MOD = 1_000_000_009
N = 10**18

def fib(n, mod):
    """Fast doubling Fibonacci.
    Returns (F_n, F_{n+1}) modulo mod.
    """
    if n == 0:
        return (0, 1)

    a, b = fib(n >> 1, mod)

    # F(2k)
    c = (a * ((2 * b - a) % mod)) % mod

    # F(2k+1)
    d = (a * a + b * b) % mod

    if n & 1:
        return d, (c + d) % mod
    return c, d

# Fibonacci values
Fn_minus_1 = fib(N - 1, MOD)[0]
Fn, Fn_plus_1 = fib(N, MOD)

# Lucas number: L_n = F_{n-1} + F_{n+1}
Ln = (Fn_minus_1 + Fn_plus_1) % MOD

# Powers
pow2 = pow(2, N, MOD)
pow4 = pow(4, N, MOD)

# Since N = 10^18 is even, (-1)^N = 1
sign = 1

# Numerator and denominator modulo MOD
numerator = (pow2 * Fn_minus_1 - sign) % MOD
denominator = (pow4 - pow2 * Ln + sign) % MOD

# Modular division
answer = numerator * pow(denominator, MOD - 2, MOD) % MOD

print(answer)

3. Code walkthrough

Fast doubling

The identities:

$$F_{2k}=F_k(2F_{k+1}-F_k),$$

$$F_{2k+1}=F_k^2+F_{k+1}^2$$

allow Fibonacci computation in $O(\log n)$.

The function returns:

$$(F_n,F_{n+1})$$

so we can recover everything needed.

Lucas number

We use:

$$L_n = F_{n-1}+F_{n+1}.$$

Probability formula

Since $N$ is even:

$$(-1)^N=1.$$

Thus:

$$a = 2^N F_{N-1}-1,$$

$$b = 4^N - 2^N L_N + 1.$$

Finally:

$$Q(P(N),p)=a,b^{-1}\pmod p.$$

Small-example verification

For $n=2$:

$$P(2)=\frac35$$

and modulo $109$:

$$5^{-1}\cdot3 \equiv 66.$$

For $n=3$:

$$P(3)=\frac9{31}$$

and modulo $109$:

$$31^{-1}\cdot9 \equiv 46.$$

Both agree with the problem statement.

4. Final verification

Formula reproduces the given examples exactly.
Complexity is $O(\log n)$, feasible for $10^{18}$.
Denominator is invertible modulo $1{,}000{,}000{,}009$ (nonzero mod prime).
Final modular computation yields:

Answer: 984524441