Are there Fibonacci numbers starting with 2012?
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:
- There are infinitely many such numbers.
- In fact, the fraction of (powers of 2 / Fibonacci numbers) starting with 2012 is exactly
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,
Thus a power of 2, say 2n, starts with p iff
Taking logarithms to base 10 and simplifying, this is equivalent to
This is saying that the fractional part of lies between the fractional parts of and For example, if , this means that the fractional part of lies between and .
Similarly, for Fibonacci numbers, as is (or should be) well-known, the nth Fibonacci number Fn is the closest integer to , where is the golden ratio. So starts with iff
Taking logarithms to base 10 and simplifying, while ignoring the annoying which becomes irrelevant in the limit (this line is not rigorous), this is equivalent to
which means that the fractional part of lies between the fractional parts of and . For , this means that the fractional part of lies between and .
In either case, we are trying to make the fractional part of , for some irrational number , lie in some interval. The relevant fact is this:
Theorem 1: for any irrational number , the sequence (where denotes the fractional part of ) is dense in .
or, in other words,
Theorem 1: For any irrational number , the sequence is dense modulo .
Proving this theorem is a good exercise.
This means that for any interval you want, you can always find some such that the fractional part of lies in your interval. In fact, because the sequence is dense, you can find an infinite sequence of such that the fractional parts of 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 , the numbers are uniformly distributed modulo 1.
This means that for any interval of size (say), the fraction of integers for which lies in the interval satisfies
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 is exactly 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.