Example of a primitive recursive function whose range is properly general recursive

Question

I know that not every recursive function from $\mathbb{N}$ to $\mathbb{N}$ has a range which is a recursive set. I wonder, is there a primitive recursive function $f$ such that the range of $f$ is a general recursive set, but not a primitive recursive set?

Answer 1

A standard "waiting" trick proves that in fact "r.e. = p.r.e." - any (nonempty) set which is the range of a recursive function is also the range of a primitive recursive function. The key point is that Kleene's $T$ predicate is primitive recursive.

Suppose $A=ran(\varphi_e)$ with $\varphi_e$ total recursive (total doesn't really matter here but it simplifies things). Fix $a\in A$, let $\langle\cdot,\cdot\rangle$ be the Cantor pairing function, and let $$\psi(\langle x,y\rangle)=\begin{cases} \varphi_e(x) & \mbox{ if }\varphi_e(x)[y]\downarrow\\ a & \mbox{ otherwise.} \end{cases}$$

Here "$\varphi_e(x)[y]\downarrow$" means "$\varphi_e(x)$ halts in at most $y$ steps," and is implemented using the $T$-predicate. The point is that because of the runtime bound, the function $\psi$ is primitive recursive. And we clearly have $ran(\psi)=A$.