Prove that this function is primitive recursive?

Question

Let $g : \mathbb{N} \rightarrow \mathbb{N}$, $n\mapsto$ the $(n+1)^{th}$ natural number which is not prime.

I have to prove that $g$ is a primitive recursive function.

My attempt is by minimization : $g(n) = \mu k \le n! + 1$, $\exists \ 1<m<k$ such as {$k$ is divided by $m$}. The last set is primitive recursive.

Is it correct ?

Thanks in advance !

Answer 1

1) So we'll assume $\mathbb{N} = {0,1,2,...} $

2) Let $P=\{2, 3, 5, ...\} = \{p_0 , p_1 , ... \}$ and so $p_n$= the $n+1$th prime.

The primitive recursive function you asked for can be defined as follows:

$\Pi(0)=1 $

$\Pi(n+1)=h(n, \Pi(n) )= (\mu m<4n)(m \notin P \wedge m> \Pi(n))$

---

Table:

$\Pi(0)=1 $

$\Pi(1)=4 $

$\Pi(2)=6 $

$...$

And so we can see, given any $n \in \mathbb{N} $ the prim rec $\Pi(n) $ finds the $n+1$-th non-prime natural number.