Последовательность Фибоначчи, ставшая известной большинству благодаря фильму и книге «Код да Винчи», это ряд чисел, выведенный итальянским математиком Пизанским Леонардо, более известным под псевдонимом Фибоначчи, в тринадцатом веке. Последователи ученого заметили, что формула, которой подчинен данный ряд цифр, находит свое отображение в окружающем нас мире и перекликается с другими математическими открытиями, тем самым открывая для нас дверь в тайны мироздания. В этой статье мы расскажем, что такое последовательность Фибоначчи, рассмотрим примеры отображения этой закономерности в природе, а также сравним с другими математическими теориями.
Формулировка и определение понятия
Ряд Фибоначчи - это математическая последовательность, каждый элемент которой равен сумме двух предыдущих. Обозначим некой член последовательности как х n. Таким образом, получим формулу, справедливую для всего ряда: х n+2 =х n +х n+1. При этом порядок последовательности будет выглядеть так: 1, 1, 2, 3, 5, 8, 13, 21, 34. Следующим числом будет 55, так как сумма 21 и 34 равна 55. И так далее по такому же принципу.
Примеры в окружающей среде
Если мы посмотрим на растение, в частности, на крону из листьев, то заметим, что они распускаются по спирали. Между соседними листьями образуются углы, которые, в свою очередь, образуют правильную математическую последовательность Фибоначчи. Благодаря этой особенности каждый отдельно взятый листочек, который растет на дереве, получает максимальное количество солнечного света и тепла.
Математическая загадка Фибоначчи
Известный математик представил свою теорию в виде загадки. Звучит она следующим образом. Можно поместить пару кроликов в замкнутое пространство для того, чтобы узнать, какое количество пар кроликов родится в течении одного года. Учитывая природу этих животных, то, что каждый месяц пара способна производить на свет новую пару, а готовность к размножению у них появляется по достижении двух месяцев, в итоге он получил свой знаменитый ряд чисел: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 - где показано количество новых пар кроликов в каждом месяце.
Последовательность Фибоначчи и пропорциональное соотношение
Этот ряд имеет несколько математических нюансов, которые обязательно нужно рассмотреть. Он, приближаясь медленнее и медленнее (асимптотически), стремится к некоему пропорциональному соотношению. Но оно иррациональное. Другими словами, представляет собой число с непредсказуемой и бесконечной последовательностью десятичных чисел в дробной части. Например, соотношение любого элемента ряда варьируется около цифры 1,618, то превосходя, то достигая его. Следующее по аналогии приближается к 0,618. Что есть обратно пропорциональным к числу 1,618. Если мы поделим элементы через один, то получим 2,618 и 0,382. Как вы уже поняли, они также являются обратно пропорциональными. Полученные числа называются коэффициентами Фибоначчи. А теперь объясним, для чего мы выполняли эти вычисления.
Золотое сечение
Все окружающие нас предметы мы различаем по определенным критериям. Один из них - форма. Какие-то нас привлекают больше, какие-то меньше, а некоторые и вовсе не нравятся. Замечено, что симметричный и пропорциональный объект гораздо легче воспринимается человеком и вызывает чувство гармонии и красоты. Цельный образ всегда включает в себя части различного размера, которые находятся в определенном соотношении друг с другом. Отсюда вытекает ответ на вопрос о том, что называют Золотым сечением. Данное понятие означает совершенство соотношений целого и частей в природе, науке, искусстве и т. д. С математической точки зрения рассмотрим следующий пример. Возьмем отрезок любой длины и разделим его на две части таким образом, чтобы меньшая часть относилась к большей как сумма (длина всего отрезка) к большей. Итак, примем отрезок с за величину один. Его часть а будет равна 0,618, вторая часть b , выходит, равна 0,382. Таким образом, мы соблюдаем условие Золотого сечения. Отношение отрезка c к a равняется 1,618. А отношение частей c и b - 2,618. Получаем уже известные нам коэффициенты Фибоначчи. По такому же принципу строятся золотой треугольник, золотой прямоугольник и золотой кубоид. Стоит также отметить, что пропорциональное соотношение частей тела человека близко к Золотому сечению.
Последовательность Фибоначчи - основа всего?
Попробуем объединить теорию Золотого сечения и известного ряда итальянского математика. Начнем с двух квадратов первого размера. Затем сверху добавим еще квадрат второго размера. Подрисуем рядом такую же фигуру с длиной стороны, равной сумме двух предыдущих сторон. Аналогичным образом рисуем квадрат пятого размера. И так можно продолжать до бесконечности, пока не надоест. Главное, чтобы величина стороны каждого последующего квадрата равнялась сумме величин сторон двух предыдущих. Получаем серию многоугольников, длина сторон которых является числами Фибоначчи. Эти фигуры называются прямоугольниками Фибоначчи. Проведем плавную линию через углы наших многоугольников и получим… спираль Архимеда! Увеличение шага данной фигуры, как известно, всегда равномерно. Если включить фантазию, то полученный рисунок можно проассоциировать с раковиной моллюска. Отсюда можем сделать вывод, что последовательность Фибоначи - это основа пропорциональных, гармоничных соотношений элементов в окружающем мире.
Математическая последовательность и мироздание
Если присмотреться, то спираль Архимеда (где-то явно, а где-то завуалированно) и, следовательно, принцип Фибоначчи прослеживаются во многих привычных природных элементах, окружающих человека. Например, все та же раковина моллюска, соцветия обычной брокколи, цветок подсолнечника, шишка хвойного растения и тому подобное. Если заглянем подальше, то увидим последовательность Фибоначчи в бесконечных галактиках. Даже человек, вдохновляясь от природы и перенимая ее формы, создает предметы, в которых прослеживается вышеупомянутый ряд. Тут самое время вспомнить и о Золотом сечении. Наряду с закономерностью Фибоначчи прослеживаются принципы данной теории. Существует версия, что последовательность Фибоначчи - это своего рода проба природы адаптироваться к более совершенной и фундаментальной логарифмической последовательности Золотого сечения, которая практически идентична, но не имеет своего начала и бесконечна. Закономерность природы такова, что она должна иметь свою точку отсчета, от чего отталкиваться для создания чего-то нового. Отношение первых элементов ряда Фибоначчи далеки от принципов Золотого сечения. Однако чем дальше мы его продолжаем, тем больше это несоответствие сглаживается. Для определения последовательности необходимо знать три его элемента, которые идут друг за другом. Для Золотой последовательности же достаточно и двух. Так как она является одновременно арифметической и геометрической прогрессией.
Заключение
Все-таки, исходя из вышесказанного, можно задать вполне логичные вопросы: "Откуда появились эти числа? Кто этот автор устройства всего мира, попытавшийся сделать его идеальным? Было ли всегда все так, как он хотел? Если да, то почему возник сбой? Что будет дальше?" Находя ответ на один вопрос, получаешь следующий. Разгадал его - появляются еще два. Решив их, получаешь еще три. Разобравшись с ними, получишь пять нерешенных. Затем восемь, далее тринадцать, двадцать один, тридцать четыре, пятьдесят пять…
1,6180339887 4989484820 4586834365 6381177203 0917980576 2862135448 6227052604 6281890244 9707207204 1893911374 8475408807 5386891752 1266338622 2353693179 3180060766 7263544333 8908659593 9582905638 3226613199 2829026788 0675208766 8925017116 9620703222 1043216269 5486262963 1361443814 9758701220 3408058879 5445474924 6185695364 8644492410 4432077134 4947049565 8467885098 7433944221 2544877066 4780915884 6074998871 2400765217 0575179788 3416625624 9407589069 7040002812 1042762177 1117778053 1531714101 1704666599 1466979873 1761356006 7087480710 1317952368 9427521948 4353056783 0022878569 9782977834 7845878228 9110976250 0302696156 1700250464 3382437764 8610283831 2683303724 2926752631 1653392473 1671112115 8818638513 3162038400 5222165791 2866752946 5490681131 7159934323 5973494985 0904094762 1322298101 7261070596 1164562990 9816290555 2085247903 5240602017 2799747175 3427775927 7862561943 2082750513 1218156285 5122248093 9471234145 1702237358 0577278616 0086883829 5230459264 7878017889 9219902707 7690389532 1968198615 1437803149 9741106926 0886742962 2675756052 3172777520 3536139362
Числа Фибоначчи и золотое сечение составляют основу разгадки окружающего мира, построения его формы и оптимального зрительного восприятия человеком, с помощью которых он может ощущать красоту и гармонию.
Принцип определения размеров золотого сечения лежит в основе совершенства целого мира и его частей в своей структуре и функциях, его проявление можно видеть в природе, искусстве и технике. Учение о золотой пропорции было заложено в результате исследований древними учеными природы чисел.
Свидетельства использования древними мыслителями золотой пропорции приведены в книге Эвклида «Начала», написанной еще в 3 в. до н.э., который применял это правило для построения правильных 5-угольников. У пифагорейцев эта фигура считается священной, поскольку является одновременно симметричной и асимметричной. Пентаграмма символизировала жизнь и здоровье.
Числа Фибоначчи
Знаменитая книга Liber abaci математика из Италии Леонардо Пизанского, который в последующем стал известен, как Фибоначчи, увидела свет в 1202 г. В ней ученый впервые приводит закономерность чисел, в ряду которых каждое число является суммой 2-х предыдущих цифр. Последовательность чисел Фибоначчи заключается в следующем:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377 и т.д.
Также ученый привел ряд закономерностей:
Любое число из ряда, разделенное на последующее, будет равно значению, которое стремится к 0,618. Причем первые числа Фибоначчи не дают такого числа, но по мере продвижения от начала последовательности это соотношение будет все более точным.
Если же поделить число из ряда на предыдущее, то результат устремится к 1,618.
Одно число, поделенное на следующее через одно, покажет значение, стремящееся к 0,382.
Применение связи и закономерностей золотого сечения, числа Фибоначчи (0,618) можно найти не только в математике, но и в природе, в истории, в архитектуре и строительстве и во многих других науках.
Для практических целей ограничиваются приблизительным значением Φ = 1,618 или Φ = 1,62. В процентном округлённом значении золотое сечение - это деление какой-либо величины в отношении 62 % и 38 %.
Исторически изначально золотым сечением именовалось деление отрезка АВ точкой С на две части (меньший отрезок АС и больший отрезок ВС), чтобы для длин отрезков было верно AC/BC = BC/AВ. Говоря простыми словами, золотым сечением отрезок рассечён на две неравные части так, что меньшая часть относится к большей, как большая ко всему отрезку. Позже это понятие было распространено на произвольные величины.
Число Φ называется также золотым числом.
Золотое сечение имеет множество замечательных свойств, но, кроме того, ему приписывают и многие вымышленные свойства.
Теперь подробности:
Определение ЗС - это деление отрезка на две части в таком соотношении, при котором большая часть относится к меньшей, как их сумма (весь отрезок) к большей.
То есть, если мы примем весь отрезок c за 1, то отрезок a будет равен 0,618, отрезок b - 0,382. Таким образом, если взять строение, например, храм, построенный по принципу ЗС, то при его высоте скажем 10 метров, высота барабана с куполом будут равны 3,82 см, а высота основания строения будет 6, 18 см. (понятно, что цифры взяты ровными для наглядности)
А какова связь между ЗС и числами Фибоначчи?
Числа последовательности Фибоначчи это:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597…
Закономерность чисел в том, что каждое последующее число равно сумме двух предыдущих чисел.
0 + 1 = 1;
1 + 1 = 2;
2 + 3 = 5;
3 + 5 = 8;
5 + 8 = 13;
8 + 13 = 21 и т.д.,
а отношение смежных чисел приближается к отношению ЗС.
Так, 21: 34 = 0,617, а 34: 55 = 0,618.
То есть в основе ЗС лежат числа последовательности Фибоначчи.
Считается, что термин «Золотое сечение» ввел Леонардо Да Винчи, который говорил, «пусть никто, не будучи математиком, не дерзнет читать мои труды” и показывал пропорции человеческого тела на своём знаменитом рисунке «Витрувианский человек». “Если мы человеческую фигуру – самое совершенное творение Вселенной – перевяжем поясом и отмерим потом расстояние от пояса до ступней, то эта величина будет относиться к расстоянию от того же пояса до макушки, как весь рост человека к длине от пояса до ступней”.
Ряд чисел Фибоначчи наглядно моделируется (материализуется) в форме спирали.
А в природе спираль ЗС выглядит вот так:
При этом, спираль наблюдается повсеместно (в природе и не только):
Семена в большинстве растений расположены по спирали
- Паук плетет паутину по спирали
- Спиралью закручивается ураган
- Испуганное стадо северных оленей разбегается по спирали.
- Молекула ДНK закручена двойной спиралью. Молекулу ДНК составляют две вертикально переплетенные спирали длиной 34 ангстрема и шириной 21 ангстрема. Числа 21 и 34 следуют друг за другом в последовательности Фибоначчи.
- Эмбрион развивается в форме спирали
- Спираль «улитки во внутреннем ухе»
- Вода уходит в слив по спирали
- Спиральная динамика показывает развитие личности человека и его ценностей по спирали.
- Ну и конечно, сама Галактика имеет форму спирали
Таким образом можно утверждать, что сама природа построена по принципу Золотого Сечения, оттого эта пропорция гармоничнее воспринимается человеческим глазом. Она не требует «исправления» или дополнения получаемой картинки мира.
Фильм. Число Бога. Неопровержимое доказательство Бога; The number of God. The incontrovertible proof of God.
Золотые пропорции в строении молекулы ДНК
Все сведения о физиологических особенностях живых существ хранятся в микроскопической молекуле ДНК, строение которой также содержит в себе закон золотой пропорции. Молекула ДНК состоит из двух вертикально переплетенных между собой спиралей. Длина каждой из этих спиралей составляет 34 ангстрема, ширина 21 ангстрема. (1 ангстрем - одна стомиллионная доля сантиметра).
21 и 34 - это цифры, следующие друг за другом в последовательности чисел Фибоначчи, то есть соотношение длины и ширины логарифмической спирали молекулы ДНК несет в себе формулу золотого сечения 1:1,618
Золотое сечение в строении микромиров
Геометрические фигуры не ограничиваются только лишь треугольником, квадратом, пяти- или шестиугольником. Если соединить эти фигуры различным образом между собой, то мы получим новые трехмерные геометрические фигуры. Примерами этому служат такие фигуры как куб или пирамида. Однако кроме них существуют также другие трехмерные фигуры, с которыми нам не приходилось встречаться в повседневной жизни, и названия которых мы слышим, возможно, впервые. Среди таких трехмерных фигур можно назвать тетраэдр (правильная четырехсторонняя фигура), октаэдр, додекаэдр, икосаэдр и т.п. Додекаэдр состоит из 13-ти пятиугольников, икосаэдр из 20-и треугольников. Математики отмечают, что эти фигуры математически очень легко трансформируются, и трансформация их происходит в соответствии с формулой логарифмической спирали золотого сечения.
В микромире трехмерные логарифмические формы, построенные по золотым пропорциям, распространены повсеместно. К примеру, многие вирусы имеют трехмерную геометрическую форму икосаэдра. Пожалуй, самый известный из таких вирусов - вирус Adeno. Белковая оболочка вируса Адено формируется из 252 единиц белковых клеток, расположенных в определенной последовательности. В каждом углу икосаэдра расположены по 12 единиц белковых клеток в форме пятиугольной призмы и из этих углов простираются шипообразные структуры.
Впервые золотое сечение в строении вирусов обнаружили в 1950-хх гг. ученые из Лондонского Биркбекского Колледжа А.Клуг и Д.Каспар. 13 Первым логарифмическую форму явил в себе вирус Polyo. Форма этого вируса оказалась аналогичной с формой вируса Rhino 14.
Возникает вопрос, каким образом вирусы образуют столь сложные трехмерные формы, устройство которых содержит в себе золотое сечение, которые даже нашим человеческим умом сконструировать довольно сложно? Первооткрыватель этих форм вирусов, вирусолог А.Клуг дает такой комментарий:
«Доктор Каспар и я показали, что для сферической оболочки вируса самой оптимальной формой является симметрия типа формы икосаэдра. Такой порядок сводит к минимуму число связующих элементов… Большая часть геодезических полусферических кубов Букминстера Фуллера построены по аналогичному геометрическому принципу. 14 Монтаж таких кубов требует чрезвычайно точной и подробной схемы-разъяснения. Тогда как бессознательные вирусы сами сооружают себе столь сложную оболочку из эластичных, гибких белковых клеточных единиц.»
Итальянский математик Леонардо Фибоначчи жил в 13 столетии и одним из первых в Европе стал использовать арабские (индийские) цифры. Он придумал несколько искусственную задачу о кроликах, которых выращивают на ферме, причем все они считаются самками, самцы игнорируются. Кролики начинают размножаться после того, как им исполняется два месяца, а потом каждый месяц рожают по кролику. Кролики никогда не умирают.
Нужно определить, сколько кроликов будет на ферме через n месяцев, если в начальный момент времени был только один новорожденный кролик.
Очевидно, что
фермер имеет одного кролика в первый
месяц и одного кролика – во второй
месяц. На третий месяц будет уже два
кролика, на четвертый – три и т.д.
Обозначим количество кроликов в n
месяце как
.
Таким образом,
,
,
,
,
,
…
Можно построить
алгоритм, позволяющий найти
при любомn
.
Согласно условию
задачи общее количество кроликов
вn
+1
месяце раскладывается на три составляющие:
одномесячные кролики, не способные к размножению, в количестве
;
Таким образом, получим
. (8.1)
Формула (8.1) позволяет вычислить ряд чисел: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, …
Числа в данной последовательности называются числами Фибоначчи .
Если
принять
и
,
то с помощью формулы (8.1) можно определить
все остальные числа Фибоначчи. Формула
(8.1) называется рекуррентной
формулой (recurrence
– «возвращение» на латыни).
Пример 8.1. Предположим, что имеется лестница в n ступенек. Мы можем подниматься по ней с шагом в одну ступеньку, либо – с шагом в две ступеньки. Сколько существует комбинаций различных способов подъема?
Если n = 1, имеется только один вариант решения задачи. Для n = 2 существует 2 варианта: два единичных шага либо один двойной. Для n = 3 существует 3 варианта: три единичных шага, либо один единичный и один двойной, либо один двойной и один единичный.
В следующем случае n = 4, имеем 5 возможностей (1+1+1+1, 2+1+1, 1+2+1, 1+1+2, 2+2).
Для
того чтобы ответить на заданный вопрос
при произвольном n
,
обозначим количество вариантов как
,
и попробуем определить
по известным
и
.
Если мы стартуем с единичного шага, то
имеем
комбинаций для оставшихсяn
ступенек. Если стартуем с двойного шага,
то имеем
комбинаций для оставшихсяn
–1
ступенек. Общее количество вариантов
для n
+1
ступенек равно
. (8.2)
Полученная
формула как близнец напоминает формулу
(8.1). Тем не менее, это не позволяет
отождествлять количество комбинаций
с числами Фибоначчи
.
Мы видим, например, что
,
но
.
Однако имеет место следующая зависимость:
.
Это
справедливо для n
= 1, 2, и также справедливо для каждого n
.
Числа Фибоначчи и количество комбинаций
вычисляются по одной и той же формуле,
однако начальные значения
,
и
,
у них различаются.
Пример 8.2.
Этотпример имеет
практическое
значение для задач помехоустойчивого
кодирования. Найдем число всех двоичных
слов длины n
,
не содержащих несколько нулей подряд.
Обозначим это число через
.
Очевидно,
,
а слова длины 2, удовлетворяющие нашему
ограничению, таковы: 10, 01, 11, т.е.
.
Пусть
– такое слово изn
символов. Если символ
,
то
может быть произвольным (
)-буквенным
словом, не содержащим несколько нулей
подряд. Значит, число слов с единицей
на конце равно
.
Если же символ
,
то обязательно
,
а первые
символа
могут быть произвольными с учетом
рассматриваемых ограничений. Следовательно,
имеется
слов длины
n
с нулем на конце. Таким образом, общее
число интересующих нас слов равно
.
С учетом того, что
и
,
полученная последовательность чисел
– это числа Фибоначчи.
Пример 8.3.
В
примере 7.6 мы нашли, что число двоичных
слов постоянного веса t
(и длиной k
)
равно
.
Теперь найдем число двоичных слов
постоянного весаt
,
не содержащих несколько нулей подряд.
Рассуждать можно
так. Пусть
число нулей в рассматриваемых словах.
В любом слове имеется
промежутков между ближайшими нулями,
в каждом из которых находится одна или
несколько единиц. Предполагается, что
.
В противном случае нет ни одного слова
без рядом стоящих нулей.
Если из каждого
промежутка удалить ровно по одной
единице, то получим слово длины
,
содержащее
нулей. Любое такое слово может быть
получено указанным образом из некоторого
(и притом только одного)k
-буквенного
слова, содержащего
нулей, никакие два из которых не стоят
рядом. Значит, искомое число совпадает
с числом всех слов длины
,
содержащих ровно
нулей, т.е. равно
.
Пример 8.4.
Докажем,что сумма
равна числам Фибоначчи для любого целого
.
Символ
обозначаетнаименьшее
целое число, большее или равное
.
Например, если
,
то
;
а если
,
то
ceil
(«потолок»). Также встречается символ
,
который обозначаетнаибольшее
целое число, меньшее или равное
.
По-английски эту операцию называютfloor
(«пол»).
Если
,
то
.
Если
,
то
.
Если
,
то
.
Таким образом, для рассмотренных случаев сумма действительно равна числам Фибоначчи. Теперь приведем доказательство для общего случая. Поскольку числа Фибоначчи можно получить с помощью рекуррентного уравнения (8.1), то должно выполняться равенство:
.
И оно действительно выполняется:
Здесь мы использовали
полученную ранее формулу (4.4):
.
Сумма чисел Фибоначчи
Определим сумму первых n чисел Фибоначчи.
0+1+1+2+3+5 = 12,
0+1+1+2+3+5+8 = 20,
0+1+1+2+3+5+8+13 = 33.
Легко заметить, что прибавлением к правой части каждого уравнения единицы мы снова получаем число Фибоначчи. Общая формула для определения суммы первых n чисел Фибоначчи имеет вид:
Докажем это, используя метод математической индукции. Для этого запишем:
Эта
сумма должна быть равна
.
Сократив левую и правую часть уравнения на –1, получим уравнение (6.1).
Формула для чисел Фибоначчи
Теорема 8.1. Числа Фибоначчи можно рассчитать по формуле
.
Доказательство . Убедимся в справедливости этой формулы для n = 0, 1, а затем докажем справедливость данной формулы для произвольного n по индукции. Вычислим отношение двух ближайших чисел Фибоначчи:
Мы
видим, что отношение этих чисел колеблется
около значения 1.618 (если игнорировать
несколько первых значений). Этим свойством
числа Фибоначчи напоминают члены
геометрической прогрессии. Примем
,
(
).
Тогда выражение
преобразуется в
которое после упрощений выглядит так
.
Мы получили квадратное уравнение, корни которого равны:
Теперь можем записать:
(где
c
является константой). Оба члена 
и
не дают чисел Фибоначчи,
например
,
в то время как
.
Однако разность 
удовлетворяет
рекуррентному уравнению:
Для
n
=0
эта разность дает
,
то есть: 
.
Однако при n
=1
мы имеем 
.
Чтобы получить
,
необходимо принять:
.
Теперь
мы имеем две последовательности: 
и 
,
которые начинаются с одинаковых двух
чисел и удовлетворяют одной и той же
рекуррентной формуле. Они должны быть
равны: 
.
Теорема доказана.
При
возрастании n
член
становится очень большим, в то время
как
,
и роль члена
в разности сокращается.
Поэтому при больших n
приближенно можем записать
.
Мы игнорируем 1/2 (поскольку числа Фибоначчи возрастают до бесконечности при росте n до бесконечности).
Отношение
называется золотым
сечением
,
его используют за пределами математики
(например, в скульптуре и архитектуре).
Золотым сечением является отношение
между диагональю и стороной правильного
пятиугольника
(рис. 8.1).
Рис. 8.1. Правильный пятиугольник и его диагонали
Для обозначения
золотого сечения принято использовать
букву
в честь известного афинского скульптора
Фидия.
Простые числа
Все натуральные числа, большие единицы, распадаются на два класса. К первому относятся числа, имеющие ровно два натуральных делителя, единицу и самого себя, ко второму – все остальные. Числа первого класса называют простыми , а второго – составными . Простые числа в пределах первых трех десятков: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, …
Свойства простых чисел и их связь со всеми натуральными числами изучалась Евклидом (3 век до нашей эры). Если выписывать простые числа подряд, то можно заметить, что относительная плотность их убывает. На первый десяток их приходится 4, т. е. 40%, на сотню – 25, т.е. 25%, на тысячу – 168, т.е. меньше 17%, на миллион – 78498, т.е. меньше 8%, и т.д.. Тем не менее, их общее число бесконечно.
Среди простых чисел попадаются пары таких, разность между которыми равна двум (так называемые простые близнецы ), однако конечность или бесконечность таких пар не доказана.
Евклид считал очевидным, что с помощью умножения только простых чисел можно получить все натуральные числа, причем каждое натуральное число представимо в виде произведения простых чисел единственным образом (с точностью до порядка множителей). Таким образом, простые числа образуют мультипликативный базис натурального ряда.
Изучение распределения
простых чисел привело к созданию
алгоритма, позволяющего получать таблицы
простых чисел. Таким алгоритмом является
решето
Эратосфена
(3 век до нашей эры). Этот метод заключается
в отсеивании (например, путем зачеркивания)
тех целых чисел заданной последовательности
,
которые делятся хотя бы на одно из
простых чисел, меньших
.
Теорема 8 . 2 . (теорема Евклида). Число простых чисел бесконечно .
Доказательство . Теорему Евклида о бесконечности числа простых чисел докажем способом, предложенным Леонардом Эйлером (1707–1783). Эйлер рассмотрел произведение по всем простым числам p :
при
.
Это произведение сходится, и если его
раскрыть, то в силу однозначности
разложения натуральных чисел на простые
сомножители получается, что оно равняется
сумме ряда
,
откуда следует тождество Эйлера:
.
Так как при
ряд справа расходится (гармонический
ряд), то из тождества Эйлера следует
теорема Евклида.
Русский математик
П.Л. Чебышев (1821–1894) вывел формулу,
определяющую пределы, в которых заключено
число простых чисел
,
не превосходящихX
:
,
где
,
.
- Перевод
Введение
Программистам числа Фибоначчи должны уже поднадоесть. Примеры их вычисления используются везде. Всё от того, что эти числа предоставляют простейший пример рекурсии. А ещё они являются хорошим примером динамического программирования. Но надо ли вычислять их так в реальном проекте? Не надо. Ни рекурсия, ни динамическое программирование не являются идеальными вариантами. И не замкнутая формула, использующая числа с плавающей запятой. Сейчас я расскажу, как правильно. Но сначала пройдёмся по всем известным вариантам решения.Код предназначен для Python 3, хотя должен идти и на Python 2.
Для начала – напомню определение:
F n = F n-1 + F n-2
И F 1 = F 2 =1.
Замкнутая формула
Пропустим детали, но желающие могут ознакомиться с выводом формулы . Идея в том, чтобы предположить, что есть некий x, для которого F n = x n , а затем найти x.Что означает
Сокращаем x n-2
Решаем квадратное уравнение:
Откуда и растёт «золотое сечение» ϕ=(1+√5)/2. Подставив исходные значения и проделав ещё вычисления, мы получаем:
Что и используем для вычисления F n .
From __future__ import division import math def fib(n): SQRT5 = math.sqrt(5) PHI = (SQRT5 + 1) / 2 return int(PHI ** n / SQRT5 + 0.5)
Хорошее:
Быстро и просто для малых n
Плохое:
Требуются операции с плавающей запятой. Для больших n потребуется большая точность.
Злое:
Использование комплексных чисел для вычисления F n красиво с математической точки зрения, но уродливо - с компьютерной.
Рекурсия
Самое очевидное решение, которое вы уже много раз видели – скорее всего, в качестве примера того, что такое рекурсия. Повторю его ещё раз, для полноты. В Python её можно записать в одну строку:Fib = lambda n: fib(n - 1) + fib(n - 2) if n > 2 else 1
Хорошее:
Очень простая реализация, повторяющая математическое определение
Плохое:
Экспоненциальное время выполнения. Для больших n очень медленно
Злое:
Переполнение стека
Запоминание
У решения с рекурсией есть большая проблема: пересекающиеся вычисления. Когда вызывается fib(n), то подсчитываются fib(n-1) и fib(n-2). Но когда считается fib(n-1), она снова независимо подсчитает fib(n-2) – то есть, fib(n-2) подсчитается дважды. Если продолжить рассуждения, будет видно, что fib(n-3) будет подсчитана трижды, и т.д. Слишком много пересечений.Поэтому надо просто запоминать результаты, чтобы не подсчитывать их снова. Время и память у этого решения расходуются линейным образом. В решении я использую словарь, но можно было бы использовать и простой массив.
M = {0: 0, 1: 1} def fib(n): if n in M: return M[n] M[n] = fib(n - 1) + fib(n - 2) return M[n]
(В Python это можно также сделать при помощи декоратора, functools.lru_cache.)
Хорошее:
Просто превратить рекурсию в решение с запоминанием. Превращает экспоненциальное время выполнение в линейное, для чего тратит больше памяти.
Плохое:
Тратит много памяти
Злое:
Возможно переполнение стека, как и у рекурсии
Динамическое программирование
После решения с запоминанием становится понятно, что нам нужны не все предыдущие результаты, а только два последних. Кроме этого, вместо того, чтобы начинать с fib(n) и идти назад, можно начать с fib(0) и идти вперёд. У следующего кода линейное время выполнение, а использование памяти – фиксированное. На практике скорость решения будет ещё выше, поскольку тут отсутствуют рекурсивные вызовы функций и связанная с этим работа. И код выглядит проще.Это решение часто приводится в качестве примера динамического программирования.
Def fib(n): a = 0 b = 1 for __ in range(n): a, b = b, a + b return a
Хорошее:
Быстро работает для малых n, простой код
Плохое:
Всё ещё линейное время выполнения
Злое:
Да особо ничего.
Матричная алгебра
И, наконец, наименее освещаемое, но наиболее правильное решение, грамотно использующее как время, так и память. Его также можно расширить на любую гомогенную линейную последовательность. Идея в использовании матриц. Достаточно просто видеть, что
А обобщение этого говорит о том, что
Два значения для x, полученных нами ранее, из которых одно представляло собою золотое сечение, являются собственными значениями матрицы. Поэтому, ещё одним способом вывода замкнутой формулы является использование матричного уравнения и линейной алгебры.
Так чем же полезна такая формулировка? Тем, что возведение в степень можно произвести за логарифмическое время. Это делается через возведения в квадрат . Суть в том, что
Где первое выражение используется для чётных A, второе для нечётных. Осталось только организовать перемножения матриц, и всё готово. Получается следующий код. Я организовал рекурсивную реализацию pow, поскольку её проще понять. Итеративную версию смотрите тут.
Def pow(x, n, I, mult): """ Возвращает x в степени n. Предполагает, что I – это единичная матрица, которая перемножается с mult, а n – положительное целое """ if n == 0: return I elif n == 1: return x else: y = pow(x, n // 2, I, mult) y = mult(y, y) if n % 2: y = mult(x, y) return y def identity_matrix(n): """Возвращает единичную матрицу n на n""" r = list(range(n)) return [ for j in r] def matrix_multiply(A, B): BT = list(zip(*B)) return [ for row_a in A] def fib(n): F = pow([, ], n, identity_matrix(2), matrix_multiply) return F
Хорошее:
Фиксированный объём памяти, логарифмическое время
Плохое:
Код посложнее
Злое:
Приходится работать с матрицами, хотя они не так уж и плохи
Сравнение быстродействия
Сравнивать стоит только вариант динамического программирования и матрицы. Если сравнивать их по количеству знаков в числе n, то получится, что матричное решение линейно, а решение с динамическим программированием – экспоненциально. Практический пример – вычисление fib(10 ** 6), числа, у которого будет больше двухсот тысяч знаков.N = 10 ** 6
Вычисляем fib_matrix: у fib(n) всего 208988 цифр, расчёт занял 0.24993 секунд.
Вычисляем fib_dynamic: у fib(n) всего 208988 цифр, расчёт занял 11.83377 секунд.
Теоретические замечания
Не напрямую касаясь приведённого выше кода, данное замечание всё-таки имеет определённый интерес. Рассмотрим следующий граф:
Подсчитаем количество путей длины n от A до B. Например, для n = 1 у нас есть один путь, 1. Для n = 2 у нас опять есть один путь, 01. Для n = 3 у нас есть два пути, 001 и 101. Довольно просто можно показать, что количество путей длины n от А до В равно в точности F n . Записав матрицу смежности для графа, мы получим такую же матрицу, которая была описана выше. Это известный результат из теории графов, что при заданной матрице смежности А, вхождения в А n - это количество путей длины n в графе (одна из задач, упоминавшихся в фильме «Умница Уилл Хантинг»).
Почему на рёбрах стоят такие обозначения? Оказывается, что при рассмотрении бесконечной последовательности символов на бесконечной в обе стороны последовательности путей на графе, вы получите нечто под названием "подсдвиги конечного типа ", представляющее собой тип системы символической динамики. Конкретно этот подсдвиг конечного типа известен, как «сдвиг золотого сечения», и задаётся набором «запрещённых слов» {11}. Иными словами, мы получим бесконечные в обе стороны двоичные последовательности и никакие пары из них не будут смежными. Топологическая энтропия этой динамической системы равна золотому сечению ϕ. Интересно, как это число периодически появляется в разных областях математики.
по материалам книги Б. Биггса «вышел хеджер из тумана»
Числа Фибоначчи
Фибоначчи прожил долгую, особенно для своего времени, жизнь, которую посвятил решению ряда математических задач, сформулировав их в своем объемном труде «Книга о счетах» (начало 13 века). Его всегда интересовала мистика чисел — вероятно, он был не менее гениален, чем Архимед или Евклид. Задачи, связанные с квадратными уравнениями, ставились и частично решались и до Фибоначчи, например известным Омаром Хайямом — ученым и поэтом; однако Фибоначчи сформулировал задачу о размножении кроликов, выводы из которой и не позволили его имени затеряться в веках.
Вкратце задача заключается в следующем. В место, огороженное со всех сторон стеной, поместили пару кроликов, причем любая пара кроликов производит на свет другую пару каждый месяц, начиная со второго месяца своего существования. Размножение кроликов во времени при этом будет описываться последовательностью: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 и т.д. С математической точки зрения последовательность оказалась просто уникальной, поскольку обладала целым рядом выдающихся свойств:
сумма двух любых последовательных чисел есть следующее число последовательности;
отношение каждого числа последовательности, начиная с пятого, к предыдущему, равно 1.618;
разница между квадратом любого числа и квадратом числа на две позиции левее, будет числом Фибоначчи;
сумма квадратов стоящих рядом чисел будет числом Фибоначчи, которое стоит через две позиции после большего из возведенных в квадрат чисел
Из этих выводов наиболее интересен второй, поскольку в нем используется число 1.618, известное как «золотое сечение». Это число было известно еще древним грекам, которые использовали его при постройке Парфенона (кстати, по некоторым данным служившим грекам Центробанком). Не менее интересно и то, что число 1.618 можно обнаружить в природе как в микро-, так и макромасштабе — от витков спирали на панцире улитки до больших спиралей космических галактик.
Пирамиды в Гизе, созданные древними египтянами, при конструировании также содержали сразу несколько параметров ряда Фибоначчи. Прямоугольник, одна сторона которого больше другой в 1.618 раза, выглядит наиболее приятно для глаза — это соотношение использовал Леонардо да Винчи для своих картин, а в более житейском плане им пользовались при создании окон или дверных проемов. Даже волну, как на рисунке в начале статьи, можно представить в виде спирали Фибоначчи.
В живой природе последовательность Фибоначчи проявляется не менее часто — ее можно найти в когтях, зубах, подсолнухе, паутине и даже размножении бактерий. При желании последовательность обнаруживается практически во всем, включая человеческое лицо и тело. И тем не менее многие утверждения, находящие числа Фибоначчи в природных и исторических явлениях, явно неверны - это распространенный миф, который оказывается неточной подгонкой под желаемый результат.
Числа Фибоначчи на финансовых рынках
Одним из первых, кто наиболее плотно занимался приложением чисел Фибоначчи к финансовому рынку, был Р. Эллиот. Его труды не пропали даром в том смысле, что рыночные описания с применением теории Фибоначчи часто называются «волнами Эллиота». В основу развития рынков здесь была положена модель развития человечества из суперциклов с тремя шагами вперед и двумя назад.
То, что человечество развивается нелинейно, очевидно почти каждому — знания Древнего Египта и атомистическое учение Демокрита было полностью утрачено в Средневековье, т.е. спустя примерно 2000 лет. Однако даже если принять теорию шагов и их количество за истину, остается неясным размер каждого шага, что делает волны Эллиота сравнимыми с предсказательной силой орла и решки. Отправная точка и правильный расчет числа волн были и видимо будут главной слабостью теории.
Тем не менее локальные успехи у теории были. Боб Претчер, которого можно считать учеником Эллиота, правильно предсказал бычий рынок начала 80-х, а 1987 год — как поворотный. Это действительно случилось, после чего Боб очевидно чувствовал себя гением — по крайней мере, в глазах других он точно стал инвестиционным гуру.
Подписка на Elliott Wave Theorist Пречтера в тот год выросла до 20 000, однако уменьшилась в начале 1990-х годов, поскольку предсказываемые далее «гибель и мрак» американского рынка решили немного повременить. Однако для японского рынка это сработало, и ряд сторонников теории, «опоздавших» там на одну волну, потеряли либо свои капиталы, либо капиталы клиентов своих компаний. Равным образом и с теми же успехами теорию нередко пытаются применить к торговле на валютном рынке.
Волны Эллиота охватывают самые разные периоды торговли — от недельной, что роднит ее со стандартными стратегиями теханализа, до расчета на десятилетия, т.е. влезает на территорию фундаментальных предсказаний. Это возможно благодаря варьированию числа волн. Слабости теории, о которых говорилось выше, позволяют ее адептам говорить не о несостоятельности волн, а о собственных просчетах в их числе и неверном определении исходного положения. Это похоже на лабиринт — даже если у вас есть верная карта, то выйти по ней можно лишь при условии, что понимаешь, где именно находишься. Иначе пользы от карты нет. В случае же с волнами Эллиота есть все признаки сомневаться не только в правильности своего месторасположения, но и в верности карты как таковой.
Выводы
Волновое развитие человечества имеет под собой реальную основу — в средние века волны инфляции и дефляции чередовались между собой, когда войны сменяли относительно спокойную мирную жизнь. Наблюдение последовательности Фибоначчи в природе по крайней мере в отдельных случаях сомнения тоже не вызывает. Поэтому каждый на вопрос, кто есть Бог: математик или генератор случайных чисел — вправе давать собственный ответ. Лично мое мнение: хотя всю человеческую историю и рынки можно представить в волновой концепции, высоту и продолжительность каждой волны не дано предугадать никому.