Prime Exponent Function is Primitive Recursive

Theorem

Let $n \in \N$ be a natural number.

Let $\left({n, j}\right): \N^2 \to \N$ be defined as:

$\left({n, j}\right) = \left({n}\right)_j$

where $\left({n}\right)_j$ is the prime exponent function.

Then $\left({n, j}\right)$ is primitive recursive.

Proof

Let $p \left({j}\right)$ be the prime enumeration function.

For $n \ne 0$ and $j \ne 0$, we see that $\left({n}\right)_j$ is the largest value of $k$ for which $p \left({j}\right)^k$ is a divisor of $n$.

Thus $\left({n}\right)_j$ is the smallest value of $k$ for which $p \left({j}\right)^{k+1}$ is not a divisor of $n$.

We note that if $r \ge n$ and $j \ne 0$, we have $p \left({j}\right)^r \ge 2^r \ge 2^n> n$.

Thus $n$ is a (generous) upper bound of $\left({n}\right)_j$.

The condition that $p \left({j}\right)^{k+1}$ is not a divisor of $n$ can be expressed as:

$\operatorname{div} \left({n, p \left({j}\right)^{k+1}}\right) = 0$

where:

• $\operatorname{div}$ is primitive recursive
• The Equality Relation is Primitive Recursive
• $p \left({j}\right)$ is primitive recursive
• Exponentiation is Primitive Recursive
• Addition is Primitive Recursive.

So we see that the relation:

$\mathcal R \left({n, j, k}\right) \iff \operatorname{div} \left({n, p \left({j}\right)^{k+1}}\right) = 0$

is primitive recursive.

From Bounded Minimization is Primitive Recursive, we also see that:

$\left({n}\right)_j = \begin{cases} \mu k \le n \mathcal R \left({n, j, k}\right) & : n \ne 0 \land j \ne 0 \\ 0 & : \text{otherwise} \end{cases}$

is primitive recursive.

The result follows.

$\blacksquare$