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
.
I think I had some code to post as well (hey, what’s the actual Fibonacci number that starts with 2012?), but it needs to be cleaned up… probably this works (in Sage).
The thing we’re doing here is called inhomogeneous Diophantine approximation.
Leave a Reply