Чётные числа Фибоначчи

Навеяно комментарием под постом Фибоначчи на собеседовании ^[1]. Пользователь pavellyzhin ^[2] упомянул следующую задачу на собеседовании (комментарий ^[3]):

Больше года назад откликнулся на вакансию «php-программист», прислали ТЗ и там было задание с Фибоначчи: выбрать все четные числа Фибоначчи в диапазоне от 1 до 10000. Решил с помощью цикла(for). Еще там нужно было SQL-запрос составить на выборку ближайших дней рождений пользователей, что-то сверстать, точно не помню и какую-то функцию написать. Все сделал, отправил. Прислали ответ: «по итогам тестового задания Вы не приняты». Что конкретно им не понравилось так и не написали. Вот сейчас сижу и думаю, наверное все-таки из-за Фибоначчи пролетел… :)

В данном посте я собираюсь показать как можно было решить эту задачу эффектно, а может даже и эффективно, но это не точно. Заодно продемонстрирую парочку из тысяч доказанных про числа Фибоначчи фактов.

Теоретизируем

Лучшее с чего можно начать — просмотреть глазами первые N чисел Фибоначчи и попытаться обнаружить какие-то закономерности связанные с чётными элементами эмпирическим путём.

$$display$$1,1,{bf 2},3,5,{bf 8},13,21,{bf 34},55,89,{bf 144},ldots$$display$$

В последовательности отмечены чётные числа, как можно заметить каждое 3-е число Фибоначчи — чётное и, наверное, все чётные числа стоят на позициях кратных 3. Это и будет наша догадка, теперь нам нужно её подтвердить и выработать алгоритм вычисления.

Для начала воспользуемся рекурентным соотношением, образующим последовательность Фибоначчи $inline$F_{n+2} = F_{n+1} + F_n$inline$, выписав через него элемент $inline$F_{n+3}$inline$:

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

Таким образом, если $inline$F_n$inline$ — чётное, то $inline$F_{n+3}$inline$ также чётное в силу предыдущей формулы. Учитывая, что $inline$F_3=2$inline$, то каждое третье число Фибоначчи действительно чётное, что подтверждает часть нашей догадки. Но не пропускаем ли мы ещё чётные числа? Т.е. существуют ли ещё чётные числа Фибоначчи чей номер не кратен 3?

Предположим, что существует число $inline$F_m$inline$ — чётное и $inline$0notequiv mmod 3$inline$, тогда $inline$m = 3k - 1$inline$ или $inline$m=3k + 1$inline$, где $inline$k$inline$ — какое-то натуральное.

Обратимся к матричному представлению чисел Фибоначчи из оригинального поста

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

Вычисляя определитель обеих частей, получим

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

Отсюда следует, что делители чисел $inline$F_{n+1}, F_n$inline$ и $inline$F_{n-1}, F_n$inline$ совпадают с делителями $inline$(-1)^n$inline$, т.е. соседние числа Фибоначчи взаимнопросты. Это же означает, что взаимнопросты и числа $inline$F_{3k}, F_{3k-1}$inline$ и $inline$F_{3k}, F_{3k+1}$inline$, т.е. $inline$F_{3k}$inline$ и $inline$F_m$inline$. Но по предположению $inline$F_m$inline$ — чётное, а $inline$F_{3k}$inline$ — чётное по доказанному ранее. Таким образом других чётных чисел, кроме $inline$F_{3k}$inline$, где $inline$kin mathbb{N}$inline$ в последовательности Фибоначчи не существует.

Замечательно, мы полностью подтвердили нашу догадку! В самом деле все чётные числа Фибоначчи имеют номера кратные 3. Существует как минимум ещё один способ, показать это — воспользоваться теоремой Люка

Теорема Люка. Целое число делит $inline$F_m$inline$, и $inline$F_n$inline$, тогда и только тогда, когда оно является делителем $inline$F_d$inline$, где $inline$d = gcd(m,n)$inline$, в частности

$$display$$ gcd(F_m, F_n)=F_{gcd(m,n)} $$display$$

Тут $inline$gcd$inline$ — наибольший общий делитель. Если положить $inline$m=3$inline$, то $inline$gcd(2, F_n)=F_{gcd(3,n)}$inline$. Если $inline$F_n$inline$ — чётное, то левая часть равна 2, тогда чтобы правая часть тоже равнялась 2 необходимо, чтобы $inline$n$inline$ делилось на 3, а это именно то, что мы и хотели доказать!

Алгоритм

А теперь осталось придумать алгоритм. Можно конечно поступить, как изначально сделал pavellyzhin ^[2], но вместо того чтобы проверять $inline$0equiv F_nmod 2$inline$, мы можем проверить $inline$0equiv nmod 3$inline$, вот это поворот! Правда это никак не влияет на число итераций алгоритма, ведь мы просто изменили фильтр последовательности. Лучше сразу генерировать подпоследовательность чисел Фибоначчи с нужным нам свойством (чётность), поэтому другой очевидный способ это воспользоваться формулой Бине

$$display$$ F_n=leftlfloorfrac{varphi^n}{sqrt{5}}rightrceil, qquad nin{3,6,ldots,3kldots} $$display$$

Тут имеются свои сложности с эффективностью вычислений, подробней об этом сказано в оригинальном посте. Поэтому предлагаю лучший, на мой взгляд, способ — итеративное вычисление $inline$F_{n+3}$inline$, это можно сделать, как мы ранее показали, по формуле $inline$F_{n+3} = 2F_{n+1} + F_n$inline$. Чтобы построить итеративный переход в алгоритме, нам понадобится вычислять $inline$F_{n+4}$inline$, тут всё так же просто

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

Кстати, вообще говоря несложно доказать, что

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

Тогда формально алгоритм записывается следующим образом (текущее чётное число Фибоначчи $inline$F_n$inline$, следующее за ним число Фибоначчи $inline$F_{n+1}$inline$, $inline$M$inline$ — верхняя граница для чисел, заданная в условии задачи):

1. $inline$F_nleftarrow F_3 = 2,quad F_{n+1}leftarrow F_4=3$inline$
2. Если $inline$F_n > M$inline$, то закончить, иначе добавить в результат $inline$F_n$inline$
3. $inline$(F_n, F_{n+1})leftarrow (2F_{n+1} + F_n, 3F_{n+1}+2F_n)$inline$, перейти на шаг 2.

Алгоритм достаточно тривиален — мы просто перепрыгиваем на каждое третье число Фибоначчи и выводим его (если оно не больше $inline$M$inline$). Сложность алгоритма всё так же линейна, но число повторений шага 2 в точности равняется числу чётных чисел Фибоначчи в диапазоне $inline$1ldots M$inline$, для сравнения простой алгоритм с фильтрацией требует в 3 раза больше итераций (на каждое найденное будет приходиться 2 отброшенных).

Алгоритм существует на бумаге, на чём там было собеседование, PHP? Чтож расчехляем напоследок PHP значит

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

Обобщение

Мы упомянули тут теорему Люка, которая гласит, что $inline$gcd(F_m, F_n)=F_{gcd(m,n)}$inline$. Как следствие из неё мы можем получить, что число Фибоначчи $inline$F_n$inline$ кратно числу $inline$F_m$inline$, тогда и только тогда, когда его номер $inline$n$inline$ кратен номеру $inline$m$inline$. Т.е. каждое 4-е число Фибоначчи делится на 3, каждое 5-е на 5, каждое 6-е на 8 и т.д.

Тогда несложным образом получаем алгоритм вычисления подпоследовательности Фибоначчи, в которой элементы кратны какому-то заданному числу $inline$F_m$inline$. Используя тот факт, что

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

Предыдущий алгоритм превращается в

1. $inline$F_nleftarrow F_m,quad F_{n+1}leftarrow F_{m+1}$inline$
2. Если $inline$F_n > M$inline$, то закончить, иначе добавить в результат $inline$F_n$inline$
3. $inline$(F_n, F_{n+1})leftarrow (F_mF_{n+1} + F_{m-1}F_n, F_{m+1}F_{n+1}+F_mF_n)$inline$, перейти на шаг 2.

Где $inline$F_{m-1},F_m,F_{m+1}$inline$ можно задать как константы.

Что-то вроде итога

Задачка конечно полностью синтетическая, количество итераций очень мало (для $inline$M=10000$inline$ ответ содержит всего 6 чисел, т.е. выполнено было 6 итераций, а первоначальному алгоритму «в лоб» потребовалось бы 18), но таким образом юзернейм, который открыл для себя тут в этом что-то новое сможет теперь показать чуть более глубокое математическое знание в числах Фибоначчи на собеседовании.

Автор: Дмитрий Кравцов

Источник ^[4]