# The Lumber Room

"Consign them to dust and damp by way of preserving them"

## Are there Fibonacci numbers starting with 2012?

with one comment

Do there exist powers of 2 whose first four digits are 2012?
Are there Fibonacci numbers whose first four digits are 2012?

If the answer is obvious to you (or you don’t care), you can stop reading.

The answer for both is:

• Yes.
• There are infinitely many such numbers.
• In fact, the fraction of (powers of 2 / Fibonacci numbers) starting with 2012 is exactly

$\displaystyle \frac{\log 2013 - \log 2012}{\log 10} \approx \frac1{4644} \approx 0.000216$

Similarly with any other prefix p (of any length) in place of 2012. Proof follows.

A number x starts with a prefix p if and only if for some k ≥ 0,

$\displaystyle p \cdot 10^k \le x < (p+1) \cdot 10^k$

Thus a power of 2, say 2n, starts with p iff

$\displaystyle p \cdot 10^k \le 2^n < (p+1) \cdot 10^k$ for some $k \ge 0$

Taking logarithms to base 10 and simplifying, this is equivalent to

$\displaystyle \log p < n\log2 - k < \log(p+1)$ for some $k \ge 0$

This is saying that the fractional part of $n\log 2$ lies between the fractional parts of $\log p$ and $\log (p+1).$ For example, if $p = 2012$, this means that the fractional part of $n\log 2$ lies between $\log 2.012 \approx 0.303628$ and $\log 2.013 \approx 0.303844$.

Similarly, for Fibonacci numbers, as is (or should be) well-known, the nth Fibonacci number Fn is the closest integer to $\displaystyle \frac{\phi^n}{\sqrt5}$, where $\displaystyle \phi = \frac{1+\sqrt5}2$ is the golden ratio. So $F_n$ starts with $p$ iff

$\displaystyle p \cdot 10^k - \frac12 \quad < \quad \frac{\phi^n}{\sqrt5} \quad < \quad (p+1) \cdot 10^k - \frac12$

Taking logarithms to base 10 and simplifying, while ignoring the annoying $\frac12$ which becomes irrelevant in the limit (this line is not rigorous), this is equivalent to

$\displaystyle \log(p) + \log\sqrt5 \quad < \quad n\log\phi - k \quad < \quad \log(p+1) + \log\sqrt5$

which means that the fractional part of $n\log \phi$ lies between the fractional parts of $\log p + \log\sqrt5$ and $\log (p+1) + \log\sqrt5$. For $p = 2012$, this means that the fractional part of $n\log \phi$ lies between $\log 2.012 + \log\sqrt5 \approx 0.653113$ and $\log 2.013 + \log\sqrt5 \approx 0.653329$.

In either case, we are trying to make the fractional part of $n\theta$, for some irrational number $\theta$, lie in some interval. The relevant fact is this:
Theorem 1: for any irrational number $\theta$, the sequence $\mathrm{frac}(n\theta)$ (where $\mathrm{frac}(x)$ denotes the fractional part of $x$) is dense in $[0, 1)$.
or, in other words,
Theorem 1: For any irrational number $\theta$, the sequence $n\theta$ is dense modulo $1$.
Proving this theorem is a good exercise.

This means that for any interval you want, you can always find some $n$ such that the fractional part of $n\theta$ lies in your interval. In fact, because the sequence is dense, you can find an infinite sequence of $n$ such that the fractional parts of $n\theta$ converge to the midpoint (say) of the desired interval. This proves the first two facts of the answer, and for the third we need a stronger theorem:

Theorem 2 [Equidistribution theorem]: For any irrational number $\theta$, the numbers $n\theta$ are uniformly distributed modulo 1.

This means that for any interval $I \subset [0,1]$ of size $s$ (say), the fraction of integers $n$ for which $\mathrm{frac}(n\theta)$ lies in the interval satisfies

$\displaystyle \lim_{N \to \infty} \frac{ \left|\left\{ 1 \le n \le N : \mathrm{frac}(n\theta) \in I\right\}\right|}{N} = s$

This proves the third fact. The fraction of Fibonacci numbers (or of powers of a number that is not a power of 10) that start with a prefix $p \ge 1$ is exactly $\log(p+1) - \log(p)$ where log is to base 10.

That much is standard. And non-constructive. We are assured of the existence of such numbers, but how do we actually find one?

The answer (or one answer), as it so often does in these problems, involves continued fractions. Here is one method, [to be continued when I wake up :p]
Edit: Continued here.