и разность этих двух чисел равна

999 (a − d) + 90 (b − c).

Числа a, b, c, d были расположены в невозрастающем порядке, и они не все равны между собой, так что a строго больше d и a − d не равно нулю. Все остальное просто.

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

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

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

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

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

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

Для n = 2⁷⁷ − 3 и b = 7 вы получаете:

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

Это число нечетно: (2⁷⁶ − 5) − 7 = 2⁷⁶ − 12.

Делим на 4: 2⁷⁴ — 3.

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

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

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

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

(2k + 1)² = 4k² + 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 − a² − 2a*b = а*р − (а + b)² + b² = а*р − b'² + b².

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

а'*p' + b'² = а*р + b².

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

В начале а = 4, p (целая часть дроби (n − 1)/4) четно, b = 1, так что ар + b² = n.

Наконец, a, начиная с 4, умножается на 2 при каждом прохождении цикла; b начинается с 1, которое меньше соответствующего начального а = 4.

Тогда при переходе от a, b, p к a', b', p' либо

b' = b, а' = 2*а, так что если b < а, то и b' < а';

либо

b' = а + b, а' = 2*а, что также сохраняет справедливость отношения а' < b'.

Следовательно, вот ситуация, которую цикл оставляет инвариантной:

n = а*p + b²;

а — степень двойки,

p четно,

b нечетно, b < а.

Кроме того, мы знаем, что при выходе из цикла p < а.

Если p равно нулю, то n = b². Тогда мы видим, что n — квадрат числа b, которое выводится, и все закончено.

Но n может оказаться полным квадратом и тогда, когда p не нуль. Попробуем рассмотреть все возможные случаи. Положим n = r² (r нечетно). Соотношение

r² = ар + b дает

r² − b² = ар.

Положим r + b = 2u, r − b = 2v (r и b нечетны). Отсюда получаем 4uv = ар.

Поскольку r = u + v, где r нечетно, получаем, что u и v не могут быть числами одинаковой четности, так что одно из них четно, а другое нечетно. Так как а является степенью двойки, то нечетный сомножитель относится к p. Выявим его, полагая р = s2^t, где s нечетно, a t ≥ 1 (p четно).

Напомним, что а = 2^k. В этих обозначениях 4uv = ар = s2^k+t, uv = s2^k+t−2.

Возможные решения для пары u, v имеют вид пар

s'2^k+t-2, s''

где s's" = s.

Покажем сначала, что s" — меньший из этих двух элементов пары. Вследствие t ≥ 1 имеем k − t ≤ k + t − 2.

Вследствие p < а последовательно выводим

s2^t < 2^k,

s's"2^t < 2^k.

s's" < 2^k-t ≤ 2^k+t-2 ≤ s'²2^k+t-2

(потому что s' нечетен и не меньше 1).

Следовательно, нужно взять u = s'2^k+t-2, v = s".

Покажем теперь, что нужно обязательно взять s' =1, s" = s. По выбору u и v

b = 2^k+t−2s' − s" < а = 2^k.

Отсюда получаем:

s" > 2^k+t−2s' − 2^k,

и, так как t ≥ 1:

s" > 2^k−1s' − 2^k,

s = s's" > 2^k−1s'² − 2^ks = 2^k−1s' (s' − 2).