Detailed mathematical approach

Problem Summary

The problem asks for the first Fibonacci index \(k\) such that the first nine digits of \(F_k\) and the last nine digits of \(F_k\) are both 1-9 pandigital. In other words, each of those 9-digit blocks must contain every digit from 1 through 9 exactly once, with no zero and no repetition.

The obstacle is scale. By the time the answer appears, the Fibonacci number itself has tens of thousands of digits, so constructing it exactly at every step would be wasteful. The implementations therefore split the question into two smaller numerical views of the same sequence: the tail is handled exactly with modular arithmetic, while the head is reconstructed from logarithms.

Mathematical Approach

Let the Fibonacci sequence be defined by \(F_1=1\), \(F_2=1\), and \(F_n=F_{n-1}+F_{n-2}\) for \(n \ge 3\). The search condition is naturally the conjunction of two tests on the same index \(n\): one test on \(F_n \bmod 10^9\), and one test on the leading decimal digits of \(F_n\).

Splitting the Condition into Tail and Head

If the last nine digits are all that matter, then the entire problem lives modulo \(10^9\). If the first nine digits are all that matter, then only the decimal order of magnitude and mantissa matter. Those two facts let us avoid big integers in the main loop.

The key point is that the Fibonacci recurrence survives reduction modulo any integer:

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

At the same time, the size of \(F_n\) is controlled by Binet's formula, which makes the leading digits accessible through logarithms.

Trailing Nine Digits from the Fibonacci Recurrence

Maintain two consecutive residues modulo \(10^9\). If at some moment they represent \(F_{n-2} \bmod 10^9\) and \(F_{n-1} \bmod 10^9\), then one update produces \(F_n \bmod 10^9\). This invariant stays true for the entire scan, so the last nine digits are always known exactly, even though the full integer is enormous.

A 9-digit block is 1-9 pandigital precisely when its digits are the set \(\{1,2,\dots,9\}\). The C++, Python, and Java implementations all enforce the same condition, either by extracting digits and marking them or by checking a 9-character decimal string. A useful checkpoint is

$F_{541}\equiv 839725641 \pmod{10^9},$

and the block \(839725641\) is indeed pandigital. This shows that the trailing test can succeed much earlier than the full two-sided condition.

Leading Nine Digits from Logarithms

For the front of the number, the implementations use

$F_n=\frac{\varphi^n-\psi^n}{\sqrt5},\qquad \varphi=\frac{1+\sqrt5}{2},\qquad \psi=\frac{1-\sqrt5}{2}.$

Because \(|\psi| \lt 1\), the term \(\psi^n\) decays exponentially. For the indices relevant here, it is far too small to affect the first nine digits, so \(F_n\) is governed by \(\varphi^n/\sqrt5\).

Take base-10 logarithms and define

$x=n\log_{10}\varphi-\log_{10}\sqrt5.$

Write \(x=m+f\) with integer part \(m=\lfloor x \rfloor\) and fractional part \(0 \le f \lt 1\). Then

$F_n \approx 10^x = 10^{m+f}=10^m\cdot 10^f.$

The factor \(10^m\) determines the number of digits, while \(10^f\) determines the leading significand. Therefore the first nine digits are

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

This is the central formula used by all three implementations for the head of \(F_n\).

Worked Example: a Leading-Digit Check

A concrete checkpoint from the implementations is \(n=2749\). For this index,

$x=2749\log_{10}\varphi-\log_{10}\sqrt5 \approx 574.157538045.$

So \(f \approx 0.157538045\), and

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

The block \(143726895\) is 1-9 pandigital, so \(F_{2749}\) passes the leading-digit test. It does not yet solve the full problem because the trailing block at the same index is not pandigital. The final answer is the first index where both checks succeed simultaneously.

Why the Combined Filter Is Efficient and Reliable

The tail test is exact and very cheap: one modular addition plus a 9-digit scan. The head test is also \(O(1)\), but it uses floating-point logarithms, so it is sensible to apply it only after the tail has already passed. In practice, trailing-pandigital Fibonacci residues are rare, so most indices are rejected before any logarithmic work is needed.

The numerical approximation is stable here because the first nine digits depend only on the fractional part of \(x\), and double or long-double precision is more than sufficient for indices in the few-hundred-thousand range. One implementation adds a tiny safeguard before converting \(10^{f+8}\) to an integer, protecting against boundary effects when floating-point rounding lands extremely close to \(10^9\).

How the Code Works

The C++, Python, and Java implementations perform a forward scan through Fibonacci indices starting at \(n=3\). At each iteration they update two consecutive Fibonacci values modulo \(10^9\), so the running state always represents adjacent terms of the recurrence reduced to their last nine digits.

Next comes the pandigital filter on the trailing block. The string-based implementations format the residue as a 9-digit decimal block so that leading zeros are preserved before checking the digit set. The integer-based implementation extracts digits numerically and accepts only values with exactly nine digits, no zero, and no repetition. Those are two representations of the same mathematical test.

Whenever the trailing block passes, the implementation computes the leading block from the logarithmic formula. It then applies the same pandigital condition to that 9-digit prefix. As soon as both tests succeed for the same index, the scan terminates and returns the first valid index, which is \(k=329468\).

Complexity Analysis

If the first successful index is \(k\), the algorithm performs \(k-2\) Fibonacci updates. Every iteration uses constant time: one modular addition, one 9-digit pandigital check, and only occasionally one logarithm-based leading-digit computation. Hence the total running time is \(O(k)\).

For this problem the search stops at \(k=329468\), so the real workload is only a few hundred thousand iterations. The memory usage is \(O(1)\), since the scan stores only two current Fibonacci residues, a handful of floating-point constants, and small temporary digit-tracking state.

Footnotes and References

1. Problem page: Project Euler 104 - Pandigital Fibonacci ends
2. Fibonacci number: Wikipedia - Fibonacci number
3. Binet's formula: Wikipedia - Closed-form expression for Fibonacci numbers
4. Golden ratio: Wikipedia - Golden ratio
5. Pandigital number: Wikipedia - Pandigital number
6. Logarithm: Wikipedia - Logarithm