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.
[Originally posted on math.stackexchange, here and here.]
Leave a Reply