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
There are other ways to compute it?
[Math] Fibonacci sequence inversion
sequences-and-series
Related Solutions
In response to Mark's comment, it is possible to determine that the probability of $X_n=0$ decays exponentially directly, and this is in fact easier than the theorems about the growth of these random sequences.
Since we only care about testing if the sequence becomes zero, symmetry implies that we might as well reduce to the case $X_n=|X_{n-1}\pm X_{n-2}|$. If you see the paper "The random Fibonacci recurrence and the visible points of the plane" by T. Kalmar-Nagy, these sequences are in bijection with random walks on an infinite directed graph which looks like a trivalent tree with added parallel edges at every level.
The probability you ask for can be translated into the question of the probability that a random walk in our graph returns to the origin after $n$ steps. There is a lot of machinery available for studying random walks on highly symmetric graphs (in this case we don't have a Cayley graph, but it's really close). I did the following simple estimate: The number of walks of length $3n$ starting from the origin is $2^{3n}$. For such a path to return to the origin exactly a third of its edges are directed south-west (I'm referring to the fig. 4 on page 4 of the paper I linked to). So the numbers of paths of length $3n$ with both endpoints at the origin is at most $\binom{3n}{n}\sim (27/4)^n$. So in particular the probability that $X_{3n}=0$ is bounded above by $(27/32)^n$.
Added: Here's how one can get a lower bound as well. It is not hard to see that walks of length $3n$ in our graph are in bijection with sequences $\lbrace a_1,a_2,\dots,a_{3n}\rbrace$ which satisfy $a_i\in \lbrace 1,-\frac{1}{2}\rbrace$ and $$a_1+\cdots+a_{3n}= 0$$ $$a_1+\cdots+a_m\geq 0$$ for all $1\le m\le 3n$, and if $a_1+\cdots+a_m=\frac{1}{2}$ then $a_{m+1}=-\frac{1}{2}$. Enumerating these sequences exactly can get a bit tricky but there is a particularly nice subset if we restrict to the stronger condition $$a_1+\cdots+a_m > 1$$ for all $2\le m\le 3n-3$. Then we can enumerate these as Dyck paths on rectangles. The formula from that thread gives us $\frac{1}{3n-3}\binom{3n-3}{n-1}$. So to summarize we have $$\frac{1}{(3n-3)2^{3n}}\binom{3n-3}{n-1}\le P(X_{3n}=0)\le \frac{1}{2^{3n}}\binom{3n}{n}$$ and in particular $$\lim_{n\to \infty} \sqrt[n]{P(X_{3n}=0)}=\frac{27}{32}$$ which matches the experimental data in jc's answer.
This example is discussed in my 1990 PhD thesis, where is it is shown that $\nu(p)$ is a real analytic function of $p$. The thesis was written in Hebrew, but this result was generalized in two papers [1], [2]. Note that the existence of the limit you call the Viswanath constant (and more generally, $\nu(p)$) is an immediate consequence of the Furstenberg-Kesten Theorem [3] on the existence of the top Lyapunov exponent for random matrix products. This is because the vector $(F_n,F_{n+1})$ is obtained by multiplying $(F_{n-1},F_n)$ by a random matrix that takes two possible values.
[1] Peres, Yuval Analytic dependence of Lyapunov exponents on transition probabilities. Lyapunov exponents (Oberwolfach, 1990), 64–80, Lecture Notes in Math., 1486, Springer, Berlin, 1991.
[2] Peres, Yuval Domains of analytic continuation for the top Lyapunov exponent. Ann. Inst. H. Poincaré Probab. Statist. 28 (1992), no. 1, 131–148. (Reviewer: Philippe Bougerol) http://www.numdam.org/article/AIHPB_1992__28_1_131_0.pdf
[3] Furstenberg, Harry, and Harry Kesten. "Products of random matrices." The Annals of Mathematical Statistics 31, no. 2 (1960): 457-469.
Best Answer
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.