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

[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]

Да, логично.