How to tell if a Fibonacci number has an even or odd index

We know that $$F_n = \frac{1}{\sqrt 5}(\varphi^n - \hat\varphi^n)$$ where $\varphi = \frac12\big(1+\sqrt 5\big)$ and $\hat\varphi = \frac12\big(1-\sqrt 5\big)$ as usual. Neglecting $\hat\varphi^n$, which is small when $n$ is large, we can calculate $n$ directly as

$$n =\operatorname{round}\left \lbrace \frac{\log F_n + \log\sqrt 5}{\log \varphi} \right\rbrace $$ where “round” means round to the nearest integer. For speed of computation we should simplify this to:

$$n =\operatorname{round}\left \lbrace \alpha\cdot\log F_n+\beta \right\rbrace $$ where the $\alpha$ and $\beta$ constants are precomputed as:

$$\begin{array}{rcl} \alpha & = \frac1{\log\varphi} & \approx 2.078087\\ \beta &= \frac{\log \sqrt 5}{\log \varphi} & \approx 1.672276 \end{array} $$

For example, letting $F_n=233$, we find $n = \operatorname{round}{13.0000076556886} = 13$.

The calculation need not be done very precisely, it only needs to be done with sufficient precision to determine the nearest integer, and it always comes out extremely close to that integer. If the value fell close to a half-integer, one might have to calculate many digits to determine whether it was a little bit more than or a little bit less than $n+\frac12$. But this never happens. The $13.0000076556886$ example above is typical, and as $n$ increases the calculated value becomes increasingly close to the desired integer.

Note that one can approximate the logarithm simply by counting the number of decimal digits in $F_n$ and then multiplying by $\log 10 \approx 2.302585$, or by counting the bits in $F_n$ and multiplying by $\log 2\approx 0.693147$. (The foregoing is not correct; one has to be more careful in approximating the logarithm; see below.)

Since $\alpha$ and $\beta$ are constants, they can be precomputed and used in the program at zero cost.

[ Addendum: I have not done a careful analysis of the precision with which the logarithm needs to be calculated, but experiments suggest that it is low, as I suggested earlier. For example, I tried the following method for fudging the logarithm:

1. Take $F_n$ and count the decimal digits.
2. Multiply this by $2.3026$.
3. Add the log of the two leftmost digits of $F_n$. (There are only 90 possible values, which can be precomputed and stored in a lookup table.)

This was sufficiently precise to yield correct answers for each $F_n$ with $n<1000$. ]

Based on the relationship with the Lucas numbers,

$$L_n^2 = 5 F_n^2 + 4 (-1)^n$$

And the fact that

$$\lim_{n \rightarrow \infty} \dfrac{L_n}{F_n} = \sqrt{5}$$

We see for $n \ge 3$,

$$\dfrac{5 F_n^2 - \operatorname{round}(\sqrt{5} F_n)^2}{4} = (-1)^n$$

So

$$\dfrac{5 F_n^2 - \operatorname{round}(\sqrt{5} F_n)^2}{4} = -1 \Rightarrow n\text{ is odd}$$

$$\dfrac{5 F_n^2 - \operatorname{round}(\sqrt{5} F_n)^2}{4} = 1 \Rightarrow n \text{ is even}$$

Which is equivalent to

$$\sqrt{5} F_n - \operatorname{round}(\sqrt{5} F_n) < 0 \Rightarrow n\text{ is odd}$$

$$\sqrt{5} F_n - \operatorname{round}(\sqrt{5} F_n) > 0 \Rightarrow n \text{ is even}$$

You can't, in general, since $F_1=F_2$ but $1\not\equiv2\pmod2.$ Otherwise, compute the index of the Fibonacci number and checks its parity (the negatives don't cause trouble because $F_{2n+1}=F_{-2n-2}$ both have odd indices).

Modular methods with a fixed modulus will never be entirely effective for the same reason: $F_1=F_2$ and so $F_{m+1}\equiv F_{m+2}\mod M$ where m is the Pisano period mod M. But you could use multiple moduli to increase the chance of at least one working. In the extreme case, if the LCM of the moduli is at least as large as the number itself, at least one modulus will work (by the CRT) assuming the Fibonacci number is greater than 1.