Пешеход, делающий три шага вперёд и два назад, хотя и не быстро, но всё же доберётся до цели. А вот в одной любопытной нерешённой задаче из теории чисел утверждается, что при таком передвижении достижение цели весьма сомнительно. Задача формулируется так. Возьмём произвольное целое число N больше нуля (любое натуральное число). Если оно нечётное, умножим его на 3 и прибавим 1, т.е. заменим N на 3N+1. Если же оно чётное, разделим на 2, т.е. заменим N на на N/2. В любом случае получаем новое значение N, с которым повторяем описанную операцию. Появится ли после многократного повторения указанных действий тенденция к увеличению чисел или, быть может, к уменьшению? Каким будет процесс: расходящимся или он будет сходиться к некому значению? Долго ли дожидаться числа, которое для этого процесса окажется «фатальным»?

Если задано конкретное N, то для ответа на поставленные вопросы достаточно обычной арифметики. Например, начав с нечётного числа 27, следующим получим значение (3×27)+1=82, затем 41, а потом 124. Очевидно, что в последовательности будет много «взлётов» и «падений»: взлетов, когда N нечётное, и падений, когда оно чётное. Читателю предлагается самому продолжить вычисление и убедиться в справедливости сказанного.

Трудность задачи заключается не в выписывании последовательности для данного N, а в нахождении общего решения, которое годилось бы для всех исходных значений N. Такое общее решение пока не получено. Было испробовано огромное количество чисел, и все они вели себя одинаково, но ещё никто не смог доказать, что так же будет с любым целым числом. Из нерешённых задач теории чисел — эта едва ли самая важная, но она одна из тех, что вызывают сильную досаду. И описание вычислительной процедуры, и её выполнение чрезвычайно просты, но понять, к чему она может привести, невероятно трудно.

На примере этой задачи особенно хорошо видны как польза компьютера при вычислениях, так и ограниченность его возможностей. С небольшими целыми числами можно справиться самим, а далее для вычислений понадобится механический помощник. Им может быть любая машина, даже небольшой программируемый калькулятор. В области же очень больших чисел такая работа под силу только самым мощным ЭВМ. Когда же ставятся более глубокие вопросы, уже не поможет никакой компьютер. Основное назначение ЭВМ — быть подспорьем в математическом эксперименте: строить примеры и контрпримеры. Для описания же закона, по которому N изменяет свои значения, нужна не числодробилка, а скорее механический «доказыватель теорем».

Если к произвольному целому числу N многократно применять описанные преобразования, то какого результата следует ожидать? На этот счёт есть три интуитивные гипотезы.

В первой гипотезе рассуждаем так. Имеется равное количество чётных и нечётных чисел, так что в любой длинной последовательности вычислений чётные и нечётные N будут появляться одинаково часто. Нечётное N увеличивается втрое (чуть больше), а чётное уменьшается всего лишь вдвое. Следовательно, по мере роста числа итераций значение N будет бесконечно возрастать. За каждую итерацию N будет в среднем увеличиваться на (3N+1)/2. Для больших значений N это, в сущности, равно 3N/2.

Вторая гипотеза основана на тезисе «Чем выше заберёшься, тем ниже скатишься». Справедливость этой мысли подкрепляется тем реальным фактом, что стóит в вычислениях получить точную степень двойки, как последовательность неудержимо скатится к 1. (При делении на 2 числá, представляющего собой 2 в любой степени, кроме самой двойки, постоянно будет получаться всё меньшее и меньшее чётное число.) Среди бесконечного счётного множества целых чисел существует бесконечно много степеней двойки, так что при достаточно долгом вычислении обязательно получится одна из них. В процессе вычислений можно получить сколь угодно большое число N, но крах его неизбежен.

Третья гипотеза по форме схожа со второй, но приводит к иному выводу. Замечено, что как только вычисления меняют направление, скажем после ряда чётных чисел появляется нечётное, мы вновь возвращаемся в ту же область, в которой были раньше. В самом деле, получая то бóльшие, то меньшие числа, мы можем сколь угодно часто возвращаться в некую конечную область. Можно ожидать, что рано или поздно результат вычислений повторится, и, как только это произойдёт, всё дальнейшее предрешено. Образуется замкнутый цикл, из которого уже никогда не выйти. Это объясняется тем, что выбор каждого следующего шага происходит по вполне определённому правилу.

К рассмотренным гипотезам не следует относиться слишком серьёзно: они не могут быть все справедливыми. Какие-то из их посылок определённо спорны. В частности, во всех трёх гипотезах привлекаются вероятностные соображения, хотя последовательности чисел порождаются по некоему правилу, а не случайным образом. Далее, бесконечные величины играют существенную роль при любом анализе этой задачи, а, когда имеешь дело с бесконечностью, здравый смысл редко бывает хорошим советчиком.

Делая эти оговорки, должен тем не менее отметить, что все три гипотезы считаю в высшей степени правдоподобными. Взвешивая каждую из них, я думаю, что не может быть сомнений в её справедливости, и в то же время другие гипотезы мне кажутся не менее убедительными. Что же по этому поводу говорит математический эксперимент?

Начнём вычисления с 1. Это — нечётное число, поэтому, следуя условиям задачи, умножим его на 3 и прибавим 1. Полученное в результате 4 — чётное число, так что делим его на 2 и снова получаем чётное число. Поделив ещё раз на 2, вновь возвращаемся к 1. Таким образом, результат нашего первого вычисления подтверждает две из рассмотренных выше гипотетических теорий. Гипотеза о крахе больших чисел подтвердилась тем, что после первой же итерации результат оказался степенью 2. Подтверждением гипотезы о зацикливании является получение 1 — числа, с которого мы начали. Замкнутый цикл 4, 2, 1 далее будет беспрестанно повторяться.

Из всех натуральных чисел единица занимает особое положение: это первое число и наименьшее. Таким образом, результат, полученный для N=1, может быть нетипичным: прежде чем делать какие-либо выводы, надо проверить другие числа. «Фатальность» чисел 2 и 4 очевидна из вычисления для N=1, поэтому попробуем начать с 3. Это число нечётное, так что следующим будет (3×3)+1, т.е. 10. Разделив на 2, получаем 5. Умножив теперь на 3 и прибавив 1, получаем 16 — опять степень 2; последовательное деление на 2 даст значения N=8, 4, 2, 1, т.е. мы вновь попадаем в замкнутый цикл 4, 2, 1.

После исследования первых четырёх натуральных чисел вроде бы выявилась определённая тенденция, но всё же оснований для окончательного вывода нет. В проведённых вычислениях нас больше всего интересуют две величины: максимальное из полученных значений N и длина пути, под которой будем понимать общее число итераций, необходимое для достижения 1. Для самой 1 максимальное значение равно 1, а длина пути — нулю. Для 2 максимум равен 2, а длина пути — 1. Для 3 максимумом будет 16, а длиной пути 7. Пример с тройкой говорит о том, что максимум достигается, а число последовательных итераций может быть значительно больше исходного значения N, так что вполне возможно, что для некоторого значения N эта функция окажется вовсе неограниченной.

Снова вернёмся к последовательности, которая порождается начальным значением 27. Как уже было сказано, первые три числа — это 82, 41 и 124, но два деления подряд отбрасывают нас назад, к 31. Можно сказать, что после пяти шагов мы почти не продвинулись вперёд.

Но если вычисления продолжить, метод «три шага вперёд и два назад» приводит к осциллирующей кривой с постоянно возрастающей амплитудой. Новыми пиками будут 142, 214, 322 и 484. В дальнейшем будут и спады (на 19-м шаге значение опустится до 91), но прослеживается общая тенденция к возрастанию. Миновав числа 700, 1186, и 2158, кривая достигнет весьма значительной величины: 9232. Казалось бы, мы на верном пути. Но, увы, этот путь после 111 шагов завершается в 1, так и не поднявшись выше 9232. (Вся последовательность вычислений графически представлена на рисунке.)

Последовательность значений чисел-градин, полученных для N=27

Подобные вычисления проводились с огромным набором целых чисел. Сотрудник Токийского университета Набуо Йонеда исследовал все целые числа до 2⁴⁰, т.е. до 1,1×10¹². Результат во всех случаях был одним и тем же: после конечного числа шагов последовательность навсегда попадала в цикл 4, 2, 1. Из первых 50 целых чисел самая большая длина пути возврата в 1 у числа 27 (впрочем, для 41 и 31 этот путь не намного короче, а по пути достигаются те же самые пики; это должно быть ясно из сказанного выше). Целых чисел, которые порождали бы бесконечную последовательность, уходящую неограниченно вверх, не было найдено, равно как не найдены и другие циклы, кроме 4, 2, 1. И всё же утверждать, что все целые числа ведут себя одинаково, мы не можем, так как этому пока нет теоретического обоснования.

Длины путей (чёрные точки) и максимальные значения (красные точки) для всех целых от 1 до 27

История проблемы «3N+1», как её обычно называют, хоть и довольно туманна, вряд ли уходит в глубь веков. В течение последних примерно 30 лет эта задача время от времени ставилась на факультетах математики и кибернетики различных университетов. Она появлялась и исчезала так же непредсказуемо, как непредсказуемо и поведение чисел, получаемых в процессе решения рассматриваемой задачи. Сотрудник фирмы Bell Laboratories Джефри Лагариас, недавно изучавший истоки этой задачи и попытки её решения, отметил, что она, по-видимому, открывалась не однажды. В 1930 году Лотар Коллатц, ещё будучи студентом Гамбургского университета, исследовал класс задач, включающий в себя и проблему «3N+1», но результаты его исследований были опубликованы лишь много лет спустя. Английский математик Б. Туэйтс открыл эту задачу независимо от других в 1952 году, а несколькими годами позже её снова сформулировал Р. В. Эндри из Оклахомского университета в Нормане.

Лагариас ссылается примерно на 20 научных статей по проблеме «3N+1» и её обобщениям; большинство из них было опубликовано в течение последнего десятилетия, но задолго до этого она уже передавалась изустно. Коллега Коллатца Г. Хассе в 50-х годах ввёл её в Сиракузском университете, С. Улам — в научной лаборатории Лос-Аламоса и, кажется, ещё где-то. С. Какутани, впервые услышавший о проблеме «3N+1» в 1960 году, сообщил Лагариасу: «Целый месяц весь Йельский университет безрезультатно трудился над этой задачей. Такая же участь постигла исследователей Чикагского университета, когда я им сообщил о ней. Ходила шутка, что эта задача использовалась для заговора, имеющего целью снизить интенсивность математических исследований в США».

Группой исследователей из Лаборатории искусственного интеллекта Массачусетского технологического института в начале 70-х годов была предпринята ещё одна длительная атака на эту задачу. Здесь основной упор делался на вычислительные методы, использующие ЭВМ. Во внутреннем (и неопубликованном) отчёте этой группы, названном HAKMEM (сокращение от "hackers' memorandum" — записки работяг), проблема значилась под номером 133.

Постоянно кочуя, задача обрастала множеством имён. Название «проблема "3N+1"», мне кажется не очень подходящим, поскольку освещает лишь одну половину процедуры, оставляя вторую в тени. Среди всевозможных вариантов её названия нашёлся один, точнее других отражающий процесс порождения чисел из исходного: «числа-градины». Графически представленная последовательность чисел, получаемых при вычислении, очень похожа на траекторию градины в грозовой туче, поднимающейся в воздушных потоках и затем падающей под силой собственной тяжести.

На языке высокого уровня, скажем на Бейсике, можно написать программу для вычисления чисел-градин, и займёт она всего лишь несколько строк. В самом деле, основной алгоритм формулируется одним предложением. На Бейсике оно имеет вид:

IF N MOD 2 = 0 THEN N = N/2 ELSE N = 3*N + 1

Первой здесь записана операция, которую люди (но не машина) выполняют, не прибегая к явным вычислениям: определение чётности (или нечётности) числа N. Компьютер пользуется для этого операцией сравнения по модулю 2, определяющей остаток от деления на 2 числа N. Если остаток равен 0, то выполнится команда, записанная частью предложения, начинающегося с THEN, и N будет присвоено значение N/2; в противном случае выполнится команда, начинающаяся с ELSE, и N станет равным 3N+1.

Такая программа на Бейсике вполне сносно справляется с порождением чисел-градин из нескольких первых сотен чисел. Но если требуются более громоздкие вычисления, процесс невероятно замедляется. В предложении на Бейсике предусмотрено деление (при сравнении по модулю), сравнение и затем либо второе деление, либо умножение на 3 и сложение. Умножение и деление нещадно тратят машинное время, особенно на небольших вычислительных системах. Можно добиться большой экономии, если обращаться непосредственно к центральному процессору на его собственном языке. Это позволит исключить все операции умножения и деления.

Приблизительное представление о такой программе на языке машины даёт рисунок справа. Предполагается, что исходное значение N первоначально находится в регистре AX, который служит ещё и «сумматором», где выполняются арифметические операции. В нём в двоичной системе записано число 27, с которого начинается вычисление.

На первом шаге исходное число в двоичном коде переписывается в другой регистр, обозначенный на схеме BX. За счёт особых свойств двоичного представления чисел операция деления в данном случае может быть исключена: сдвиг двоичного числа вправо на один знак эквивалентен делению на 2 точно так же, как сдвиг десятичного числа вправо на одну позицию соответствует делению на 10. В процессе сдвига самый правый разряд (разряд единиц) сохраняется в ячейке памяти размером в 1 бит, которая называется разрядом переноса. Проверяя разряд переноса, можно определить чётность числа, поскольку в двоичной системе каждое чётное число имеет на конце нуль, а нечётное — единицу.

Если N чётное, то вычисления на этом этапе закончены. В регистре AX после сдвига вправо окажется частное N/2. В том случае, однако, когда N нечётное, вычисления необходимо продолжить. Прежде всего восстанавливается исходное значение N обращением к регистру BX. Далее, вместо умножения на 3 это значение дважды прибавляется. Здесь потребуются две машинные команды вместо одной, но всё равно это значительно быстрее. Последний шаг — увеличение на 1 числа в AX. В одном микропроцессоре с таким набором команд вся процедура занимает 20 тактов при нечётном N и 18 тактов при чётном N. При тактовой частоте примерно 5 мГц такой фрагмент программы за одну секунду выполняется примерно 250 000 раз. (Можно сэкономить даже немного больше машинных тактов, но тогда программа будет более сложной.) Аналогичный алгоритм, но использующий команды умножения и деления, занимает 175 тактов для чётного N и 286 тактов — для нечётного.

Из рисунка видно, что регистры имеют 8 разрядов и, следовательно, в них нельзя поместить число больше чем 2⁸, т.е. больше 256. В основном микропроцессоры имеют размер регистров 16 бит, и, следовательно, в них можно записывать числа до 65 536. Но даже такой диапазон весьма ограничивает нас, поскольку программа, использующая 16-разрядную арифметику, не может оперировать с числами-градинами больше 702. Чтобы расширить наши возможности, нужна арифметика с повышенной точностью, в которой число располагается в нескольких регистрах или ячейках памяти. При точности в 32 бит можно оперировать числами почти до 4·10⁹, а при 64 бит предел равен 10¹⁹. К сожалению, при каждом увеличении точности в той же мере снижается скорость.

Алгоритм получения одного значения N — всего лишь фрагмент рабочей программы. В ней, кроме того, должна быть предусмотрена возможность ввода в машину значений и вывода результатов. Реальные же программы для исследования поведения чисел-градин должны делать ещё больше. Например, следует предусмотреть возможность целиком выпечатывать последовательности чисел, получающиеся из данного начального значения, или составлять таблицу максимальных значений и длин пути для каждого из целых чисел. Другая программа могла бы предназначаться для поиска целых чисел, при которых последовательно удлиняется путь и увеличивается максимальное значение.

Разновидности формулы 3N+1, в которых используются другие коэффициенты и постоянные, также плохо поддаются исследованию. У. Госпер и Р. Шоппель, когда они ещё входили в группу HAKMEM, исследовали проблему «3N–1» и показали, что она эквивалентна проблеме «3N+1» с отрицательными значениями N. Все выбираемые ими числа приводили к одному из трёх замкнутых циклов: самый длинный из них начинается при N=17 и состоит из 18 шагов.

Программу, позволяющую лишь выявить числа, которые не попадают в цикл 4, 2, 1, можно значительно упростить. Если числа проверять подряд, начиная с 1, то в изучении нуждаются лишь нечётные числа. Любое чётное число сразу будет уменьшено вдвое, и, следовательно, путь, который должно породить полученное число, окажется уже изученным раньше. По тем же причинам нет смысла прослеживать весь путь до 1: как только значение N опускается ниже исходного, дальнейшее исследование можно прекратить. Работающий ныне в Бостонском университете бывший член группы HAKMEM У. Хеннеман предложил ещё более эффективные правила для сужения области исследования.

После всего, что было сказано, по-видимому, нет смысла продолжать поиски числа, которое вело бы себя как-то иначе. Но даже если такое число никогда не будет найдено, сам факт существования чисел-градин ставит немало любопытных вопросов.

Возможно, самые интригующие свойства таких чисел — это выраженный характер распределения максимальных значений и длин пути. Если такое небольшое число, как 27, удерживается «в подвешенном состоянии» в течение 111 шагов и достигает максимума 9232, то можно было бы ожидать, что длина пути и максимальные значения растут так же быстро, как и N. В действительности же длины пути растут крайне медленно; рост максимальных значений более быстрый, но тоже весьма неупорядочен.

Среди первой сотни целых чисел самый длинный путь равен 118 шагам (N=97); из первых 100 000 чисел самый длинный путь равен лишь 350 шагам (N=77 031). Таким образом, при увеличении N в 1000 раз длина пути увеличивается только втрое. Здесь, по-видимому, имеет место логарифмическая зависимость. Что же касается максимального значения, то рекордная величина 9232, достигамая числом (N=27, была побита лишь числом (N=255: его максимум равняется 13 120. Другие из зарегистрированных максимумов распределялись самым беспорядочным образом. Градина 77 671 побила все рекорды, достигнув 1 570 824 736.

Легко видеть, что максимальные значения, получаемые при вычислении чисел-градин, неизменно чётные. Можно также доказать, что лишь нечётное N способно установить новый рекорд максимального значения (за исключением числа 2). Для чисел, устанавливающих новые рекорды длины пути, мне неизвестны теоретические аргументы ни в пользу их чётности, ни в пользу нечётности. Однако среди первых 100 000 рекордные длины пути достигались почти исключительно нечётными числами; среди рекордсменов оказались лишь три чётных числа — 6, 18 и 54 (опять не считая 2).

Полученная на ЭВМ распечатка длин пути и максимумов для некоторой области целых чисел представляет собой удручающую смесь закономерности и беспорядка. Последовательность безусловно не случайна, но ей не удаётся дать никакого толкования. Например, некоторые максимальные значения повторяются чаще, чем другие, причём появление некоторых максимумов настолько часто, что их нельзя описать каким-либо статистическим законом. Выдающийся в этом смысле пример представляет максимум 9232, который ранее других чисел достигается числом 27. Среди первых 1000 целых более 350 достигают того же максимума. Порождающие его числа, однако, не имеют никаких явных общих черт.

Распределение длины пути столь же хаотично. Можно породить любую из возможных длин пути (последовательностью точных степеней двойки), но и в этом случае некоторые числа будут появляться чаще других. Кроме того, и длины пути, и максимумы проявляют чёткую тенденцию к группированию в кластеры. Ф. Грюнберг из Калифорнийского университета в Нотридже в 1976 году опубликовал перечень таких кластеров. Самый обширный из них представлял собой цепочку из 52 целых чисел, которые проходили одинаково длинный путь. Возникает вопрос: могут ли одинаковые максимумы и одинаковые длины пути достигаться двумя последовательными числами? Ответ на этот вопрос можно дать в алгебраической форме, но если читатель предпочитает демонстрацию на примерах с числами, ему следует рассмотреть последовательности для всех N от 386 до 391.

Один из подходов, позволяющих пролить свет на задачу о градинах, состоит в обратной её постановке. Предположим, что все положительные целые числа действительно обязательно попадут в цикл 4, 2, 1. Тогда они должны образовать неразрывную цепь, связывающую всё бесконечное счётное множество целых чисел с циклом в основании этой цепи. Поэтому возможно и обращение преобразования над числами-градинами: начиная с 1, применяем преобразование, как бы пятясь назад, для получения больших чисел. Если какое-либо число таким способом получить не удастся, оно не может достичь единицы.

Этот метод прекрасно бы подошёл для получения общего решения задачи о градинах, если бы только его можно было довести до конца. Оказывается, процедура не столь прямолинейна, как кажется. Обычная функция преобразования градин однозначна: у любого значения N в любой точке вычислений только один преемник. Если, например, N=40, то следующим (порождённым им) числом может быть лишь 20. Когда же мы проходим путь в обратном направлении, возникает неоднозначность. Относительно числа 20 понятно, что оно могло получиться из 40, которое, следовательно, и должно теперь идти за ним. Но после числа 40 может получиться либо 80, либо 13: поток растекается на два рукава, каждый из которых нужно исследовать. Разветвления происходят во всех точках вида 6K+4, где K — любое неотрицательное целое, включая нуль.

Дерево, порождённое обратной функцией преобразования чисел-градин

Такого рода разветвляющуюся систему можно проследить только до определённого уровня. Движемся по отдельной ветви до некоторого наперёд заданного предела и затем переключаем внимание на другую ветвь. При пределе 100 надо будет изучить 13 ветвей, причём в этой числовой системе ручейков и протоков между собой связаны 49 чисел. Если предел равен 1000, то ветвей будет 84, а чисел 340. Предел 10 000 даёт 1065 ветвей, которые объединяют 4235 чисел. Заметим, что больше половины чисел провалилось между ветвями потока. При возрастании предела растёт количество включаемых чисел, но теряется ещё больше. Если бы можно было изучить эту разветвляющуюся систему до какого угодно уровня, то были бы охвачены абсолютно все числа? Этот важный вопрос всё ещё остаётся без ответа.