Even Fibonacci numbers

Inspired by the commentary under the Fibonacci post on the interview . The user pavellyzhin mentioned the following task at the interview ( comment ):

More than a year ago, the php-programmer responded to the vacancy, sent a request 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 am sitting and thinking, probably because of Fibonacci, flying all the same ... :)

In this post I am going to show how it was possible to solve this problem 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.

Theorize

The best thing to begin 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$$

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 originally 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. The proof by induction is obvious, but I cannot help but lead him

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

• Base induction . The first two numbers of fibonacci $$$1,1$- odd, third number $$$2$- even
• Hypothesis Suppose that up to some multiple of the number 3 Fibonacci number 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 two previous ones for him are odd, by construction its number is a multiple of 3, it is even, and the two preceding are odd.

This is how you can prove our guess without even resorting to mathematical calculations. You can formalize this idea, at the same time getting the formula to calculate every third Fibonacci number $$$F_ {n + 3}$of $$$F_n$and $$$F_ {n + 1}$. Using the recurrence ratio $$$F_ {n + 2} = F_ {n + 1} + F_ {n}$we will receive:

$$

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

So, if $$$F_n$- even, then $$$F_ {n + 3}$also even by virtue of this formula. Considering that $$$F_3 = 2$, then every third Fibonacci number is really even, which confirms 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 janatem for his simple idea, because from the above formula for $$$F_ {n + 3}$it also follows that if $$$F_n$- odd then $$$F_ {n + 3}$also odd, so we get the numbers with 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. Suppose there is a number $$$F_m$- 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 & 1 \\ 1 & 1 \ end {pmatrix} ^ n = \ begin {pmatrix} F_ {n-1} & F_n \\ F_n & 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 the numbers $$$F_ {n + 1}, F_n$and $$$F_ {n-1}, F_n$match divisors $$$(- 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 by assumption $$$F_m$- even, and $$$F_ {3k}$- even on proven earlier. Thus, other even numbers except $$$F_ {3k}$where $$$k \ in \ mathbb {N}$in the Fibonacci sequence does not exist. And also we have established an interesting fact that neighboring Fibonacci numbers are mutually simple.

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

Luke's theorem . 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$- the greatest common divisor. If we put $$$m = 3$then $$$\ gcd (2, F_n) = F _ {\ gcd (3, n)}$. If a $$$F_n$- even, then the left side is equal to 2, then the right side should also be 2, so that $$$n$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 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$, What 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, method - iterative calculation $$$F_ {n + 3}$, this can be done, as we have previously shown, by 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$the next 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 a $$$F_n> M$, then finish, otherwise add to the 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 drops).

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 <= $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 the user hunroll . 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 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 < 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 the Luke 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$multiple of number $$$F_m$if and only if its number $$$n$multiple of number $$$m$. Those. each 4th Fibonacci number is divided by 3, each 5th by 5, each 6th by 8, and so on.

Then, in a simple way, we obtain an algorithm for computing the Fibonacci subsequence, in which the 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 a $$$F_n> M$, then finish, otherwise add to the 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 set as constants.

Summary of the 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.

$$

$$F_ {n + 1} = F_n + F_ {n-1} \\ F_ {n + 2} = 3F_ {n} - F_ {n-2} \\ F_ {n + 3} = 4F_ {n} + F_ {n-3} \\ F_ {n + 4} = 7F_ {n} - F_ {n-4} \\ F_ {n + 5} = 11F_ {n} + F_ {n-5} \\ \ cdots \\ F_ {n + t} = (F_t + 2F_ {t-1}) F_n + (-1) ^ {t-1} F_ {nt}$$

Let us prove this by the method of mathematical induction, for t = 1 and t = 2, the execution is obvious. Let it be executed up to some t, then

$$

$$F_ {n + t + 1} = F_ {n + t} + F_ {n + t-1} = \\ (F_t + 2F_ {t-1}) F_n + (-1) ^ {t-1} F_ {nt} + \\ (F_ {t-1} + 2F_ {t-2}) F_n + (-1) ^ {t-2} F_ {n-t + 1} = \\ (F_t + F_ { t-1} + 2 (F_ {t-1} + F_ {t-2})) F_n + (-1) ^ {t-1} (F_ {nt} -F_ {n-t + 1}) = \\ (F_ {t + 1} + 2F_t) F_n + (-1) ^ {t-1} (F_ {nt} -F_ {nt} -F_ {nt-1}) = \\ (F_ {t + 1} + 2F_t) F_n + (-1) ^ tF_ {nt-1}$$

Something like a total

The problem is of course completely synthetic, the number of iterations is very small (for $$$M = $ 10,00$the answer contains only 6 numbers, i.e. 6 iterations were performed, and the original algorithm “head-on” would take 18), but in this way the username that discovered something new here could now show a little deeper mathematical knowledge in Fibonacci numbers at the interview.

Edit: Thanks to janatem and AllexIn users for simple proofs, I included them in "Teoretiziruem", and also hunroll for an algorithm using only already received even numbers in calculations and to the user ignorance for its generalization.