Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given some prefix how can we check if this prefix belongs to a Fibonacci number? If yes then to which one?

By the prefix of number I define first $n$ digits. For example

10 is prefix of 10231
1234 is prefix of 1234592

and so on.

I was trying to get anything from Binet's formula, but couldn't... Thanks for any tip.

share|improve this question
    
To clarify, given a certain string of digits, you want to find if they're the first few digits of some Fibonacci number? –  J. M. Oct 22 '11 at 15:49
    
yes, exactly, thats what i meant –  Chris Oct 22 '11 at 16:05
2  
Given any prefix, there is always a Fibonacci number with that prefix (and in fact, infinitely many such Fibonacci numbers). See André's answer. Basically, $F_n$ is the integer closest to $\frac{\phi^n}{\sqrt{5}}$, so given a prefix $p$, you're trying to find an $n$ such that for some number $k$, you have $$(p)10^k < \frac{\phi^n}{\sqrt{5}} < (p+1)10^k$$. See my answer to this question for an explicit way of finding such $n$. –  ShreevatsaR Oct 22 '11 at 17:04
add comment

2 Answers

up vote 4 down vote accepted

Given any prefix, there is always a Fibonacci number (and in fact, infinitely many Fibonacci numbers) with that prefix. Just for completeness, here is an elaboration of André's answer, which also answers the "if yes then to which one" part.


I'll work with a specific prefix, $42$, but the method is general. So you're trying to find a Fibonacci number $F_n$ which starts with $42$: that is, for some number $k$, $$4.2\cdot10^k \le F_n < 4.3\cdot10^k$$ Because $F_n$ is always the integer closest to $\frac{\phi^n}{\sqrt5}$ (where $\phi = \frac{1+\sqrt 5}2$ is the golden ratio), this is (almost) the same as: $$4.2\cdot10^k \le \frac{\phi^n}{\sqrt{5}} < 4.3\cdot10^k$$ So let's solve that instead. (The "almost" is because $\frac{\phi^n}{\sqrt5}$ could lie in $(4.3\cdot10^k - 0.5, 4.3\cdot10^k)$ so that $F_n = 4.3\cdot10^k$, but in that case we can just try again and find another $n$… or pick something like $425$ as the prefix to start with.)

Taking logs to base $10$, you want $$k + \log 4.2 \le n\log\phi - \log\sqrt5 < k + \log 4.3$$ or $$0.9727 \approx \log 4.2 + \log\sqrt5 \le n\log\phi -k < \log 4.3 + \log\sqrt5 \approx 0.98295$$

Thus we want $n$ such that the fractional part of $n \log \phi$ lies in $(\log 4.2 + \log\sqrt5, \log 4.3 + \log\sqrt5)$.


Adapting what I wrote in another answer, one way to find such $n$ is:

  • Let $\alpha = \frac{\log 4.2 + \log 4.3}{2} + \log{\sqrt5}$ be the midpoint of the interval in which you want $n\log\phi$ to lie, and let $\beta = \frac{\log 4.3 - \log 4.2}{2}$ be the width of that interval.

  • Pick relatively prime $a$ and $b$ such that $|b\log\phi - a| < \frac1b$. For instance, you can pick a convergent $\frac{a}{b}$ of the continued fraction of $\log \phi$. Let $b$ be large enough so that $\frac3b \le \frac{\beta}{2}$, i.e., $b \ge \frac6{\beta}$. (In practice, a smaller $b$ will also do.)

  • Let $N$ be the closest integer to $b\alpha$.

  • Write $N$ as $av - bu$ with $|v| \le \frac{b}{2}$ (using the extended Euclidean algorithm).

  • Pick $n = b + v$ and $k = a + u$, then $|n\log\phi - k - \alpha| < \frac3b \le \frac{\beta}2$.
    So $42$ is a prefix of the Fibonacci number $F_n$.


Doing this example with actual numbers:

  • Here, $\frac6{\beta}$ is about $1174.26$, and the convergents of $\log\phi$ are $\frac14, \frac15, \frac4{19}, \frac5{24}, \frac9{43}, \frac{14}{67}, \frac{93}{445}, \frac{386}{1847}, \dots$, so we take $a = 386$, $b = 1847$.

  • The closest integer to $1847\alpha$ is $N = 1806$.

  • $1806 = 386v - 1847u = 386(-225) - 1847(-48)$. That is, $v = -225$, $u = -48$.

  • $n = b + v = 1847 - 225 = 1622$, and $k = a + u = 386 - 48 = 338$, and indeed the Fibonacci number $F_{1622} = 425076879\dots326170761$. (339 digits)

Note that doing the calculation with the previous convergent $\frac{93}{445}$ will give the earlier Fibonacci number $F_{665} = 423931574\dots49753165$ (139 digits), and there are earlier Fibonacci numbers like $F_{86} = 420196140727489673$ and $F_{153} = 42230279526998466217810220532898$, most of which you can get by starting with semiconvergents (for instance you get $F_{86}$ if you start with $\frac{23}{110}$, and $F_{153}$ if you start with $\frac{51}{244}$).

So this method may not(?) give the smallest Fibonacci number with a given prefix, but it is a fast way of finding infinitely many such Fibonacci numbers.


The same method works with any prefix in place of $42$.

share|improve this answer
    
Wow that solution is beautiful. Thanks a lot. –  Chris Oct 24 '11 at 7:56
add comment

Your idea of using the Binet Formula can be made to work.

If for arbitrarily large $n$, $\frac{\varphi^n}{\sqrt{5}}$ has any specified prefix $P$, then for arbitrarily large $n$, $F_n$ has any specified prefix $Q$. (If we are worried about a prefix like $2000$, change it to $20001$. If $\frac{\varphi^n}{\sqrt{5}}$ has $20001$ as a prefix, and $n$ is large, then $F_n$ has $2000$ as a prefix.)

Now we show that for any $P$, there are infinitely many $n$ such that $\frac{\varphi^n}{\sqrt{5}}$ has prefix $P$. Consider $\log_{10}\frac{\varphi^n}{\sqrt{5}}=n\,\log_{10}\varphi -\log_{10}\sqrt{5}$. It is easy to show that $\log_{10}\, \varphi$ is irrational. Thus the fractional parts of $n\,\log_{10}\varphi$, as $n$ ranges over the natural numbers, are dense in the unit interval, and therefore so are the fractional parts of $n\,\log_{10}\varphi -\log_{10}\sqrt{5}$. The result follows.

Comment: The above solution gives no real information about the "if so which one" part of the question. There are infinitely many. One would like to produce a decent upper bound for the smallest one. Calculations I have made with continued fractions for very similar problems, such as producing a specified prefix for $2^n$, have not given good bounds.

share|improve this answer
    
The fractional parts are not just dense but uniformly distributed, and better yet, good estimates are known for its discrepancy. So there's a pretty good chance that any given $k$-digit prefix shows up for some $n\le10^k$, and using the discrepancy you can probably get a bound not all that much bigger than $10^k$ by which time every $k$-digit prefix has turned up. –  Gerry Myerson Oct 24 '11 at 5:04
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.