The Lumber Room

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

Archive for January 2012

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.

Advertisement

Written by S

Sun, 2012-01-08 at 01:29:26

Posted in mathematics