Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

How do I get the index in the sequence from the Fibonacci number?

0 1 1 2 3 5 8 13 21 34...

For example

N(3) = 4 (starting from zero)

N(34) = 9 (starting from zero)

..

N(X) = ?

I've seen an equation in wikipedia

alt text

There are other ways to compute it?

share|improve this question
8  
What's wrong with the logarithm? –  Qiaochu Yuan Sep 17 '10 at 18:02
1  
There's a sense in which the logarithm seems inelegant here, I think. –  Michael Lugo Sep 17 '10 at 18:43
1  
If a logarithm is distasteful, then you could also just iteratively compute the Fourier series until you find a number which is either greater than or equal to the number you are looking for. By doing this, you would ultimately find the index you want in time proportional to its location in the sequence. Since the Fourier series terms grow exponentially, this algorithm would be polynomial on the size of the input number (in bits), and so it isn't really that inefficient. –  Mikola Sep 17 '10 at 20:11
6  
The logarithm seems inevitable, but you can get rid of the floor function at the expense of some square roots. Just observe that $5F_n^2-2=\varphi^{2n}+\varphi^{-2n}$ and solve a quadratic equation in $\varphi^{2n}$. –  Sergei Ivanov Sep 17 '10 at 20:21
add comment

6 Answers 6

up vote 7 down vote accepted

As the previous answers have stated the map from $F_n \rightarrow n$ is essentially a logarithm. Since the binary representation of $F_n$ has about $c n$ bits (for the appropriate constant $c = \log_2 \phi$, where $\phi = (1+\sqrt{5})/2$), the bit complexity of calculating the logarithms is about $c' \log^2 n$, for some constant $c'$. Here's another simpler method which has the same complexity:

If you are given $F_n$ for some unknown $n$ if you knew $F_{n-1}$ with $n$ subtractions you can find out what $n$ is (run the fibonacci recursion in reverse). But $F_n/F_{n-1} \approx \phi$. So if you know $1/\phi$ to about $2n$ bits of precision you can find $F_{n-1}$ by multiplying by $1/\phi$ and rounding to the nearest integer. This calculation is certainly simpler than taking logs.

Another alternative is to take $p$-adic logarithms: the function $n \rightarrow F_n$ is $p$-adically continuous, so since $\mathbb{Z}$ is dense in $\mathbb{Z}_p$ it defines a unique $p$-adically continuous function, which by a criterion of Mahler is analytic. You can invert the function via Newton's method -- you just need to find the answer mod $p$ to get a starting point.

share|improve this answer
1  
Hendrik Lenstra's paper "Profinite Fibonacci Numbers" is relevant to the $p$-adic version mentioned above math.leidenuniv.nl/~hwl/papers/fibo.pdf –  Victor Miller Sep 18 '10 at 2:23
    
By your information count, knowing the number of binary digits of $N=F_n$ still misses less than one bit to identify $n$. So there should be a practical formula based on the number of binary digits of $F_n$ and for instance the second digit... –  Pietro Majer Nov 4 '13 at 15:27
add comment

Well, you can almost certainly use integer and modular arithmetic, with the Chinese remainder theorem, because the sequence is periodic for any modulus n you want. This requires some pre-computation, but probably you can predict how much in advance if you know how large a Fibonacci number ahead of time.

For example, I know the index for 34 must be a multiple of 3, just because 34 is even.

Edit: In practical terms perhaps you just sieve on a range on integers instead of using the Chinese remainder theorem (see comments)? Using the number of bits of input as the complexity measure N, you'd need a range of length proportional to N (take some easy rational upper and lower bounds to log 2/log (golden ratio)). Then looking mod 2 you can strike out at least one third of the numbers. Modulo other small primes you strike out some proportion which depends on case but is not too small. You are going to continue until only one integer from the range remains as a candidate. This really doesn't look too bad: the period mod p may be large or small, but what matters is the proportion of the time a given residue class appears.

share|improve this answer
    
You shouldn't need much precomputation. Just knowing the number of digits of the Fibonacci number in question, you can compute n to within a constant factor, and after that it shouldn't be hard to use modular considerations to pin the index down precisely (if you really, really want to avoid using logarithms for some reason). –  Qiaochu Yuan Sep 17 '10 at 18:49
1  
If you wanted to compute this quickly, logs are hard to compute exactly. –  Michael Lugo Sep 17 '10 at 18:58
    
In particular the sequence is periodic with period at most $n^2-1$ modulo any integer $n \ge 1$ (the proof is elementary and nearly obvious). So to do CRT you just need a bunch of primes (or maybe prime powers?). Shouldn't be much bigger than $n^2$? –  drvitek Sep 18 '10 at 0:14
add comment

You can find the index using only integer arithmetic.

Since $F_n$ is monotone one can use Binary search using the fact that $F_i$ can be computed in $O(\log(i))$.

This method works for all monotone sequences and can be used to check if a number is in the sequence.

share|improve this answer
add comment

For what it's worth, this is essentially A072649 in Sloane (http://oeis.org/A072649). All the formulas given there for that formula either are in terms of the logarithm or assume the Fibonacci numbers are already known and just search that sequence.

share|improve this answer
add comment

Any such formula has a problem in that two consecutive elements of the sequence are equal to 1. So any formula applies for sufficiently large members of the sequence.

Another question is whether you know that the number is a Fibonacci number and want to find the index, or whether the question involves detecting whether the number is a Fibonacci number and also determining its position in the sequence.

share|improve this answer
add comment

Invert the formula $F(n)= (r^n - (1-r)^n)/\sqrt{5}$ where $r=(1+\sqrt{5})/2$ by the Lagrange Inversion Formula (LIF). Let $X=\sqrt{5}*F(n)$ and $s=1-r$ so $X=r^n - s^n$. So

$$X=\sum_{j=0}^\infty \frac{(\ln(r))^j - (\ln(s))^j}{j! n^j}$$

Then n = X + sum of X^j * sum over all sequences (b(2),b(3),....,) of nonnegative integers of (-1)^(sum of b(i) from i=2 to j) * ( (sum of b(i) from i=2 to j) + j-1)!/(j!) * product from i=2 to j of (((ln(r))^i - (ln(s))^i)/i!)^b(i) / (b(i)!) ) such that sum of (i-1)*b(i) from i=2 to j equals j-1 and pray for convergence everywhere.

I got this form of the LIF from page 264 of G.P. Egorychev's book, "Integral Representations of Combinatorial Sums"

share|improve this answer
    
@resolvent: the LaTeX support exists for a reason. Use it and your formulae will appear much nicer (I fixed up the first paragraph for ya!). Also, proper handling of equation makes it clearer what you meant. For the displayed equation for $X = \ldots$ above, I had to guess whether you meant that $n^j$ factor to go in the denominator or the numerator. I probably guessed wrong, but it wasn't clear from how you written it in in-line text form. Please try to see if you can fix up the second paragraph? –  Willie Wong Oct 4 '10 at 16:58
    
(I mean, it is okay if it is some simple things, but with all the sums and square roots floating around, you really should take advantage of the LaTeX display.) –  Willie Wong Oct 4 '10 at 17:00
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.