На этом уровне можно поверить, что появляется возвратное соотношение: во второй последовательности нет четных чисел, в третьей — нет кратных трем. Образуем следующую: 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 дает (3p + 1)/2, которое можно еще переписать в виде
3(p + 1)/2 − 1,
что дает правило: добавить 1,
разделить на 2 и умножить на 3,
уменьшить на 1.
Предположим, что результат нечетен. За операцией «уменьшить на 1» сраву же следует операция «добавить 1», и в результате этих двух операций ничто не меняется. Отсюда следует новое правило:
добавить 1,
пока результат четен, делить его на 2 и умножать его на 3,
уменьшить на 1,
делить на 2, пока это возможно.
Составьте по этому правилу программу и заставьте ее перечислять все величины, полученные таким образом (все они будут нечетны. Заметьте, что только первое число в ряду может оказаться кратным трем).
Если вы замените 3 на m, то второе правило изменяется: пока результат четен, делить его на 2 и умножать его на m.
Вернемся к случаю числа 3. Наше правило можно переписать следующим образом: пусть k — некоторое нечетное число; тогда 2pk − 1 дает (3pk − 1)/2q.
Назовем эту операцию переходом p, q.
Можете ли вы показать, что:
если n = 2 по модулю 3, то элемент, следующий за n, равен некоторому элементу, следующему за (2n − 1)/3;
если n дает некоторое n при переходе p, q, где q > 1, то число (n − 1)/2 порождает ту же последовательность, что и n, за исключением, быть может, нескольких первых членов.
Любое число вида n = 4k + 1 имеет непосредственно следующее n' < n.
Для того чтобы n допускало переход p, 1, необходимо и достаточно, чтобы n имело вид n = k2p − 1, где
k = 1 по модулю 4, если p нечетно,
k = 3 по модулю 4, если p четно.
Если вы хотите проверить о помощью программы, что это свойство выполняется для любого нечетного n в данном интервале от 3 до n, вы можете пробежать все нечетные числа в возрастающем порядке и проверить, что для каждого ив них это верно. Но вы можете сначала вычеркнуть из списка все нечетные числа, о которых вы знаете, что их поведение сводится к поведению последовательности, относящейся к меньшему нечетному числу, поскольку список нечетных чисел пробегается в возрастающем порядке, и этот случай уже был неучен. Таким образом, остается не больше чисел, чем уже было отмечено.
Но построить список априори, без вычеркиваний в более широком списке, так же трудно, как построить последовательность счастливых чисел…
Затем можно пытаться сделать еще один шаг: для любого не вычеркнутого n вычислить первый следующий за ним элемент. Он больше n (в противном случае n был бы вычеркнут). Если он содержится в интервале от 3 до N, то мы ничего не делаем (этот случай будет изучен ниже). Если же он больше N, то мы помещаем его в резерв. Таким образом, мы получим некоторый список чисел, больших N. Если для каждого числа из этого списка возвратная последовательность достигает 1, то мы сможем доказать, что это свойство выполняется для всех чисел, меньших N, и еще для некоторых других.
Конечно, это не доказывает общей теоремы: для любого n предложенная последовательность достигает 1. Но нужно присоединить к делу новую форму рассуждения, которая потребует серьезных размышлений и надежных логических оснований для того, чтобы оказалось возможным поправить дело…