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 !

  • $\begingroup$ 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. $\endgroup$ – André Nicolas Dec 24 '15 at 0:09
  • $\begingroup$ @AndréNicolas the set division is primitive recursive $\endgroup$ – Maman Dec 24 '15 at 18:25
  • $\begingroup$ The way you have defined it we have $g(n)=4$ for all $n\ge 3$. $\endgroup$ – André Nicolas Dec 24 '15 at 20:07
  • $\begingroup$ @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. $\endgroup$ – Maman Dec 25 '15 at 11:12
  • $\begingroup$ Not right yet, you need to use primitive recursion. I don't know how detailed you have to be. $\endgroup$ – 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))$


$\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.

  • 1
    $\begingroup$ Why did you use $\mu m < 4n$ ? $\endgroup$ – Maman Jan 4 '16 at 0:04
  • $\begingroup$ 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. $\endgroup$ – Philip White Jan 5 '16 at 1:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.