Условие
Последовательность задана F₁=F₂=1, Fₙ₊₂=Fₙ₊₁+Fₙ. Рассматриваются остатки modulo 5. а) Найдите наименьший период пар соседних остатков. б) Найдите первый n, для которого Fₙ делится на 5. в) Найдите сумму всех n≤60, для которых Fₙ делится на 5.
Подсказка
Шаг 1 для варианта 10: Состояние рекурсии полностью задаётся упорядоченной парой соседних остатков; выписывайте пары до повторения (1,1).
Шаг 2 для варианта 10: После нахождения первого нулевого остатка проверьте его период повторения и просуммируйте соответствующие индексы.
Показать ответ
а) 20; б) 5; в) 390
Пошаговое решение
- Намечаем ход решения
Состояние рекурсии полностью задаётся упорядоченной парой соседних остатков; выписывайте пары до повторения (1,1). После нахождения первого нулевого остатка проверьте его период повторения и просуммируйте соответствующие индексы.
- Получаем следующий результат
Последовательно вычисляя остатки, до возврата пары (1,1) получаем цикл длины 20: 1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, 3, 2, 0, 2, 2, 4, 1, 0.
- Выполняем преобразование
Ни одна более ранняя пара не равна (1,1), поэтому период минимален.
- Выполняем преобразование
Первый нулевой остаток стоит на месте 5; из цикла видно, что нули повторяются через 5 индексов.
- Выполняем преобразование
До 60 это индексы 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60.
- Выполняем преобразование
Их сумма равна 390.
Ответ: а) 20; б) 5; в) 390