WWW.NET.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Интернет ресурсы
 

«Ученица: Безменова Саша Класс: 8 Руководитель: Сгибнев А. И. Последовательность Фибоначчи – это последовательность, в которой каждый следующий член равен сумме ...»

ПРОЕКТНАЯ РАБОТА ПО

МАТЕМАТИКЕ

ЦИКЛЫ В РЯДУ ОСТАТКОВ ОТ

ДЕЛЕНИЯ ЧИСЕЛ

ПОСЛЕДОВАТЕЛЬНОСТИ

ФИБОНАЧЧИ

Ученица: Безменова Саша

Класс: 8

Руководитель: Сгибнев А. И.

Последовательность Фибоначчи – это последовательность, в которой каждый

следующий член равен сумме двух предыдущих. Ясно, что такая последовательность полностью определяется первыми двумя членами. Будем обозначать Ф(a;b) последовательность Фибоначчи, задающуюся первыми двумя членами a и b.

Рассмотрим остатки от деления членов последовательности Ф(0;1) на 2:

0,1,1,0,1,1,0,1,1,… (будем называть последовательность остатков от деления чисел последовательности Фибоначчи просто последовательностью остатков). Приведем ещё пример: та же последовательность Фибоначчи, делитель k=5. Последовательность остатков:

0,1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1, | 0,1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1, | 0,1,… Видно, что в первом случае участок 0,1,1, а во втором случае участок 0,1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1 всё время повторяются. Возникает вопрос – будут ли они повторяться бесконечно? Будут ли также периодичны последовательности остатков от деления чисел произвольной последовательности Ф(a;b) на произвольное натуральное число k, большее 1?



Теорема. Последовательность остатков от деления чисел произвольной последовательности Фибоначчи на произвольное натуральное число k всегда периодична.

Доказательство. Так же, как и каждый член последовательности Фибоначчи, каждый следующий остаток можно получить из двух предыдущих. Следовательно, если какая-то пара остатков повторится, то последовательность остатков зациклится.

Поскольку при делении на k возможно лишь k различных остатков, то возможно не более k2 различных пар остатков. Это число конечно, следовательно, какая-нибудь пара остатков обязательно повторится и последовательность зациклится.

Следующая теорема показывает, что период в последовательности остатков начинается с первого члена. Вообще говоря, для произвольной периодической последовательности это не так. Например, рассмотрим периодичную десятичную дробь. В ней периодичность может начаться как с первого, так и с любого другого члена, например 0,142(3). Для последовательности Ф(0;1) и k=2 или k=5 периодичность в последовательности остатков также началась с первого члена. А верно ли это для других последовательностей Фибоначчи и других k?

Теорема. Первый период в последовательности остатков всегда начинается с первого члена.

Доказательство. Последовательность Фибоначчи (а, следовательно, и последовательность остатков) можно восстанавливать по двум членам не только вперёд, но и назад. Обозначим ai - i-й член последовательности Фибоначчи, а ri - остаток от деления этого числа на k. Тогда ai 1 = ai + 1 ai ri 1 = ri + 1 ri (здесь и далее все сложения и вычитания для остатков понимаются по модулюk).

Предположим, что первый период в последовательности остатков начался не с первого члена. Тогда, восстанавливая последовательность остатков назад по первым двум членам первого периода ri и ri+1, получим, что ri-1 равно последнему члену периода (так как после последнего члена периода стоят первые два члена периода), ri-2 равно предпоследнему и т.





д. Таким образом, r1 и r2 будут равны каким-то двум соседним членам периода, и, следовательно, с них и будет начинаться первый период.

Возникает вопрос – какова длина периода для данных последовательности Ф(a;b) и k? Периодом максимальной длины будет период, в котором есть все возможные пары остатков. Первые две пары образуют участок длиной 3. Добавляя две пары, мы увеличиваем длину на 2, а добавляя одну пару – на 1. Следовательно, если k делится на 2, то максимальная длина периода будет равна L= k2 : 2 2+1 = k2 +1, а если k не делится на 2, то максимальная длина периода будет равна L= (k2 -1): 2 2+2 = k2 +1. Поэтому если мы попытаемся найти длину периода перебором (поиском пары остатков, равной первой паре), в худшем случае на это потребуется k2 +1 операций. Попытаемся оптимизировать поиск.

Рассмотрим последовательность Ф(0;1).

Поскольку первое число последовательности остатков 0, оно встретится в нём ещё - в начале каждого цикла и в некоторых случаях где-то в середине цикла. Но первый 0, перед которым стоит 1 – это начало следующего цикла, так как 1+0=1 и 11 (mod k) для любого k1.

Выпишем последовательность остатков в следующем виде (каждая строка – участок последовательности остатков от 0 до остатка, предшествующего следующему 0):

0, 1, 1, 2,, r 1, (mod k ) 0, r, r, 2r,, r 2, (mod k ) 0, r 2, r 2, 2r 2,, r 3, (mod k )

–  –  –

Поскольку r и k взаимно просты, найдётся такое m, что r m 1( mod k ). Первая степень r, равная 1 – это конец цикла.

Лемма. Все строки имеют одинаковую длину.

Доказательство. Заметим, что j-й член (i+1)-й строки равен j-му члену i-й строки, умноженному на r. Следовательно, если какая-то строка (длинной l) короче соседней, то (l +1)-й элемент этой соседней строки равен 0r=0, т. е. её длина также равна l.

Итак, чтобы найти конец периода, нам достаточно найти второй 0, а затем перебирать степени идущего перед ним числа, пока не получится число, сравнимое с единицей по модулю k. Иными словами, надо пройти в таблице первую строку, а затем последний столбец. Если строк X, то этот алгоритм быстрее обычного перебора почти в X раз.

–  –  –

Таким образом, n в последовательности остатков от деления чисел последовательности Ф(0;n) встречается на том и только на том месте, где в последовательности остатков от деления чисел последовательности Ф(0;1) встречается 1, а 0 – на том и только на том месте, где встречается 0. Следовательно, длина периода для последовательности Ф(0; n) будет такая же, как и для последовательности Ф(0;1) при делении на тот же делитель, и мы можем найти её по описанному выше алгоритму.

II. (n, k)1.

Пусть (n, k)1. Рассмотрим последовательность Ф(0;n/(n, k)) (все члены будут делиться на (n, k), потому что каждый член делится на n) и делитель k/(n, k). Длину его цикла мы можем найти из предыдущего результата, так как числа n/(n, k) и k/(n, k) взаимно простые. Докажем, что она будет равна искомой.

Заметим, что при увеличении делимого и делителя в s раз остаток также увеличивается в s раз. Если же делимое и делитель делятся нацело на s, то и остаток также делится, причём остаток «делённой» последовательности равен остатку исходной, делённому на s.

Тем самым циклы исходной и «делённой» последовательности имеют одинаковую длину.

Рассмотрим последовательности Ф(n;0) и Ф(n,n), где n1.

Видно, что эти последовательности представляют собой последовательность Ф(0;n), «сдвинутую» в первом случае на 1 влево, а во втором – на 1 вправо.

Следовательно, и длина цикла будет как у последовательности (0;n), а поиск длины для неё уже оптимизирован.

Рассмотрим последовательность Ф(n;m).

Каждый член этой последовательности (и последовательности остатков) представляет собой сумму соответствующих членов последовательностей Ф(n;0) и Ф(0;m) (последовательностей их остатков). Пусть длина периода для последовательности Ф(n;0) равна Ln;0, а для последовательности Ф(0;m) - L0;m. Тогда с [Ln;0,L0;m]-того члена последовательности остатков для последовательности Ф(n;m) начнётся какой-то период, хотя этот период вообще говоря не является минимальным.

Вернёмся к алгоритму вычисления длины периода для последовательности Ф(0:1).

Была написана программа, которая вычисляла длину периода для последовательности Ф(0;1) при k от 2 до 10000 простым перебором и по описанному выше алгоритму, считала число операций при вычислении тем и другим способом, а также вычисляла, сколько раз встречался 0 в периоде (или, что то же самое, сколько было бы строчек в при записи последовательности остатков описанным выше способом или какое значение принимает минимальное m, такое что r m 1( mod k ) ).

Результаты:

1. Оказалось, что m принимало значения 1, 2, 4.

2. Оказалось, что во всех 9999 случаях второй способ даёт меньше действий. Из них в 8989 случаях – меньше более чем в 2 раза На основании первого наблюдения была сформулирована следующая Теорема. Если m – минимальное число, такое что r m 1( mod k ), где r – остаток от деления члена последовательности Ф(0;1), стоящего перед вторым членом той же последовательности, сравнимым с нулём по модулю k, то m может быть равным только 1, 2 или 4.

Доказательство. Выпишем остатки: 0,1,1,2,…r,0,… Пусть длина строки (от 0 до r) = n. Теперь восстановим последовательность остатков назад по паре r,0 (при этом заметим, что на каждом шаге получаем r, умноженное на соответствующий член последовательности Ф(0;1) – 0=r(-a1), r=ra2, -r=r(-a3), и т.

д.):

± a n +1 r, a n r,± a n 1 r,...,2r, r, r,0,... Следовательно ± a n r 1( mod k ). Также из первого ряда видно, что a n r ( mod k ).

Если r=1, то m=1. Если r1, то рассмотрим два случая: 1) a n r 1( mod k ) и 2) a n r 1( mod k ).

–  –  –

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

Я благодарна моему научному руководителю А. И. Сгибневу, а также Д.Э. Шнолю и А.С. Воронцову за обсуждения темы и помощь в оформлении результатов.



Похожие работы:

«Технологии и оборудование для подготовки поверхности Окрасочные и сушильные камеры. Автоматизация процессов нанесения покрытий • Установки дробеметнои очистки и консервации для профильного, сортового и листового проката • Камеры дробеструйной очистки для готовых узлов и изделий • Окрасочные и сушильные камеры • Электростатическое нанесен...»

«ХИМИЯ Полимерно-солевые композиции П ОЛИМЕ РН ОСОЛЕВ ЫЕ КО М ПО З ИЦ ИИ П ОЛИМЕ РН ОСОЛЕВ ЫЕ КО М ПО З ИЦ ИИ А.А. Остроушко Александр Александрович Остроушко, доктор химических наук, старший научный сотрудник, руководитель лаборатории Уральского государственного университета им. А.М. Горького. Руководитель проектов 02-03-32777, 02-03-96443. П...»

«Федеральное агентство по образованию Московский инженерно-физический институт (государственный университет) Методы обработки результатов ядерно-физического эксперимента Учебное пособие Под редакцией В....»

«fUtwosfiff сообщения объединенного института ядерных исследовании дубна Р1-92-376 Г.В.Велев*, НЛ.Русакович АНАЛИЗ ИНФОРМАЦИИ В ЭКСПЕРИМЕНТЕ ПО ИЗУЧЕНИЮ РАСПАДА 1С -* л°е\ НА УСТАНОВКЕ ГИПЕРОН щ Jrjjf * "•Компьютерный центр по физике" БАН, София, Болгария л: • l. введение в настоящее время на установке ГИПЕРОН [1] о...»

«Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования Владимирский государственный университет А.Г. СЕРГЕЕВ ВВЕДЕНИЕ В НАНОМЕТРОЛОГИЮ Учебное пособие Допущено Учебно-методическим объединением вузов по образованию в обла...»

«Конспект лекций по курсу общей физики. Часть III “Оптика. Квантовые представления о свете. Атомная физика и физика ядра” Лекция № 13 9. СТРОЕНИЕ ЯДРА 9.1. Состав атомного ядра Теперь мы должны обратить наше внимание на существенно более трудную проблему строения ядра. Открытие Беккерелем явления радиоактивности урана (1896г) и открытие рентгеновск...»

«КАЗАНСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ ИНСТИТУТ ФИЗИКИ Кафедра общей физики Н.И.МОНАХОВА, Е.А.ФИЛИППОВА, А.И.ФИШМАН ЭКСПЕРИМЕНТАЛЬНЫЕ ЗАДАЧИ ОБЩЕГО ФИЗИЧЕСКОГО ПРАКТИКУМА ПО ОПТИКЕ. ГЕОМЕТРИЧЕСКАЯ ОПТИКА. Казань – 2012 УДК 535 Принято на заседании кафедры общей физики Протокол № 8 от 6 марта 2012 года Ре...»

«PA550 PVC MEMBRANE PRESS ADHESIVE Паспорт безопасности в соответствии с Регламентом (Евросоюз) 2015/830 Дата выпуска: 01.12.2014 Дата пересмотра: 21.12.2015 Отменяет: 01.12.2014 Версия: 1.0 РАЗДЕЛ 1: Идентификация химической продукции и сведения о производителе и/или пос...»








 
2017 www.net.knigi-x.ru - «Бесплатная электронная библиотека - электронные матриалы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.