Жак Арсак - Программирование игр и головоломок

3 : 5 7 11 13 17 1923 25 28 31 3537 41 43 47 49

На этом уровне можно поверить, что появляется возвратное соотношение: во второй последовательности нет четных чисел, в третьей — нет кратных трем. Образуем следующую: 25, кратное 5 содержится. Покажем механизм перехода от одной последовательности к другой последовательности

3 : 5 7 11 13 17 19 23 26 29 31 35 37 41 43 47 49

5 : 7 11 13 17 23 25 29 81 87 41 43 47

Если вы все это хорошо поняли, то вы теперь должны суметь обобщить. Обозначим черев g ( i , j ) число, стоящее в последовательности ранга i , которая начинается с g ( i , 0). Число g ( i , 0) = h ( i ) и есть счастливое число ранга i . Если вы можете построить g ( i + 1, j ), исходя ив g ( i , …), то вы должны суметь решить задачу. Само собою разумеется, что таблица чисел g не должна участвовать в программе. Это — только промежуточное средство вычисления…

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

Нужно попытаться сгруппировать эффект нескольких последовательных шагов. Нечетное p дает (3 p + 1)/2, которое можно еще переписать в виде

3( p + 1)/2 − 1,

что дает правило: добавить 1,

разделить на 2 и умножить на 3,

уменьшить на 1.

Предположим, что результат нечетен. За операцией «уменьшить на 1» сраву же следует операция «добавить 1», и в результате этих двух операций ничто не меняется. Отсюда следует новое правило:

добавить 1,

пока результат четен, делить его на 2 и умножать его на 3,

уменьшить на 1,

делить на 2, пока это возможно.

Составьте по этому правилу программу и заставьте ее перечислять все величины, полученные таким образом (все они будут нечетны. Заметьте, что только первое число в ряду может оказаться кратным трем).

Если вы замените 3 на m , то второе правило изменяется: пока результат четен, делить его на 2 и умножать его на m .

Вернемся к случаю числа 3. Наше правило можно переписать следующим образом: пусть k — некоторое нечетное число; тогда 2 pk − 1 дает (3 pk − 1)/2 q .

Назовем эту операцию переходом p , q .

Можете ли вы показать, что:

если n = 2 по модулю 3, то элемент, следующий за n , равен некоторому элементу, следующему за (2 n − 1)/3;

если n дает некоторое n при переходе p , q , где q > 1, то число ( n − 1)/2 порождает ту же последовательность, что и n , за исключением, быть может, нескольких первых членов.

Любое число вида n = 4 k + 1 имеет непосредственно следующее n ' < n .

Для того чтобы n допускало переход p , 1, необходимо и достаточно, чтобы n имело вид n = k 2 p − 1, где

k = 1 по модулю 4, если p нечетно,

k = 3 по модулю 4, если p четно.

Если вы хотите проверить о помощью программы, что это свойство выполняется для любого нечетного n в данном интервале от 3 до n , вы можете пробежать все нечетные числа в возрастающем порядке и проверить, что для каждого ив них это верно. Но вы можете сначала вычеркнуть из списка все нечетные числа, о которых вы знаете, что их поведение сводится к поведению последовательности, относящейся к меньшему нечетному числу, поскольку список нечетных чисел пробегается в возрастающем порядке, и этот случай уже был неучен. Таким образом, остается не больше чисел, чем уже было отмечено.

Но построить список априори, без вычеркиваний в более широком списке, так же трудно, как построить последовательность счастливых чисел…

Затем можно пытаться сделать еще один шаг: для любого не вычеркнутого n вычислить первый следующий за ним элемент. Он больше n (в противном случае n был бы вычеркнут). Если он содержится в интервале от 3 до N , то мы ничего не делаем (этот случай будет изучен ниже). Если же он больше N , то мы помещаем его в резерв. Таким образом, мы получим некоторый список чисел, больших N . Если для каждого числа из этого списка возвратная последовательность достигает 1, то мы сможем доказать, что это свойство выполняется для всех чисел, меньших N , и еще для некоторых других.

Конечно, это не доказывает общей теоремы: для любого n предложенная последовательность достигает 1. Но нужно присоединить к делу новую форму рассуждения, которая потребует серьезных размышлений и надежных логических оснований для того, чтобы оказалось возможным поправить дело…

Вот, наконец, последнее свойство, которое вы должны уметь доказывать: не существует пар p , q , где p и q — натуральные числа, для которых n дает n при переходе p , q . Это не означает, что не существует периодических последовательностей. Про них я сумел доказать только тот факт, что не может иметь места цикл