Последовательность Фибоначчи на остатках от деления #534840

Пусть a[0]=0, a[1]=1 и a[k+2]=(a[k]+a[k+1])%m - остаток от деления на некоторое фиксированное m суммы двух предыдущих членов. 1. Доказать что найдутся такое n>0, что a[n]=0, a[n+1]=1 2. Найти зависимость периода последовательности от m

зачем?

опять ты? мне интересно

1. Легко: n = 3, m = 2 2. период = m^2-1

1. нужно доказать для любого m, а не выбранного Вами 2. неверно при m=4, например

Хотя нет, в 2. ошибся в расчетах, сильно сложно.

в условии не было "Для любого m", там было "найдутся такое n>0"

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

это подразумевается из контекста, ведь для каждого m свой случай не будем спорить: первый пункт нужно доказать для всех m

вообще непонятное поведение длины цикла от m: m n --- 2 3 3 8 4 6 5 20 6 24 7 16 8 12 9 24 10 60 11 10 12 24 13 28 14 48 15 40 16 24 17 36 18 24 19 18 20 60

Нифига себе. Такое наверное не вычислить, только догадаться можно.

Нда... что удалось получить если n=p - простое число: Обозначим h(p) - минимальный индекс в последовательности Фибоначчи для которого F[p] делится на p, тогда 1. h(p)<=p+1 2. длина цикла п(p)=q(p)*h(p), где q(p)=4, если h(p)-нечетное q(p)=1 или 2, если h(p)-четное 3. всего таких циклов (я их назвал "главными" циклами) (p-1)/q(p) но "главными" циклами не все описывается, есть еще другие, вот с ними засада, например циклы для p=11: > 0 > 1 2 3 5 8 2 10 1 0 1 > 2 4 6 10 5 4 9 2 0 2 > 3 6 9 4 2 6 8 3 0 3 > 4 8 1 9 10 8 7 4 0 4 > 5 10 4 3 7 10 6 5 0 5 > 6 1 7 8 4 1 5 6 0 6 > 7 3 10 2 1 3 4 7 0 7 > 8 5 2 7 9 5 3 8 0 8 > 9 7 5 1 6 7 2 9 0 9 > 10 9 8 6 3 9 1 10 0 10 > 5 9 3 1 4 > 9 6 4 10 3 2 5 7 1 8 > 10 7 6 2 8