Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

5 Answers 5

up vote 16 down vote accepted

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$. ]

share|improve this answer
4  
For large $x$, you probably need high-precision values of $\sqrt 5$ and $\phi$ and their logs. Computing $\sqrt{5F_n^2+ 4}$ is probably easier. –  lhf Jun 26 at 19:23
2  
I don't think you need high-precision values, because you only need to calculate the answer to the nearest integer. This would be troublesome if the computed value were something like $n+0.4999999999999999937$, but it never is; it's extremely close to an integer, so much so that you need only calculate the integer value plus one more bit. Values of $\log\sqrt5 $ and $\log\varphi$ can of course be precomputed. $\log F_n$ can be calculated to the required precision by looking at the length of $F_n$ in bits and then multiplying by $\log 2$. –  MJD Jun 26 at 19:25
1  
I don't know what "precision rate" means. It will only take you five minutes to write the code, so why don't you try some experiments? –  MJD Jun 26 at 19:28
2  
@DaneBouchie The values are never close to $\frac12$ except when $n<2$. This is because the neglected value of $\hat\varphi^n$ quickly becomes insignificant. So even for as small an $F_n$ as 233, the value you need to round differs from 13 by less than $2^{-15}$. For $1346269$ the value before rounding is $31.0000000000002$. –  MJD Jun 26 at 19:33
2  
@johannesvalks Right, thanks! happily, for this application it doesn't matter. –  MJD Jun 26 at 19:44

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}$$

share|improve this answer

You can do some things with moduli, but I haven't found a complete solution. If $F_n \equiv 2 \pmod {12}$, $n$ is odd. Similarly for $10$, while if it is equivalvent to $0, 3, 4, 7, 8, 9$ or $11, n$ is even. Unfortunately, $1$ and $5$ go both ways and account for $9$ of the cycle of $24$. You might do better with some others.

share|improve this answer
1  
I kind of talked about this with Pisano periods, the issue is if $n \equiv 1\mod \pi(k)$, they will be $F_n \equiv 1 \mod k$, so you cannot tell the difference without performing more and more mod operations, which takes up more memory as well. –  Dane Bouchie Jun 26 at 19:43
    
@DaneBouchie: true for $1 \pmod k$, but $2 \pmod {12}$ does work. Unfortunately, this still only works for $\frac 58$ of numbers. –  Ross Millikan Jun 26 at 19:50
    
Corrected my stating, I actually meant 1+ the pisano period length, and 2 + the pisano period length, because they are equal, and always 1, it is an issue, thus the 5/8 you are getting. –  Dane Bouchie Jun 26 at 19:58
1  
@DaneBouchie: In this case that is not the only problem or I could get $\frac {11}{12}$. There are two more $1$'s plus five $5$'s. But it is a pretty simple computation. –  Ross Millikan Jun 26 at 20:00
1  
I suppose they are a fast pre-compute before a different method for those "debatable" exceptions. –  Dane Bouchie Jun 26 at 20:05

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.

share|improve this answer
    
I think the part "compute the index of the Fibonacci number" is what the question is about. –  ShreevatsaR Jun 27 at 7:52
    
@ShreevatsaR: That's standard, just take the base-$\varphi$ logarithm of the number times $\sqrt5$ and round. –  Charles Jun 27 at 13:31
    
Yes, as I see it, the question is how efficient doing that is, and whether that's the most efficient method possible. See MJD's answer (which IMO is not complete yet). (BTW, the OP does mention the $F_1 = F_2$ exception, and is presumably fine with a rule that applies only for $n > 2$.) –  ShreevatsaR Jun 27 at 16:18
    
@ShreevatsaR: OK, I added a comment to that effect. –  Charles Jun 27 at 17:17

Assuming that $F_n\geq 2$, you can check the parity of $n$ depending on the sign of the difference between $\frac{1+\sqrt{5}}{2}F_n$ and the closest integer. If negative, then $n$ is even, if positive, then $n$ is odd.

share|improve this answer
1  
The problem with this is that you have to multiply by an approximation to $\phi$ and then determine whether a number very very close to an integer is bigger or smaller. –  jwg Jun 27 at 15:09

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.