Нечётные числа

Что же я там считаю такое, что мне понадобились 128-битные числа? Сейчас расскажу.

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

Формулировка у неё была очень простая.

Дано множество X. Единица принадлежит X. Если 3×x принадлежит X, то и x принадлежит X. Если x принадлежит X, то и 2×x + 1 принадлежит X. При этом x — натуральное, разумеется.

Требуется доказать, что таким образом можно получить множество всех натуральных нечётных чисел. Авторы статьи, кстати, были убеждены, что найти доказательство у читателей не получится.

Упомянутый коллега у себя в университете при помощи студента, Фортрана и Пролога пытался проверить эту теорему по следующему алгоритму.

Берём число, например, «9». Оно могло быть получено, согласно перечисленным утверждениям, двумя путями: либо какое-то другое нечётное число умножили на два и прибавили один, либо умножили на три. Поэтому надо проверить по формулам откуда мы могли попасть в это число, отсекая циклы и останавливаясь, когда мы попадаем в чётные числа.

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

В общем, я решил с этой задачкой побаловаться.

Для начала написал программу, которая вычисляет эти числа перебором. Начинаем, понятное дело, с единицы, следующее число получаем по формуле 2×x + 1, потом, пока число делится на три, делим и выводим эти числа, считая для каждого ещё и  2×x + 1 и так далее. Кроме того, пришлось ещё запоминать все найденные числа, чтобы избегать циклов.

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