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

Навеяно комментарием под постом Фибоначчи на собеседовании. Пользователь 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 за простую идею, которую я первоначально упустил. Каждое последующее число Фибоначчи представляет собой сумму двух предыдущих, если два предыдущих числа — нечётные, то следующее будет чётным, если в двух предыдущих числах одно нечётное, а другое чётное, то следующее будет нечётным. В принципе одной этой идеи уже достаточно, чтобы «интуитивно нащупать» доказываемый факт. Доказательство по индукции очевидное, но не могу удержаться, чтобы не привести его

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


Вот так можно доказать нашу догадку даже не прибегая к математическим выкладкам. Можно формализовать эту идею, заодно получив формулу для вычисления каждого третьего числа Фибоначчи $F_{n+3}$ из $F_n$ и $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 $


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

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

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

$ \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$ совпадают с делителями $(-1)^n$, т.е. соседние числа Фибоначчи взаимнопросты. Это же означает, что взаимнопросты и числа $F_{3k}, F_{3k-1}$ и $F_{3k}, F_{3k+1}$, т.е. $F_{3k}$ и $F_m$. Но по предположению $F_m$ — чётное, а $F_{3k}$ — чётное по доказанному ранее. Таким образом других чётных чисел, кроме $F_{3k}$, где $k\in \mathbb{N}$ в последовательности Фибоначчи не существует. А также мы установили интересный факт, что соседние числа Фибоначчи взаимнопросты.

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

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

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


Тут $\gcd$ — наибольший общий делитель. Если положить $m=3$, то $\gcd(2, F_n)=F_{\gcd(3,n)}$. Если $F_n$ — чётное, то левая часть равна 2, тогда чтобы правая часть тоже равнялась 2 необходимо, чтобы $n$ делилось на 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 $


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

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

Алгоритм достаточно тривиален — мы просто перепрыгиваем на каждое третье число Фибоначчи и выводим его (если оно не больше $M$). Сложность алгоритма всё так же линейна, но число повторений шага 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)}$. Как следствие из неё мы можем получить, что число Фибоначчи $F_n$ кратно числу $F_m$, тогда и только тогда, когда его номер $n$ кратен номеру $m$. Т.е. каждое 4-е число Фибоначчи делится на 3, каждое 5-е на 5, каждое 6-е на 8 и т.д.

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

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


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

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



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


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

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

Комментарии 39

    +13
    наверное, все чётные числа стоят на позициях кратных 3

    Эмпирически? Догадка?
    ЛОЛ. Нечетные числа всегда в сумме своей дают четное. А нечетное с четным — нечетное.
    Или я не понял и эта статья — стёб на тему «доказываем простое сложно»?
      +1
      Нет — это я балбес) спасибо, добавил в статью
        0
        Это ж очевидно. На этом доказательную часть можно было бы и закончить :)
        +5
        Even[0]=2;
        Even[1]=8;
        for(int i=2;i<N; i++) {
           Even[i]=Even[i-1]*4 + Even[i-2];
        }

        Так тоже можно
          0
          Спасибо, добавил в конец секции «Алгоритм»
            +1
            Более того, это обобщается. Любую t-подпоследовательность (составленную из чисел, стоящих на местах, кратных t) Фибоначчи можно выразить через ее саму. Смотрите
            t = 1: F(n) = F(n-1) + F(n-2) — сама последовательность Фибоначчи
            t = 2: F(2*n) = 3*F(2*(n-1)) — F(2*(n-2))
            t = 3: F(3*n) = 4*F(3*(n-1)) + F(3*(n-2))
            t = 4: F(4*n) = 7*F(4*(n-1)) — F(4*(n-2))
            t = 5: F(5*n) = 11*F(5*(n-1)) + F(5*(n-2))

            Обобщая, имеем
            F(t*n) = a(t)*F(t*(n-1)) + (-1)^(t+1)*F(t*(n-2))

            Нетрудно видеть, что последовательность a(t) также является последовательностью a-la Фибоначчи, с базой 1, 3: 1,3,4,7,11,18…
            Для t>=3 справедливо a(t) = 2*F(t) + F(t-3) (полагая F(0) = 0).

            Доказать, думаю, по индукции вполне возможно, просто вывод долгий получится.
              0
              a(t) лучше переписать в виде a(t)=F(t)+2F(t-1), тогда оно будет определелено для всех t>=1

              Идея интересная, попробую придумать доказательство покороче)
                +1
                Да, действительно.
                Я попробовал в лоб вывести через равенство
                F(n+t) = F(t)*F(n+1) + F(t-1)*F(n)
                Но приехал к остаточному члену
                F(t-2)*F(n) — F(t)*F(n-2)
                Возможно, уже есть известное равенство для таких выражений?
                  0
                  Я доказал индукцией, вставил в статью в конец секции «Обобщение», спасибо)
          +8

          Остался вопрос, на сколько вообще актуально знание математики для программиста PHP? Почему-то мне кажется, что такое знание математики требуется в единичных случаях. Больше необходимы умения связать несвязуемое, там 1С прицепить к сайту, плагин для магазина какой добавить...

            0
            У вас слишком ограниченное видение работы программистом, на php так же пишутся большие приложения, а не только связывают не связуемое и не впихуемое
              +3

              Вполне допускаю это, но смотрю на большинство сайтов, которыми сам пользуюсь, и вот не понимаю я, где там может жить даже такая довольно примитивная математика из статьи.
              Соответственно, и когда требуется программист для впихивания невпихуемого, а на собеседовании от него требуют каких-то извращений с высшей математикой и квантовой физикой, то мне это начинает напоминать требование высшего образования и докторской степени от уборщицы.

              +3
              Из всего пласта математики, преподанного в универе, в веб-разработке пригодилась только пару раз дискретная математика (графы и конечные автоматы) и немного тервер. Остальная огромная часть математики полезна, но как общее развитие мышления.
                0
                Бэкэнд в онлайн-игрушках (браузерки и флеш — точно) нередко пишут на PHP, если там прокрадываются элементы геймдизайна, то знание математики будет полезным.
                  0
                  По-хорошему, геймдизайнер в таких случаях должен предоставить формулы или алгоритм. От разработчика знание подобных вещей нужно, скорее, для увеличения производительности.
                  0
                  Вы используете математику каждый раз, когда задумываетесь о том, правильно ли работает программа. То есть когда пишите её, когда ищете баги, когда читаете чужой код. Потому что во всех этих случаях вам приходится рассуждать. Мысленно доказывать леммы и теоремы об этом коде, искать противоречия, находить контрпримеры. В общем, как мольеровский Мещанин — вы говорите прозой, но не догадываетесь об этом :)))
                    0
                    Является ли это той математикой, о которой идёт речь в статье, или это всё же ближе к логике и алгоритмике?
                    Так-то уборщица тоже использует химию, при мытье полов и физику, когда отдирает прилипшую жвачку, а математику при подсчёте своей зарплаты.
                    И да, я не хочу ни сколько принизить профессию программиста, да и уборщицы тоже. Мне просто кажется, что зачастую подобные требования выдвинутые работодателями не совсем адекватны.
                      0
                      Для решения этой задачи не требуется ничего, кроме способности совершать логические умозаключения. Автор статьи пошёл в ней гораздо дальше того, что требовалось в задаче. Сомневаюсь, что авторы задачи требовали от него чего-то большего, чем подсчёта N-го числа и проверки его на чётность. Не rocket science.
                  +8

                  Boomburum, не работает отображение формул на мобилке, fix pls :(

                    0
                    А можете больше подробностей в личку прислать? На каком девайсе/ос/браузере не работает.
                    У меня в ios/chrome формулы отображаются.
                      +1
                      Уже все заработало, не знаю, с чем связано)

                      На всякий случай: Xiaomi Redmi Note 4x, Chrome 73.0.3683.90, включая отображение версии для ПК.
                    +2
                    [sarcasm]
                    >Решил с помощью цикла(for)
                    >while

                    Мы вам перезвоним.
                    [/sarcasm]
                      +7
                      … А потом оказалось, что потенциальный работодатель чётными числами называет числа, стоящие на чётных местах (2-е, 4-е, 6-е, ...)?
                        0
                        Значит можно сказать — потенциальный работодатель не умеет давать чёткие ТЗ
                          0
                          Значит можно сказать — потенциальный работодатель не умеет давать чёткие ТЗ

                          … Добро пожаловать в реальный мир :) Не знаю, на счет работодателей, но подавляющее большинство Заказчиков не умеет давать четкие ТЗ и предпочитают играться с формой квадрата.
                        +3
                        существуют ли ещё чётные числа Фибоначчи чей номер не кратен 3?

                        После чего идет несколько абзацев выкладок, чтобы это доказать. При том, что выше уже выписано равенство из которого это тривиальным образом следует:
                        F_{n+3} = 2F_{n+1} + F_n
                        Если F_n — нечетное, то F_{n+3} — тоже нечетное. Остается лишь проверить четность двух первых чисел ряда.
                          0
                          Упустил, спасибо, добавил в статью
                          –9
                          Само словосочетание «программист PHP» оксюморон.
                            +1
                            Кстати, есть ещё одна прикольная задача про сумму первых n четных чисел Фибоначчи, которая решается за О(1). Сумма чисел Фибоначчи от 1 до 3n равна числу Ф. с номером 3n + 2, с другой стороны это удвоенная сумма первых n четных чисел Ф. т. к. каждое чётное равно сумме двух предыдущих, а они как раз идут группами по три. То есть ответ что-то вроде F(3n+2) / 2, который считается напрямую по формуле Бине.
                              –1
                              Мнится мне, что работодатель, говоря про Фибоначчи, имел в виду рекурсию. А в рекурсию могут не только лишь все…
                                0
                                Мнится мне, что программисты должны работать по ТЗ, а не догадками, кто там что имел в виду.
                                  0

                                  Вот если примут на работу, дадут ТЗ. А это был тест на наличие компетенций. И человек его не прошел. Потому что не все задачи решаются в лоб. Через цикл for.

                                    0
                                    А сколько начнёт кушать памяти «компетентное» рекурсивное решение не в лоб через пару тысяч итераций?
                                –1
                                Вот сейчас сижу и думаю, наверное все-таки из-за Фибоначчи пролетел

                                Я так и не понял, почему. Если задача действительно стояла так, как описано в письме (выбрать все четные числа Фибоначчи в диапазоне от 1 до 10000), то решение пишется за две минуты:


                                def fib():
                                    a, b = 1, 1
                                    yield a
                                    while True:
                                        yield b
                                        a, b = b, a + b
                                
                                def even_fib(n=10000):
                                    for i in fib():
                                        if i > n:
                                            return
                                        if i % 2 == 0:
                                            yield i

                                И именно такое решени, написанное за две минуты, является верным и самым подходящим, потому что корректно решает задачу минимальными ресурсами. И даже выполняется за смешное время:


                                In [3]: %time list(even_fib())
                                Wall time: 15.7 µs
                                Out[3]: [2, 8, 34, 144, 610, 2584]

                                Даже для больши́х значений:


                                In [5]: %time list(even_fib(10**30))
                                Wall time: 54.8 µs
                                Out[5]: [2, 8, 34, 144, 610, 2584, 10946, 46368, 196418, 832040, 3524578, 14930352, 63245986, 267914296, 1134903170, 4807526976, 20365011074, 86267571272, 365435296162, 1548008755920, 6557470319842, 27777890035288, 117669030460994, 498454011879264, 2111485077978050, 8944394323791464, 37889062373143906, 160500643816367088, 679891637638612258, 2880067194370816120, 12200160415121876738, 51680708854858323072, 218922995834555169026, 927372692193078999176, 3928413764606871165730, 16641027750620563662096, 70492524767089125814114, 298611126818977066918552, 1264937032042997393488322, 5358359254990966640871840, 22698374052006863956975682, 96151855463018422468774568, 407305795904080553832073954, 1725375039079340637797070384, 7308805952221443105020355490, 30960598847965113057878492344, 131151201344081895336534324866, 555565404224292694404015791808]

                                Без дополнительных условий, любые исследования и попытки оптимизировать — бесполезная трата рабочего времени.


                                Что конечно не уменьшет интересность статьи, если отойти от просто решения тестового задания.

                                  +2
                                  Наверное вы не смотрели оригинальный пост или уже забыли) там всесторонне рассматривались способы вычисления N-ого числа Фибоначчи, ну и юзернейм этим комментарием как бы иронизировал, что наверное в этой самой простой задаче собака то и была зарыта. А так вы все правильно заметили в 99% случаев чем проще решение, тем лучше, а основное назначение этого поста — жвачка для мозгов.
                                  0
                                  Прелесть этого примера еще и в том, что он не будет работать на PHP, если его перевести как есть.

                                  Дело в том, что в PHP числа только до 64 бит точности. А дальше они становятся double, у которых не проверить четность из-за маленького диапазона.

                                  А в Питоне числа безразмерные

                                  In [16]: print(10**100 + 1)                                                                                                     
                                  10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001


                                  В PHP же нестрогая типизация, там скорее всего получится что-то такое:

                                  php > print(10**30 + 1);
                                  "десять в тридцатой один"
                                    0
                                    Там ограничение на значение чисел Фибоначчи, а не на их номер, поэтому будет работать. Если изменить задачу и поставить ограничение в 10000 на количество чисел, то да, надо будет подключать длинную арифметику.
                                    0

                                    Самое смешное было как то такое же тз. Фибоначи, запрос с др, и третье найти количество белых пикселей на изображении,
                                    К третьему заданию придрались, и я ещё написал два разных способа и доказал через картинку созданную самим php что количество пикселов считает верно. Фибоначи нашёл какой то пример в мане про генераторы, запрос сам составил. Оказывается это стандартный набор). Я отказался, так как удалёнка. Типо я прошёл

                                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                    Самое читаемое