Given only $F_n$, that is the $n$th term of the Fibonacci sequence, how can you tell if $n \equiv 1 \mod 2$ or $n \equiv 0 \mod 2$?
I know you can use the Pisano period, however if $n \equiv 1$ or $n \equiv 2$ $\mod \pi(k)$, it can never be found, where $k$ is in $\pi(k)$ (The Pisano period).
Also there is the fact that if $\sqrt{5F_n^2+ 4}$ is an integer then $n
\equiv 0 \mod 2$, but is there a faster way?
Lastly, because $F_1 = F_2 = 1$, that would have to be an exception for whatever rule/formula that would apply.
Best Answer
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:
This was sufficiently precise to yield correct answers for each $F_n$ with $n<1000$. ]