Do the Fibonacci numbers contain any run of digits?

Solution 1:

Yes, there is. We can even demand that the prescribed $x$ appears at the beginning of a Fibonacci number.

For large $n$ the Fibonacci number $F_n$ shares its all but possibly the least significant digit with $$F_n\approx\frac1{\sqrt5}\left(\frac{1+\sqrt5}2\right)^n$$ by Binet's formula.

Because $\theta=\log_{10}((1+\sqrt5)/2)$ is irrational the claim follows from Kronecker's density theorem. The argument is the same as here, where the question is about the string of the most significant digits in the decimal expansion of $2^n$.

For the sake of completeness here's the proof for the irrationality of $\theta$. Assume contrariwise that there exists a rational number $m/n$ such that $$ 10^{m/n}=\frac{1+\sqrt5}2. $$ Raising this to power $n$ would then imply that $$ 10^m=\left(\frac{1+\sqrt5}2\right)^n. $$ But here the left hand side is an integer where as the right hand side differs from an integer by the tiny amount $\left(\frac{1-\sqrt5}2\right)^n$.

A way of finding explicit (but not necessarily anywhere near the smallest) values of $n$ is then to find good rational approximations of $\theta$. Here $\theta=0.2089876\ldots$. A good rational approximation is then $$ \frac{14}{67}=0.20895522\ldots $$ This implies that $$ \left(\frac{1+\sqrt5}2\right)^{67}\approx 1.005013\cdot10^{14} $$ is very close to a power of ten. By Binet's formula this means that $F_{n+67}$ begins with a sequence of digits close to that of $F_n$, only slightly "bigger".

For example, if you want a Fibonacci number beginning $32\cdots$, you can do the calculations $$ \begin{aligned} x&=\log_{10}(32\cdot\sqrt5)\approx1.8546\ldots,\\ y&=67\theta-\lfloor 67\theta\rfloor\approx0.0021718967\ldots,\\ m&=(x-\lfloor x\rfloor)/y\approx 393.47\ldots \end{aligned} $$ Then (thanks to Mathematica) you can calculate $$ \begin{aligned} F_{393\cdot67}=3192055\ldots,\\ F_{394\cdot 67}=3200805\ldots,\\ F_{395\cdot67}=3224142\ldots. \end{aligned} $$ You see how incrementing $n$ by $67$ increases the value of the integer formed by seven most significant digits by about $0.5$ per cent.

When that half per cent resolution is not good enough to give you the string you want (happens inevitably for longer strings), you need to look for better rational approximations for $\theta$. The tool for that is given by the theory of continued fractions (and best rational approximations).