2

So, I want to construct the function $f(x)$ that returns the smallest prime greater than $x$.

First, I constructed the function $g(x,y)$ that returns the smallest prime strictly between $x$ and $y$ (or $y$ if there is no such prime) using primitive recursion,

\begin{equation} g(x,0) = 0 \end{equation} \begin{equation} g(x,s(y))= \left\{ \begin{array}{rl} g(x,y) & \text{if } g(x,y) \text{ is prime and greater than } x,\\ y & \text{if } y \text{ is prime and greater than } x,\\ s(y) & \text{otherwise}. \end{array} \right. \end{equation}

Though, once we get rid of the bound it gets impossible to use primitive recursion. The solution I found was to define $f$ in terms of $g$, i.e.

$f(x) = g(x,(x!+2))$

Now my question is: is that a 'legal' way to define the desired function?

[Can't seem to fix the formatting on the equation above please forgive me!]

wet
  • 605
  • 1
    Seems perfectly reasonable (and clever) to me! You could also use $g(x,2x)$, since by Bertrand's postulate, there's always a prime between $x$ and $2x$. – Greg Martin Sep 03 '16 at 08:09
  • Sweet, thanks! [I can't take all the credit for the cleverness though, the book showed how to express a bounded search with primitive recursion] – wet Sep 03 '16 at 09:12

0 Answers0