Fibonacci even numbers

Inspired by a comment under a Fibonacci post for an interview . User pavellyzhin mentioned the following interview task ( comment ):

More than a year ago, “php-programmer” responded to the vacancy, they sent TK and there was a task from Fibonacci: select all even Fibonacci numbers in the range from 1 to 10000 . Decided using a (for) loop. There, it was also necessary to make an SQL query to select the nearest birthdays of users, to make up something, I just don’t remember and write some kind of function. I did everything, sent it. They sent an answer: "according to the results of the test task you are not accepted." What exactly they did not like was not written. Now I'm sitting and thinking, probably after all because of Fibonacci I flew ... :)

In this post I am going to show how it was possible to solve this problem effectively, and maybe even efficiently, but this is not accurate. At the same time I will demonstrate a couple of thousands of facts proved about Fibonacci numbers.

Theorizing

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

$$

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 work out a calculation algorithm.

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

We prove that "every third Fibonacci number is even, and the two preceding each such number are odd."

• Base induction . First two fibonacci numbers$$ - odd, third number $$ - even
• Hypothesis . Suppose that up to some Fibonacci number multiple of 3 it is true that every third is even, and the two preceding it are odd.
• Induction step . The number following the last even one from the hypothesis is odd, because it is obtained from the sum of the odd with the even, following that number already is also odd, because it is obtained from the sum of the even with the odd, and the next after it is even, because the two previous ones just received for him are odd, by construction his number is a multiple of 3, it is even, and the two previous ones are odd.

This is how we can prove our guess without even resorting to mathematical calculations. You can formalize this idea, at the same time obtaining a formula for calculating every third Fibonacci number$$ of $$ and $$. Using the recursive relation$$ we get:

$$

So if $$ - even then $$also even by virtue of this formula. Given that$$, then every third Fibonacci number is really even, which confirms part of our guess. Here you need to make sure that we do not miss other even numbers, i.e. that they all have multiples of 3. Thanks to janatem for his simple idea, because from the above formula for$$ it also follows that if $$ - odd then $$ also odd, so we get that numbers with numbers $$ - odd (by induction, start with $$ - odd), and $$- even, which covers all the Fibonacci numbers, which means that we really cover all the even numbers.

There is another way, as it would be possible to show that there are no other even numbers. Suppose there exists a number$$ - even and $$then $$ or $$where $$- some kind of natural.

Let us turn to the matrix representation of Fibonacci numbers from the original post

$$

Calculating the determinant of both parts, we obtain

$$

It follows that the divisors of numbers $$ and $$ match dividers $$, i.e. neighboring Fibonacci numbers are mutually simple. This also means that mutual simplicity and numbers$$ and $$, i.e. $$ and $$. But by assumption$$ - even, and $$- even as previously proven. So other even numbers than$$where $$in the Fibonacci sequence does not exist. And also we established an interesting fact that the neighboring Fibonacci numbers are mutual simple.

Finally, we show at least one more way to prove our guess: use Luke's theorem.

Luke's theorem . Integer divides$$, and $$, if and only if it is a divisor $$where $$, in particular

$$

Here $$Is the largest common factor. If put$$then $$. If$$ - even, then the left side is 2, so that the right side also equals 2, it is necessary that $$divided by 3 and at the same time the opposite is true. Thus, we get exactly what we wanted to prove.

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

Algorithm

And now it remains to come up with an algorithm. You can of course do what pavellyzhin originally did , but instead of checking$$we can check $$, What a twist! True, this does not affect the number of iterations of the algorithm, because we just changed the sequence filter. It’s 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

$$

There are difficulties with the efficiency of calculations, more about this in the original post. Therefore, I propose the best, in my opinion, method - iterative calculation$$, this can be done, as we previously showed, by the formula $$. To construct an iterative transition in the algorithm, we need to calculate$$, everything is just as simple

$$

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

$$

Then formally the algorithm is written as follows (the current even Fibonacci number $$followed by the Fibonacci number $$, $$ Is the upper bound for numbers given in the condition of the problem):

1. $$
2. If $$, then finish, otherwise add to the result $$
3. $$go to step 2.

The algorithm is quite trivial - we simply jump onto every third Fibonacci number and print it (if it is not more $$) 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$$, for comparison, a simple algorithm with filtering requires 3 times more iterations (for each found, there will be 2 discarded).

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

function evenfibs($ubound) {
  $result = [];
  [$evenf, $nextf] = [2, 3];
  while($evenf <= $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, the user hunroll showed . The idea is that for calculations we do not need anything superfluous, except for the partially obtained result, i.e. we can calculate even numbers using only the previous even Fibonacci numbers.

$$

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

Generalization

We mentioned here Luke's theorem, which states that $$. As a consequence of it, we can get that the Fibonacci number$$ multiple of $$, if and only if its number $$ multiple to number $$. 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 calculating the Fibonacci subsequence, in which the elements are multiples of some given number$$. Using the fact that

$$

The previous algorithm turns into

1. $$
2. If $$, then finish, otherwise add to the result $$
3. $$go to step 2.

Where $$can be set as constants.

Summary of notes . As the user ignorance rightly noted , in the generalized case, it is also possible to construct an algorithm that uses only numbers from a partial result.

$$

Let us prove this by the method of mathematical induction, for t = 1 and t = 2, the fulfillment is obvious. Suppose that it holds up to some t; then

$$

Something like a total

The task of course is completely synthetic, the number of iterations is very small (for $$the answer contains only 6 numbers, i.e. 6 iterations would have been completed, and the original “head-on” algorithm would have required 18), but in this way a user who discovered something new here can now show a little deeper mathematical knowledge in Fibonacci numbers at the interview.

Edit: Thanks to janatem and AllexIn users for the simple proofs, I included them in “Theoremizing”, as well as hunroll for the algorithm using only the even numbers already obtained in the calculations and to the user ignorance for generalizing it.