адача 52. При любом ли натуральном n рекурсивная функция

                                  (25)

равна 1?

Решение. Хотя данная строка и начата со слова "решение", ответа на поставленный вопрос мы не знаем, и, по-видимому, на сегодняшний день его не знает ни один специалист по теории чисел. Более того, неизвестно, для любого ли n problem(n) вычисляется за конечное число шагов. Рассмотренную задачу называют 3×n+1 проблемой. Мы включили её в список задач для того, чтобы обратить внимание читателя на следующий факт. Достаточно простые с виду рекурсивные определения функций могут таить в себе глубокие проблемы, решения которых лежат совсем не на поверхности. Тем не менее конкретные вычисления problem(n) при разных n приводят к одному и тому же значению, равному 1. Ниже приведена рекурсивная программа для проверки истинности утверждения "problem(n)=1" при значениях n из диапазона k1..k2:

Контрольные примеры:

A.   problem(12345678998765) = 1;                                                                

B.   proverka(100000, 105000) = "=1",     proverka(3300000, 3305000) = "=1".

Приведем еще несколько программ, могущих быть полезными при исследовании проблемы 3×n+1.

Рекурсивная функция seq(m) возвращает "траекторию аргумента m" функции problem(m), то есть последовательность вычисляемых по problem(m) значений, начиная от m и далее:

При вычислениях по этой функции по существу самой проблемы 3×n+1 возможен аварийный останов.

Рекурсивная функция sodd(m) сразу при формировании траекторий производит их "сжатие", удаляя все четные числа. Для осуществления этой операции она обращается к рекурсивной функции O2(m) нахождения максимального нечетного делителя m:

Контрольные примеры:

 seq(99)^T = [99    298    149    448    224    112    56    28    14    7    22    11
                     34    17    52    26    13    40    20    10    5    16    8    4    2    1];

 sodd(99)^T = [99    149    7    11    17    13    5    1].