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 $p$ (like $p = 2012$ ), we want $n$ such that the fractional part of $n\log 2$ lies between those of $\log p$ and $\log(p+1)$ (all logarithms here to base 10), and similarly to get a Fibonacci number starting with $p$ , we want (with some hand-waving) $n$ such that the fractional part of $n\log\phi$ lies between those of $\log(p) + \log{\sqrt{5}}$ and $\log(p+1) + \log{\sqrt{5}}$ . The more general problem is:

Problem: Given an irrational number $\theta$ and an interval $(a,b) \subset (0,1)$ , find $n$ such that $\mathrm{frac}(n\theta)$ lies in the interval $(a,b)$ .

Here is one method, based on Edward Burger’s book Exploring the Number Jungle. Let $\alpha$ be the midpoint of the interval $(a,b)$ . Then we are trying to find $n$ such that $\mathrm{frac}(n\theta)$ is close to $\alpha$ .

Find a fraction $\displaystyle \frac{p}{q}$ approximating $\theta$ , such that $\displaystyle |q\theta - p| < \frac1q$ . (These are the convergents of the continued fraction of $\theta$ , but in practice it seems you can also get away with taking semi-convergents that may not satisfy this property.)
Let $N$ be the closest integer to $q\alpha$ . Note that this automatically means $\displaystyle |q\alpha - N| \le \frac12$
Write $\displaystyle N = yp - xq$ with $\displaystyle |y| \le \frac{q}{2}$ . This you can do quite easily with the Euclidean algorithm.
Then for $n = q + y$ and $k = p + x$ , we have (it is a simple exercise to prove this)
$\displaystyle |\theta n - k - \alpha| < \frac{3}{n}$
This means that the distance between $n\theta$ and $\alpha$ is small, modulo 1. If this distance turns out to be still too large, start with a bigger convergent $\frac{p}{q}$ .

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.]

Written by S

Fri, 2012-08-03 at 01:56:18

Posted in mathematics

S	M	T	W	T	F	S
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

The Lumber Room