idkravitz 5 мая 2019 в 15:54

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

5 мин

25K

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

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

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

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

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

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

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

Лучшее доказательство — простое, поэтому спасибо пользователю AllexIn за простую идею, которую я первоначально упустил. Каждое последующее число Фибоначчи представляет собой сумму двух предыдущих, если два предыдущих числа — нечётные, то следующее будет чётным, если в двух предыдущих числах одно нечётное, а другое чётное, то следующее будет нечётным. В принципе одной этой идеи уже достаточно, чтобы «интуитивно нащупать» доказываемый факт. Доказательство по индукции очевидное, но не могу удержаться, чтобы не привести его

Мы доказываем, что «каждое третье число Фибоначчи — чётное, а два предшествующих каждому такому числу — нечётные».

База индукции. Первые два числа Фиббоначи $inline$ — нечётные, третье число $inline$ — чётное
Гипотеза. Пусть вплоть до некоторого кратного по номеру 3 числа Фибоначчи выполнено, что каждое третье — чётное, а два предшествующих ему — нечётные.
Шаг индукции. Следующее за последним чётным из гипотезы числом является нечётным, т.к. оно получается из суммы нечётного с чётным, следующее за уже этим числом также нечётное, т.к. оно получается из суммы чётного с нечётным, а уже следующее за ним — чётное, т.к. только что полученные два предыдущих для него — нечётные, по построению его номер кратен 3, оно чётное, а два предшествующих ему — нечётные.

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

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

Таким образом, если $inline$ — чётное, то $F_{n+3}$ также чётное в силу этой формулы. Учитывая, что $inline$ , то каждое третье число Фибоначчи действительно чётное, что подтверждает часть нашей догадки. Тут необходимо убедиться, что мы не пропускаем других чётных чисел, т.е. что они все имеют номера кратные 3. Спасибо пользователю janatem за его простую идею, ведь из приведенной формулы для $F_{n+3}$ также следует, что если $inline$ — нечётное, то $F_{n+3}$ также нечётное, таким образом получаем, что числа с номерами $3k-2,3k-1, k\in\mathbb{N}$ — нечётные (по индукции, начинаем с $inline$ — нечётных), а $3k,k\in\mathbb{N}$ — чётные, что покрывает все числа Фибоначчи, а значит мы действительно покрываем всё чётные числа.

Есть ещё способ, как можно было бы показать, что других чётных чисел нет. Предположим, что существует число $inline$ — чётное и $0\not\equiv m\mod 3$ , тогда $inline$ или $inline$ , где $inline$ — какое-то натуральное.

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

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

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

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

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

Напоследок покажем как минимум ещё один способ доказать нашу догадку — воспользоваться теоремой Люка.

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

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

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

Итак, каждое третье число Фибоначчи — чётное, а каждое чётное имеет номер кратный трём. Мы тщательно доказали это и никто не смеет в этом теперь усомниться.

Алгоритм

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

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

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

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

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

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

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

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

Алгоритм достаточно тривиален — мы просто перепрыгиваем на каждое третье число Фибоначчи и выводим его (если оно не больше $inline$ ). Сложность алгоритма всё так же линейна, но число повторений шага 2 в точности равняется числу чётных чисел Фибоначчи в диапазоне $1\ldots M$ , для сравнения простой алгоритм с фильтрацией требует в 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;
}

Примечание: Этот способ всегда можно улучшить, как, например, показал пользователь hunroll. Идея в том, что для вычислений нам не нужно ничего лишнего, кроме уже частично полученного результата, т.е. мы можем вычислять чётные числа используя только предыдущие чётные числа Фибоначчи.

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

Обобщение

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

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

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

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

$F_n\leftarrow F_m,\quad F_{n+1}\leftarrow F_{m+1}$
Если $inline$ , то закончить, иначе добавить в результат $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)$ , перейти на шаг 2.

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

Обобщение примечания. Как справедливо заметил пользователь ignorance, в обобщенном случае также можно построить алгоритм, который использует только числа из частичного результата.

$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_{n-t}$

Докажем, это методом математической индукции, при t = 1 и t = 2 выполнение очевидно. Пусть выполненно вплоть до некоторого t, тогда

$F_{n+t+1}=F_{n+t} + F_{n+t-1}=\\ (F_t + 2F_{t-1})F_n + (-1)^{t-1}F_{n-t} + \\ (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_{n-t}-F_{n-t+1})=\\ (F_{t+1}+2F_t)F_n + (-1)^{t-1}(F_{n-t}-F_{n-t}-F_{n-t-1})=\\ (F_{t+1}+2F_t)F_n + (-1)^tF_{n-t-1}$

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

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

Edit: Спасибо пользователям janatem и AllexIn за простые доказательства, я включил их в «Теоретизируем», а также hunroll за алгоритм использующий в вычислениях только уже полученные чётные числа и пользователю ignorance за его обобщение.

Теги:

Хабы:

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

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

Алгоритм

Обобщение

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

Публикации

Истории

Работа

Ближайшие события