Solution

Answer: 329468

We seek the first Fibonacci index $k$ such that:

the first 9 digits of $F_k$ are pandigital $1\text{-}9$,
and the last 9 digits of $F_k$ are also pandigital $1\text{-}9$.

A 9-digit number is pandigital iff it contains each digit $1,\dots,9$ exactly once.

Mathematical analysis

The Fibonacci numbers satisfy

$$F_n = F_{n-1}+F_{n-2}, \qquad F_1=F_2=1.$$

The naive approach of computing full Fibonacci numbers is infeasible because the relevant term has hundreds of thousands of digits. We therefore treat the leading and trailing digits separately.

1. Trailing 9 digits

To track the last 9 digits, we use modular arithmetic.

Since

$$F_n \equiv F_{n-1}+F_{n-2}\pmod{10^9},$$

we only store:

$$F_n \bmod 10^9.$$

This keeps every computation small and fast.

At each step we test whether the last 9 digits are pandigital:

set(str(b).zfill(9)) == set('123456789')

The zfill(9) ensures leading zeros are preserved; any zero automatically fails the pandigital test.

2. Leading digits via logarithms

The key identity is Binet’s formula:

$$F_n = \frac{\phi^n-\psi^n}{\sqrt5},$$

where

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

Because $|\psi|<1$, for large $n$,

$$F_n \approx \frac{\phi^n}{\sqrt5}.$$

Taking base-10 logarithms:

$$\log_{10}(F_n) \approx n\log_{10}(\phi)-\log_{10}(\sqrt5).$$

Write this as

$$\log_{10}(F_n)=I+f,$$

where:

$I$ is the integer part,
$f\in[0,1)$ is the fractional part.

Then

$$F_n = 10^{I+f}=10^I\cdot 10^f.$$

The first 9 digits are therefore:

$$\left\lfloor 10^{f+8}\right\rfloor.$$

So we compute:

log_fk = k * log_phi - log_sqrt5
frac = log_fk - int(log_fk)
first9 = int(10**(frac + 8))

and test whether first9 is pandigital.

This avoids ever computing the gigantic Fibonacci number itself.

Python implementation

from math import log10, sqrt

# Constants from Binet's formula
phi = (1 + sqrt(5)) / 2
log_phi = log10(phi)
log_sqrt5 = log10(sqrt(5))

# Target pandigital digit set
pan = set('123456789')

# Fibonacci values modulo 10^9
a, b = 1, 1
k = 2

while True:
    # Advance Fibonacci sequence modulo 10^9
    a, b = b, (a + b) % 10**9
    k += 1

    # Check trailing 9 digits
    if set(str(b).zfill(9)) == pan:

        # Approximate leading digits using logarithms
        log_fk = k * log_phi - log_sqrt5
        frac = log_fk - int(log_fk)

        # Extract first 9 digits
        first9 = int(10**(frac + 8))

        # Check leading 9 digits
        if set(str(first9)) == pan:
            print(k)
            break

Code walkthrough

Constants

phi = (1 + sqrt(5)) / 2

Defines the golden ratio:

$$\phi=\frac{1+\sqrt5}{2}.$$

log_phi = log10(phi)
log_sqrt5 = log10(sqrt(5))

Precompute logarithms used repeatedly in Binet’s approximation.

Pandigital target

pan = set('123456789')

A valid 9-digit pandigital number must contain exactly these digits.

Fibonacci iteration

a, b = 1, 1
k = 2

Initial Fibonacci values:

$$F_1=1,\quad F_2=1.$$

Efficient recurrence

a, b = b, (a + b) % 10**9

Stores only the last 9 digits of each Fibonacci number.

Trailing-digit test

set(str(b).zfill(9)) == pan

Example:

123456789 passes,
012345678 fails because of zero,
repeated digits fail automatically.

The problem statement confirms:

$F_{541}$ is the first Fibonacci number with pandigital trailing 9 digits.

This code reproduces that behavior.

Leading-digit extraction

log_fk = k * log_phi - log_sqrt5

Approximates:

$$\log_{10}(F_k).$$

frac = log_fk - int(log_fk)

Extracts the fractional part.

first9 = int(10**(frac + 8))

Converts the fractional logarithm into the first 9 digits.

Final condition

if set(str(first9)) == pan:

Checks whether the leading digits are pandigital too.

When both tests pass, we print the index.

Final verification

The algorithm is extremely efficient because:

trailing digits use modular arithmetic,
leading digits use logarithms,
no gigantic Fibonacci numbers are ever stored.

The known checkpoints from the problem statement are consistent:

$F_{541}$: first pandigital tail,
$F_{2749}$: first pandigital head.

Running the algorithm yields the first index satisfying both conditions.

Answer: 329468

Project Euler Problem 104