Are there Fibonacci numbers starting with 2012? (continued)
Almost 8 months ago I left the first part of this post unfinished planning to complete it in the morning; seems I slept too long. (Or as this guy said after a 2-year hiatus: “Sorry for the pause guys. I was in the bathroom.”)
Recall: To get a power of 2 that starts with a prefix (like ), we want such that the fractional part of lies between those of and (all logarithms here to base 10), and similarly to get a Fibonacci number starting with , we want (with some hand-waving) such that the fractional part of lies between those of and . The more general problem is:
Problem: Given an irrational number and an interval , find such that lies in the interval .
Here is one method, based on Edward Burger’s book Exploring the Number Jungle. Let be the midpoint of the interval . Then we are trying to find such that is close to .
- Find a fraction approximating , such that . (These are the convergents of the continued fraction of , but in practice it seems you can also get away with taking semi-convergents that may not satisfy this property.)
- Let be the closest integer to . Note that this automatically means
- Write with . This you can do quite easily with the Euclidean algorithm.
- Then for and , we have (it is a simple exercise to prove this)
- This means that the distance between and is small, modulo 1. If this distance turns out to be still too large, start with a bigger convergent .
The thing we’re doing here is called inhomogeneous Diophantine approximation.