Период Пизано
В 1960 году Дональд Уолл из IBM, Phite Plains, Нью-Йорк, доказал, что множество чисел Фибоначчи, взятое по модулю m , является периодичным.
Рассмотрим первые десять чисел Фибоначчи, и их остатки при делении на 11 :
Последовательность остатков повторяется. Пусть k(m) — длина повторяющейся подпоследовательности, тогда k(11) = 10 .
Уолл доказал несколько свойств, некоторые из которых будут Вам интересны:
- Если m > 2 , то k(m) четно.
- Для любого четного n > 2 существует такое m , что k(m) = n .
- k(m) ≤ m2 — 1
- k(2n) ≤ 3 * 2(n-1)
- k(5n) = 4 * 5n
- k(2 * 5n) = 6n
- Если n > 2 , то k(10n) = 15 * 10(n-1)
Напишите программу, которая вычислит длину повторяющейся подпоследовательности k(m) для различных значений модуля m .
Входные данные
Первая строка содержит количество тестов p ( 1 ≤ p ≤ 1000 ). Данные каждого теста расположены на одной строке и содержат два целых числа n и m , где n — номер теста, а m ( 2 ≤ m ≤ 1000000 ) — значение модуля.
Выходные данные
Для каждого теста вывести в отдельной строке номер теста n , пробел, и длину повторяющейся подпоследовательности для m — значение k(m) .
Пример
Входные данные #1 content_copy
5 1 4 2 5 3 11 4 123456 5 987654
Выходные данные #1 content_copy
1 6 2 20 3 10 4 15456 5 332808
Kazanzhy blog
Часть своего свободного времени я уделяю обучению на платформах для дистанционного обучения и прохожу разные курсы. Больше всего мне нравится Stepik.org.
На этом ресурсе можно найти много курсов для «чайников», где понятным языком объясняются разные аспекты IT (и не только).
После освоения основ язык программирования Python, я пошел дальше и поступил на курс «Алгоритмы и структуры данных» от Computer Science Center (Сейчас разделен на два: Алгоритмы: теория и практика. Методы и Алгоритмы: теория и практика. Структуры данных).
Трудности настигли на первом же уроке — «Числа Фибоначчи».
Для справки:
Числа Фибоначчи — это последовательность, в которой первые два числа равны либо 1 и 1, либо 0 и 1, а каждое последующее число равно сумме двух предыдущих чисел. Числа Фибоначчи на OEIS.
Последняя задача урока — задача на программирование повышенной сложности:
Даны целые числа n и m (1 n <= 1018, 2 m n-го числа Фибоначчи на m.
Memory Limit — 256 Mb
Time Limit — 5 seconds.
Как можно догадаться, ограничения по памяти и времени не позволят наивному алгоритму пройти решение.
Немного погуглив, я наткнулся на обсуждение такого термина как «период Пизано».
Оказывается, что если составить последовательность из остатков деления чисел Фибоначчи на какое-ибо число, то остатки будут чередоваться с определенной периодичностью.
Возьмем первые тринадцать чисел — 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 — и найдем остатки деления на 4 — 1, 1, 2, 3, 1, 0, 1, 1, 2, 3, 1, 0, 1 .
Остатки чередуются с периодичностью каждые 6 членов, таким образом период Пизано для делителя 4, равен 6.
Для решения задачи, описанной ранее, прежде всего необходимо определить тот самый период, с указанным делителем.
Для этого в отдельный массив записываем остатки от деления чисел Фибоначчи на m до тех пор, пока не получим две единички идущие подряд.
Далее, для удобства, удаляем два последних числа массива.
После этого нужно найти x — остаток от деления n на период Пизано.
Ну и наконец, программа должны вывести число из массива с остатками с номером x.
Это и будет ответом задачи.
Еще информации на Вики и в OEIS.
На этом все )
периодичность — Период Пизано
Предложить алгоритм вычисления N числа Фибоначчи по модулю M. Как я понимаю — задача сводиться к вычислению периода Пизано и делал я это следующим образом : Идем по порядку от 0 до N числа Фибоначчи и берем i число по модулю M до того момента как не встретим подряд такие два остатка равные 0 и 1 ( исходя из того, что каждый новый период начинается с 0 и 1). Тогда, получившая последовательность и будет периодом. Мы будем знать её длину и тогда поделим N по модулю длины периода и уже понятно как вычислить ответ. Но, сложность возникает с тем, что данный метод вычисления периода — медленный. Если какой то способ более быстро вычислять период Пизано, то есть не за «тупой» проход.
задан 9 Апр ’16 20:19
garex
267 ● 2 ● 22
21% принятых
1 ответ
Мне кажется, эти вещи где-то должны быть изложены. Правда, ссылки придётся искать.
Прежде всего, если $%M$% разложено на простые множители, то достаточно найти периоды по модулю чисел $%p^k$%, входящих в каноническое разложение, то есть для степеней простых, а потом рассмотреть их НОК. При этом длина такого периода будет равна наименьшему натуральному $%N$%, для которого многочлен $%x^N-1$% делится на $%x^2-x-1$% с коэффициентами по модулю $%p^k$%.
Если я правильно понимаю, то в конечном счёте всё сводится к случаю простых $%p$%. А именно, если мы знаем период по модулю $%p$%, то далее длины периодов домножаются каждый раз на число $%p$%. Скорее всего, последнее доказывается как-то не слишком сложно.
Что касается простых чисел, то здесь длина наименьшего периода является делителем числа $%p^2-1$%. Исключением является случай $%p=5$% (поскольку он равен дискриминанту квадратного уравнения). Но для этого случая известен готовый ответ; его нетрудно найти в Google. Чтобы быстрее выяснить, какова длина периода на самом деле, не считая всё подряд, нам нужно знать разложение числа $%(p-1)(p+1)$% на простые множители. Для каждого простого делителя $%q$% такого числа, нам надо проверить все числа вида $%\fracq$% на предмет того, не являются ли они периодами. Если не являются, что $%p^2-1$% будет наименьшим периодом.
Предположим теперь, что мы нашли какое-то простое $%q$%, для которого $%\fracq$% является периодом. Тогда уже это число надо делить поочерёдно на его простые делители, и проверять, можем ли мы длину периода уменьшить.
В итоге задача сводится к проверке того, не будет ли периодом некоторое заданное число $%m$%, которое мы проверяем. Это равносильно тому, делится ли $%x^m-1$% на $%x^2-x-1$% над полем $%\mathbb Z_p$%. Если число $%m$% большое, то нам не нужно проверять это $%m$% шагов, а достаточно сделать порядка $%O(\log m)$% шагов, применяя так называемый алгоритм быстрого возведения в степень.
Конкретно, мы вычисляем остатки от деления на $%x^2-x-1$% многочленов $%x^2$%, $%x^4$%, $%x^8$%, . и так далее. Предыдущий известный нам остаток (линейный многочлен) мы возводим в квадрат, и приводим его по модулю $%x^2-x-1$% (то есть просто заменяем $%x^2$% на $%x+1$%), а также по модулю $%p$%. Теперь, зная представление числа $%m$% в двоичной системе, мы последовательно перемножаем найденные остатки, каждый раз приводя произведение, и проверяем, получится ли в конце $%1$%.
Например, если $%m=123=64+32+16+8+2+1$%, то надо будет перемножить остатки для $%x^$%, $%x^$%, . и так далее.
Можно проверить, как это дело работает, например, для $%p=13$%. Там должен получиться минимальный период, равный $%28$%. К нему надо постепенно прийти от числа $%p^2-1=168$%.
отвечен 10 Апр ’16 16:23
falcao
299k ● 9 ● 38 ● 53
# Поиск периода Пизано
Даны целые числа [latex]1 \leq n \leq 10^[/latex] и [latex]2 \leq m \leq 10^5[/latex], необходимо найти остаток от деления n-го числа Фибоначчи на m.
# Решение
Последовательность остатков при делении чисел Фибоначчи на натуральное число периодична. Период Пизано
open in new window — это длина периода этой последовательности.
Для нахождения остатка от деления n-го числа Фибоначчи на натуральное число m достаточно найти все числа периода Пизано для данного m, затем найти остаток от деления n на длину периода, и взять число из периода Пизано под этим номером.
Саму последовательность Фибоначчи можно не вычислять, для нахождения периода использовать только остатки.
Первые числа в периоде Пизано — 0 и 1. Длина периода не больше m * 6 (доказательство этого не нашёл).
n, m = [int(x) for x in input().split()]
def find_pisano(n, m): pisano = [] pisano.append(0)
# при делении на 1 остаток будет всегда 0 if m == 1: return pisano pisano.append(1) # при m > 0 остатки от деления первого и второго числа Фибоначчи # всегда 0 и 1 if n pisano = find_pisano(n, m) print(pisano) print(pisano[n % len(pisano)])