Primitive Recursive Functions

Question

I would like to show that the function $f:\mathbb{N} \to \mathbb{N}$ defined by $f(n)=p_n$ where $p_n$ is the $n+1$ prime number is primitive recursive. The fact is that I just manage to show it is $μ$ recursive using Kleene operator and I don't see any way to avoid using it. Any help would be appreciated!

Answer 1

Consider (heuristically)

$$ f(0) = 2\\ f(n+1) = \text{the least $x \leq (2*f(n))$ such that $x > f(n)$ and $x$ is prime} $$

It is a theorem of arithmetic that for every $k$, there is at least one prime between $k$ and $2k$. Thus we know we can find a prime between $f(n)$ and $2 f(n)$. The least such number will, of course, be the next prime.

I leave it to you to formalize the above idea, but as a hint:

Show

$$ g(r) = \text{the least $x \leq 2r$ such that $x > r$ and $x$ is prime} $$

is primitive recursive (using bounded search), then use it to define $f$ by recursion.

---

I hope this helps ^_^