[From the sandbox] Even Fibonacci numbers

[From the sandbox] Even Fibonacci numbers


Inspired by the comment under the post Fibonacci at the interview . The user pavellyzhin mentioned the following problem at the interview ( comment ):
More than a year ago, the php-programmer responded to the vacancy, sent TK and there was a task from Fibonacci: select all even Fibonacci numbers in the range from 1 to 10,000 . Decided using a loop (for). It was also necessary to create a SQL query for a sample of the next days of users' births, to impose something, I do not remember exactly, and write some function. I did everything, sent it. They sent the answer: “according to the results of the test task, you are not accepted”. What exactly they did not like and did not write. Right now I’m sitting and thinking, probably because of Fibonacci’s flying, after all ...:)
In this post I’m going to show how this problem could be solved effectively, and maybe even effectively, but this is not accurate. At the same time I will demonstrate a couple of thousands of facts proved about the Fibonacci numbers.


Theoretically



The best thing to start with is to look through the eyes of the first N Fibonacci numbers and try to find a pattern in the arrangement of even numbers.

$ 1.1, {\ bf 2}, 3.5, {\ bf 8}, 13.21, {\ bf 34}, 55,  89, {\ bf 144}, \ ldots $ > < math>


Even numbers are marked in the sequence, as you can see every 3rd Fibonacci number is even, and probably all even numbers are in positions of multiples of 3. This will be our guess, now we need to confirm it and develop a calculation algorithm.

The best proof is simple, so thanks to AllexIn for a simple idea that I initially missed. Each subsequent Fibonacci number is the sum of the two previous ones, if the two previous numbers are odd, then the next one will be even, if the two previous numbers have one odd and the other even, then the next will be odd. In principle, this idea alone is already enough to “intuitively grope” the fact being proved. Proof by induction is obvious, but I can not help but bring it

We prove that “every third Fibonacci number is even, and the two preceding each such number are odd.”
  • Base induction . The first two fibonacci numbers $ 1.1 $ is odd, the third number  $ 2 $ - even
  • Hypothesis . Suppose that up to a certain multiple of the 3 Fibonacci numbers is satisfied that every third is even and the two preceding ones are odd.
  • Induction Step . The number following the last even of the hypothesis is odd, since it is obtained from the sum of the odd with the even, the next after this number is also odd, because it is obtained from the sum of an even with an odd, and the next after it is even, because the previous two for him were just odd, by construction its number is a multiple of 3, it is even, and the two preceding it are odd.


This is how you can prove our guess without even resorting to mathematical calculations. You can formalize this idea by getting the formula for calculating every third Fibonacci number $ F_ {n + 3} $ from  $ F_n $ and  $ F_ {n + 1} $ . Using the recurrent $ F_ {n + 2  } = F_ {n + 1} + F_ {n} $ we get:

$ F_ {n + 3} = F_ {n + 2} + F_ {n + 1} = 2 F_ {n + 1} + F_n $


Thus, if $ F_n $ is even, then $ F_ {n + 3} $ is also even by virtue of this formula. Considering that $ F_3 = 2 $ , then every third Fibonacci number is really even, which is confirmed by a part of our guess. Here it is necessary to make sure that we do not miss other even numbers, i.e. that they all have multiples of 3. Thanks to the user janatem for his simple idea, because of the above formula for $ F_ {n + 3} $ also implies that if  $ F_n $ is odd, then  $ F_ {n + 3} $ is also odd, so that the numbers with the numbers  $ 3k-2,  3k-1, k \ in \ mathbb {N} $ - odd (by induction, start with  $ F_1 = F_2 = 1 $ - odd), and $ 3k, k \ in \ mathbb {N} $ - even that covers all Fibonacci numbers, which means we really cover all even numbers.

There is still a way to show that there are no other even numbers. Assume that there is a number $ F_m $ is even and  $ 0 \ not \ equiv m \ mod 3 $ , then  $ m = 3k - 1 $ or  $ m = 3k + 1 $ where  $ k $ - some kind of natural.

Referring to the matrix representation of the Fibonacci numbers from the original post

$ \ begin {pmatrix} 0 & amp; 1 \\ 1 & amp; 1 \ end {pmatrix} ^ n = \ begin {pmatrix} F_ {n-1  } & amp; F_n \\ F_n & amp; F_ {n + 1} \ end {pmatrix} $


Calculating the determinant of both parts, we get

$ (-1) ^ n = F_ {n + 1} F_ {n-1} -F_n ^ 2 $


It follows that the divisors of numbers $ F_ {n + 1}, F_n $ and  $ F_ {n-1}, F_n $ coincide with the dividers  $ (- 1) ^ n $ , i.e. neighboring Fibonacci numbers are mutually simple. This also means that mutually simple numbers $ F_ {3k}, F_ {3k-1} $ and  $ F_ {3k}, F_ {3k + 1} $ , i.e. $ F_ {3k} $ and $ F_m $ . But under the assumption $ F_m $ is even and $ F_ {3k} $ - even according to the previously proved. Thus, other even numbers except $ F_ {3k} $ where  $ k \ in \ mathbb {N} $ in the Fibonacci sequence does not exist. We also found an interesting fact that neighboring Fibonacci numbers are mutually simple.

Finally, let us show at least one more way to prove our guess - use Luke's theorem.

Luke's Theorem . The integer divides $ F_m $ , and $ F_n $ , if and only if it is a divisor  $ F_d $ , where  $ d = \ gcd (m, n) $ , in particular

$ \ gcd (F_m, F_n) = F _ {\ gcd (m, n)} $


Here $ \ gcd $ is the greatest common factor. If you put $ m = 3 $ , then $ \ gcd (2, F_n) = F _ {\ gcd (3, n)} $ . If  $ F_n $ is even, the left side is 2, then the right side also equals 2 it is necessary that  $ n $ was divided by 3 and at the same time the opposite is true. So we get exactly that we wanted to prove.

So, every third Fibonacci number is even, and every even number has a multiple of three. We have thoroughly proved it and no one dares to doubt it now.

Algorithm


And now it remains to come up with an algorithm. You can certainly do as originally pavellyzhin , but instead of checking $ 0 \ equiv F_n \ mod 2 $ we can check $ 0 \ equiv n \ mod 3 $ , this is a twist! True, this does not affect the number of iterations of the algorithm, because we just changed the filter sequence. It is better to immediately generate a subsequence of Fibonacci numbers with the property we need (parity), so another obvious way is to use the Binet formula

$ F_n = \ left \ lfloor \ frac {\ varphi ^ n} {\ sqrt {5}} \ right \ rceil, \ qquad n \ in  \ {3.6, \ ldots, 3k \ ldots \} $


There are some difficulties with the efficiency of calculations, more about this in the original post. Therefore, I propose the best, in my opinion, way - iterative calculation $ F_ {n + 3} $ , this can be done, as we showed earlier, using the formula  $ F_ {n + 3} = 2F_ {n  +1} + F_n $ . To build an iterative transition in the algorithm, we need to calculate $ F_ {n + 4} $ , everything is just as simple

$ F_ {n + 4} = F_ {n + 3} + F_ {n + 2} = 2F_ {n + 1} + F_n + F_  {n + 1} + F_n = 3F_ {n + 1} + 2F_n $


By the way, generally speaking it is easy to prove that

$ F_ {n + m} = F_mF_ {n + 1} + F_ {m-1} F_n $


Then the algorithm is formally written as follows (the current even Fibonacci number $ F_n $ , followed by a Fibonacci number  $ F_ {n + 1} $ ,  $ M $ - the upper limit for numbers given in the problem statement):

  1. $ F_n \ leftarrow F_3 = 2, \ quad F_ {n + 1} \ leftarrow F_4 = 3 $
  2. If $ F_n & gt; M $ then finish, otherwise add to result  $ F_n $
  3. $ (F_n, F_ {n + 1}) \ leftarrow (2F_ {n + 1} + F_n, 3F_ {n + 1} + 2F_n) $ , go to step 2.

The algorithm is rather trivial - we simply jump over every third Fibonacci number and output it (if it is not more than $ M $ ). The complexity of the algorithm is still linear, but the number of repetitions of step 2 is exactly equal to the number of even Fibonacci numbers in the range $ 1 \ ldots M $ , for comparison, a simple algorithm with filtering requires 3 times more iterations (for each found, there will be 2 dropped).

The algorithm exists on paper, on what was there an interview, PHP? Well, finally, uncover PHP means

  function evenfibs ($ ubound) {
  $ result = [];
  [$ evenf, $ nextf] = [2, 3];
  while ($ evenf & lt; = $ ubound) {
  array_push ($ result, $ evenf);
  [$ nextf, $ evenf] = [
  3 * $ nextf + 2 * $ evenf,
  2 * $ nextf + $ evenf];
  }
  return $ result;
 }
  


Note : This method can always be improved, as, for example, showed by the user hunroll . The idea is that for calculations we do not need anything extra, except for the partially obtained result, i.e. we can calculate even numbers using only previous even Fibonacci numbers.

$ F_ {n + 3} = 2F_ {n + 1} + F_ {n} = 3F_n + 2F_ {n-1} = 3F_n + F_  {n-1} + F_ {n-1} = \\ 3F_n + (F_ {n-1} + F_ {n-2}) + F_ {n-3} = 4F_n + F_ {n-3} $



  function evenfibs ($ ubound) {
  if ($ ubound & lt; 2) return [];
  $ evens = [2];
  $ next = 8;
  for ($ i = 1; $ next & lt; = $ ubound; $ i ++) {
  $ evens [$ i] = $ next;
  $ next = $ evens [$ i] * 4 + $ evens [$ i-1];
  }
  return $ evens;
 }
  


Generalization


Here we mentioned Luke's theorem, which states that $ \ gcd (F_m, F_n) = F _ {\ gcd (m, n)} $ . As a consequence of it, we can get that Fibonacci number $ F_n $ is a multiple of the number  $ F_m $ , then and only if its number is  $ n $ is a multiple of  $ m $ . Those. every 4th Fibonacci number is divided by 3, every 5th by 5, every 6th by 8, etc.

Then, in a simple way, we obtain an algorithm for computing the Fibonacci subsequence, in which elements are multiples of some given number $ F_m $ .Using the fact that

$ F_ {n + m} = F_mF_ {n + 1} + F_ {m-1} F_n \\ F_ {n + m + 1}  = F_ {m + 1} F_ {n + 1} + F_mF_n $


The previous algorithm turns into

  1. $ F_n \ leftarrow F_m, \ quad F_ {n + 1} \ leftarrow F_ {m + 1} $
  2. If $ F_n & gt; M $ then finish, otherwise add to result  $ F_n $
  3. $ (F_n, F_ {n + 1}) \ leftarrow (F_mF_ {n + 1} + F_ {m-1} F_n, F_ {m + 1} F_ {n +  1} + F_mF_n) $ , go to step 2.

Where $ F_ {m-1}, F_m, F_ {m + 1} $ can be specified as constants.

Something like a total


The problem is of course completely synthetic, the number of iterations is very small (for $ M = $ 10000 the answer contains only 6 numbers, i.e. 6 iterations were performed and the original algorithm would be required 18), but in this way the username that was opened for here something new can show a little deeper mathematical knowledge in Fibonacci numbers at the interview.

Edit: Thanks to users janatem and AllexIn for simple proofs, I included them in "Teoretiziruem", as well as hunroll for the algorithm that uses in the calculations only the even numbers already received.

Source text: [From the sandbox] Even Fibonacci numbers