Вычислимое ли?

[vak]

Определим функцию push(n). Для всякого целого положительного аргумента n функция выдаёт целочисленный результат.

Разложим число n на множители и представим как:

n = 2^a * 3^b * ... * P^q

где 2, 3, ... P - последовательные простые числа.

Тогда результат функции push будет равен:

push(n) = 3^a * 5^b * ... * Q^q

где 3, 5, ... Q - последовательные простые числа.

Например:

push(1) = 1
push(2) = 3
push(3) = 5
push(4) = 9
push(5) = 7
push(6) = 15
push(7) = 11
push(8) = 27
push(9) = 25

Задачка-челлендж для пытливых: реализовать функцию push на машине Фрактран. Или на любой другой машине Тьюринга или Чёрча. Для любого положительного аргумента. В виде программы конечного размера. Есть у меня сомнения, что это возможно.

Почему называется push? В машине Фрактран её регистр рассматривается как последовательность значений [a, b, ..., q]. Последовательность конечная, но неограниченная по длине. Можно рассматривать её как стек. Функция push вталкивает значение 0 на верхушку этого стека:

[a, b, ..., q] ⟶ [0, a, b, ..., q]

Программа фактически должна реализовать "закапывание на бесконечности".

Comments

[juan_gandhi]

Да, логично.

[spamsink]

Задача, в сущности, сводится к нахождению простого числа, следующего за данным. Дальнейшее тривиально.

Раз на Фрактране можно написать универсальную машину, позволяющую представлять произвольные дроби с любыми простыми множителями в составе, следовательно, можно написать и машину, которая динамически модифицирует интерпретируемую машину, добавляя в нее на ходу новые дроби с новыми простыми множителями по необходимости.

[ichthuss]

А что здесь невозможного? Решето Эратосфена вполне помещается в конечную программу (хотя для произвольно больших чисел ему понадобится пропорционально много памяти). Можно взять любой другой алгоритм, генерирующий бесконечную последовательность простых чисел подряд. Дальнейший код тривиальный и тоже органичен по объему.