The Lumber Room

"Consign them to dust and damp by way of preserving them"

Are there Fibonacci numbers starting with 2012? (continued)

leave a comment »

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

About these ads

Written by S

Fri, 2012-08-03 at 01:56:18 +05:30

Posted in mathematics

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 67 other followers