# Prove that this function is primitive recursive?

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 ?

• It will be useful to define the $(n+2)$-th composite in terms of the $(n+1)$-th composite. Bounded minimalization can be used as an ingredient, but more is needed. I cannot really answer the question in detail, since I do not know what functions, predicates, have already been proved primitive recursive in your course. – André Nicolas Dec 24 '15 at 0:09
• @AndréNicolas the set division is primitive recursive – Maman Dec 24 '15 at 18:25
• The way you have defined it we have $g(n)=4$ for all $n\ge 3$. – André Nicolas Dec 24 '15 at 20:07
• @AndréNicolas what if I write $g(n) = \mu k \le p(n)!+1$, {$k$ is not prime} which a primitive recursive set and $p(n)$ gives the $(n+1)^{th}$ natural numbers. – Maman Dec 25 '15 at 11:12
• Not right yet, you need to use primitive recursion. I don't know how detailed you have to be. – André Nicolas Dec 25 '15 at 16:18

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.

• Why did you use $\mu m < 4n$ ? – Maman Jan 4 '16 at 0:04
• Using Bertrand's postulate, we know given $n > 1$ we always have a prime between $n$ and $2n$; I just used the more general bound of $n$ and $4n$, which holds for all $n>0$, doesn't it? When we start looking for the $m$ such that $m > \Pi(n)$, we know there must be a prime somewhere between $\Pi(n)$ and $4\Pi(n)$, and between this interval there $must$ be a $non$-$prime$ $number$. This is probably an 'excessively' large bound, but it is primitive recursive nonetheless. – Philip White Jan 5 '16 at 1:02