Fibonacci sequence inversion - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T05:04:28Z http://mathoverflow.net/feeds/question/39124 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/39124/fibonacci-sequence-inversion Fibonacci sequence inversion Hernán Eche 2010-09-17T17:19:38Z 2012-01-08T12:08:19Z <p>How do I get the index in the sequence from the Fibonacci number?</p> <p>0 1 1 2 3 5 8 13 21 34...</p> <p>For example</p> <p>N(3) = 4 (starting from zero)</p> <p>N(34) = 9 (starting from zero)</p> <p>..</p> <p>N(X) = ?</p> <p>I've seen an equation in wikipedia</p> <p><img src="http://upload.wikimedia.org/math/4/6/2/462ccc015b0168c2838cc212ccea259e.png" alt="alt text"></p> <p>There are other ways to compute it?</p> http://mathoverflow.net/questions/39124/fibonacci-sequence-inversion/39128#39128 Answer by Charles Matthews for Fibonacci sequence inversion Charles Matthews 2010-09-17T18:08:04Z 2010-09-18T06:28:36Z <p>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. </p> <p>For example, I know the index for 34 must be a multiple of 3, just because 34 is even. </p> <p><strong>Edit:</strong> 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.</p> http://mathoverflow.net/questions/39124/fibonacci-sequence-inversion/39134#39134 Answer by Michael Lugo for Fibonacci sequence inversion Michael Lugo 2010-09-17T18:57:19Z 2010-09-17T18:57:19Z <p>For what it's worth, this is essentially A072649 in Sloane (http://www.research.att.com/~njas/sequences/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.</p> http://mathoverflow.net/questions/39124/fibonacci-sequence-inversion/39137#39137 Answer by Mark Bennet for Fibonacci sequence inversion Mark Bennet 2010-09-17T19:38:12Z 2010-09-17T19:38:12Z <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/39124/fibonacci-sequence-inversion/39177#39177 Answer by Victor Miller for Fibonacci sequence inversion Victor Miller 2010-09-18T00:47:59Z 2010-09-18T01:31:38Z <p>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:</p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/39124/fibonacci-sequence-inversion/41035#41035 Answer by resolvent for Fibonacci sequence inversion resolvent 2010-10-04T16:06:02Z 2010-10-04T16:55:49Z <p>Invert the formula $F(n)= (r^n - (1-r)^n)/\sqrt{5}$ where $r=(1+\sqrt{5})/2$ by the <a href="http://en.wikipedia.org/wiki/Lagrange_inversion_theorem" rel="nofollow">Lagrange Inversion Formula</a> (LIF). Let $X=\sqrt{5}*F(n)$ and $s=1-r$ so $X=r^n - s^n$. So </p> <p>$$X=\sum_{j=0}^\infty \frac{(\ln(r))^j - (\ln(s))^j}{j! n^j}$$</p> <p>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.</p> <p>I got this form of the LIF from page 264 of G.P. Egorychev's book, "Integral Representations of Combinatorial Sums"</p> http://mathoverflow.net/questions/39124/fibonacci-sequence-inversion/85184#85184 Answer by joro for Fibonacci sequence inversion joro 2012-01-08T12:08:19Z 2012-01-08T12:08:19Z <p>You can find the index using only integer arithmetic.</p> <p>Since $F_n$ is monotone one can use <a href="https://secure.wikimedia.org/wikipedia/en/wiki/Binary_search" rel="nofollow">Binary search</a> using the fact that $F_i$ can be computed in $O(\log(i))$.</p> <p>This method works for all monotone sequences and can be used to check if a number is in the sequence.</p>