PPnT's blog

Fibonacci Number Query
By PPnT, history, 7 years ago, In English

can anyone help me to find how many odd and even fibonacci number between n'th and m'th fibonacci number where the range of n and m is 10^18

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

odd + odd = even

odd + even = odd

even + odd = odd

F0 = 0, F1 = 1, F2 = 1, F3 = 2, ...

So every third number is even. You only need to count the number of numbers divisible by three in the interval.

More generally, If Fi is the smallest fibonacci number such that a | Fi, then a | Fj iff j = 0 (mod i). This holds since gcd(Fa, Fb) = F(gcd(a, b))

https://www.cut-the-knot.org/arithmetic/algebra/FibonacciGCD.shtml

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    i understand ur idea but can you help me by giving code of this please .

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Instead, it is equivalent to the sum of all values in the fibonacci sequence between indicies n and m, and the fibonacci numbers are taken modulo 2. We can also form them (summing up) modulo 2. This can be used to count the number of odd values (for even, just taken m - n + 1 - countodd).

Instead of counting odds in the range, we can also count the odds in ranges [1, m] and [1, n — 1] and subtract the answers.

Let's form the first values of the fibonacci sequence modulo 2:

0 1 1 0 1 1 0 1 1 0 .... Notice that there's a cycle of length 3, of the form 0 1 1. We can use this property:

The number of odds in the range [1, x] (where 1 and x are indicies in the fibonacci sequence) is equal to:

Edit: you can also count instead the number of even values (which should be easier), as said in the comment above me.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you share the question link!!

→ Reply