Головоломка 16.

Единственное, что до сих пор еще не сказано — это способ определять, становится» ли последовательность периодической. Метод Полларда был основан на первой стратегии. Мы выясняем, существует ли ai с a2i = ai. Но вычисление f(x) = x2– 1 по модулю n — дорогое вычисление. Брепт улучшил этот метод, предложив использовать вторую стратегию.

Головоломка 17.

Эта программа основана на следующих результатах:

если b нечетно, n четно, то n делится на b тогда и только тогда, когда n/2 делится на b;

нечетное n делится на b тогда и только тогда, когда n– b делится на b. Но n– b четно.

Для n = 277– 3 и b = 7 вы получаете:

Число n нечетно. Рассматриваем n– b = 277– 10. Оно делится на 2: получаем 276– 5.

Это число нечетно: (276– 5) - 7 = 276– 12.

Делим на 4: 274 — 3.

Получаем ту же самую задачу, в которой показатель уменьшен на 3. Так как 77 = 3*25 + 2, то мы таким образом доходим до 22 — 3 = 1, которое не делится на 3. Вряд ли вас слишком утомит доказательство того, что 2n– 3 никогда не делится на 7…

Головоломка 18.

Я не в состоянии рассказать вам, как я получил эту программу, это — очень долгая история, связанная с разложением целых чисел на множители. Может быть, когда-нибудь я ее и опубликую. Следовательно, будем разбираться в том, что нам дано — в тексте программы.

Начнем с нечетного n. В соответствии с инициализацией программы n = 4p– 1, где p четно. В противном случае уже последует ответ «НЕТ». Следовательно, рассмотрите нечетное n, являющееся полным квадратом и, следовательно, квадратом нечетного числа 2k + 1;

(2k + 1)2 = 4k2 + 4k + 1 = 4k (k + 1) + 1.

Так как k (k + 1) — произведение двух последовательных целых чисел, и из двух последовательных целых чисел всегда есть хотя бы одно четное число, получаем простой, но интересный результат: любой квадрат нечетного числа сравним с 1 по модулю 8. Таким-образом, при n отличном от 1 по модулю 8 инициализирующая часть программы выводит, что n не является точным квадратом.

Посмотрим теперь, что происходит внутри цикла. Делим p на 2, и если результат четен, мы удовлетворяемся тем, что умножаем a на 2. При этом действии произведение a*p остается постоянным. Поэтому кажется вероятным, что в цикле существует инвариантная величина, запись которой содержит a*p в предположении, что p четно.

Если после деления p на 2 результат оказывается нечетным, то мы вычитаем из этого результата a/2 + b. Обозначим новые значения a, b, p через а', b', p' соответственно:

а' = 2*а, p' = p/2 - а/2 - b, b' = a + b.

Для этих значений получаем:

a'*p' = a*p– a2– 2a*b = а*р– (а + b)2 + b2 = а*р– b'2 + b2.

Это, наконец, дает

а'*p' + b'2 = а*р + b2.

Инвариантной величиной цикла оказывается, таким образом, сумма ар + b2, причем p остается четным. Это обеспечивается тем, что в случаях, когда p/2 нечетно, мы вычитаем нечетные b из нечетного p/2. Что касается b, то он нечетен потому, что он начинается со значения 1 и к нему прибавляются только четные значения а.