Помогите разобраться с принципом доказательства примитивной рекурсивности множества чисел
Не уверен, что это должно решаться именно так (к сожалению, не нашел ни одного похожего примера), но предполагаю, что нужно составить примитивно рекурсивную характеристическую функцию:
, где
- целочисленное деление, а
- остаток от деления.
Далее, левую часть запишем немного по-другому, а равенство справа возьмём под целочисленный корень n-ой степени:
, где
- целочисленный корень
-ой степени из
.
Вроде выглядит не очень плохо, одна только загвоздка: даже приблизительно не представляю как доказать рекурсивную примитивность ф-ии