Конкурсная задача ММ60 (12 баллов)

Триша Тройкин, Петя Пятаков и Сёма Семак пытаются сконструировать собственный генератор псевдослучайных чисел. Для этого они взяли натуральные числа a и m (одни и те же у всех троих) и выстраивают последовательность по правилу:

x_n+1 = x_na (mod m).

Начав с некоторого x₁, Триша посчитал x₂, x₃ и x₄. Но x₄ оказалось равно x₁. Тогда он взял другое (не встречавшееся ранее) число в качестве x₁. Но последовательность опять зациклилась на третьем шаге. Треья попытка привела Тришу к тому же результату.

Петя совершил пять попыток подобрать x₁. Но всякий раз получал новые циклы длины 5. Наиболее упорным оказался Сёма. Он совершил семь попыток. И получил семь циклов длины 7.

При каком наименьшем m могла возникнуть такая ситуация?

Решение

… можно посмотреть здесь.

Ответ: n = 4851

Обсуждение

Оба конкурсанта, приславших свои решения этой задачи, не нашли наименьшего подходящего m. Не смог сделать этого и ведущий Марафона, предложивший задачу. Я ошибочно считал наименьшим m = 6699. Этот же вариант ответа был и у Владислава Франка. И лишь после подведения итогов шестого тура Марафона, в который входила задача № 60, Барух Зив указал мне на мою оплошность.

Приведенное решение не отталкивается напрямую от системы сравнений
xa³ == x (mod m)
ya⁵ == y (mod m)
za⁷ == z (mod m)},
продиктованной ситуацией именно этой задачи, а претендует на некоторую универсальность.
Его очевидным образом можно приспособить для моделирования любых конечных унаров, в том числе, содержащих «хвосты» любой «длины» и «ветвистости». Например, глубина (расстояние до цикла) элемента b в принятых ранее обозначениях определяется как минимум целых неотрицательных h таких, что b_i + ha_i >= m_i для всех i.

Чуть подробнее про общую задачу можно прочитать здесь

Награды

За решение этой задачи Владислав Франк получает 12 призовых баллов. Виктор Филимоненков (найденное им m - существенно больше) получает 10 баллов.

Эстетическая оценка задачи - 4 балла —-