more examples of primitive recursive functions

With bounded minimization, bounded maximization, and properties of primitive recursive predicates, many more examples of primitive recursive functions can now be exhibited. We list some of the most common ones:

1. $\mathrm{NxtPrm}(n)$ is the smallest prime number greater than or equal to $n$.

   Let ${\mathrm{\Phi }}_1(y)$ be the predicate “$y$ is prime” and ${\mathrm{\Phi }}_2(n,y)$ the predicate “$n\le y$”. Then

   $$\mathrm{NxtPrm}(n)=\mu y({\mathrm{\Phi }}_1(y)\wedge {\mathrm{\Phi }}_2(n,y)),$$

   where $\mu$ is the minimization operator. Since both ${\mathrm{\Phi }}_1$ and ${\mathrm{\Phi }}_2$ are primitive recursive, $\mathrm{NxtPrm}$ is recursive. From Euclid’s proof of the infinitude of primes (http://planetmath.org/ProofThatThereAreInfinitelyManyPrimes), two conclusions can be made:

   • $\mathrm{NxtPrm}$ is a total function, and

   • the search for $y$ need not be unbounded: let $p_1,\mathrm{\dots },p_k$ be all the prime numbers less than $n$ (suppose $n>2$), then $p=p_1\mathrm{\cdots }{p}_k+1$ does not divide any of the $p_i$, so must be at least $n$. Let $q$ be some prime such that $q|p$. Then $q\ne p_i$ for any $i=1,\mathrm{\dots },k$, which means that $n\le q$. So what we have shown is that $q$ is the most we need to search to find the next prime after $n$. Since $q\le p=p_1\mathrm{\cdots }{p}_k+1\le n!+1$, we may reformulate the above expression:

     $$\mathrm{NxtPrm}(n)=\mu y\le (n!+1)({\mathrm{\Phi }}_1(y)\wedge {\mathrm{\Phi }}_2(n,y)).$$

   Since $n!+1$ is primitive recursive, we conclude that $\mathrm{NxtPrm}$ is primitive recursive by one application of bounded minimization and functional composition.

2. $\mathrm{Pr}(n)$ is the $n$-th prime number, and $\mathrm{Pr}(0):=1$. Again, this is a total function. To see that $\mathrm{Pr}$ is primitive recursive, we simply note that $\mathrm{Pr}(n+1)=\mathrm{NxtPrm}(\mathrm{Pr}(n))$.

3. $\mathrm{div}(x,y)$, which is $1$ if $x|y$, and $0$ otherwise, is primitive recursive. The predicate $\mathrm{\Phi }(x,y,z)$ “$x=yz$” is primitive recursive, so that $f(x,y):=\mu z\le x\mathrm{\Phi }(x,y,z)$ is primitive recursive. $f(x,y)$ returns $z\le x$ if $yz=x$, and $x+1$ otherwise. Thus “$f(x,y)\le x$” is a primitive recursive predicate, and its characteristic function is easily seen to be $\mathrm{div}(x,y)$, hence primitive recursive.

   Note that the least $z$ such that $x=yz$ is also the only $z$ satisfying the equation. An alternative, more direct (without bounded minimization) way to prove that $\mathrm{div}$ is primitive recursive is by noticing that $\mathrm{div}(x,y)=1\dot{-}\mathrm{sgn}(\mathrm{rem}(x,y))$, where $\mathrm{sgn}$ is the sign function, and $\mathrm{rem}$ is the remainder function, both of which are primitive recursive. Since $\dot{-}$ is primitive recursive, so is $\mathrm{div}$.

   Remark. $\mathrm{div}(x,y)$ is also the characteristic function of the predicate “$x|y$”, which shows that “$x$ divides $y$” is a primitive recursive predicate.

4. $[x^{1/y}]$, which returns the largest $z$ (bounded by $x$) such that $z^y\le x$, is primitive recursive, since it can be obtained by an application of bounded maximization to the predicate “$z^y\le x$”.

5. $\mathrm{lo}(x,y)$, which returns the largest $z$ (bounded by $y$) such that $x^z\mid y$, the integer version of the logarithm function, is primitive recursive, for $\mathrm{lo}(x,y)$ is the largest $z$ such that $\mathrm{div}(x^z,y)=1$, and $\mathrm{div}$ has been shown to be primitive recursive in the previous example. To make $\mathrm{lo}$ a total function, we also set $\mathrm{lo}(x,y):=0$ if $x\in \{0,1\}$.

6. $F(n)$ is the $n$-th Fibonacci number. The Fibonacci numbers are defined using a slight variation of primitive recursion: $F(0)=F(1)=1$, and $F(n+2)=F(n+1)+F(n)$. To show that $F$ is primitive recursive, first define a function $g$ as follows:

   $$g(n)=\exp (2,F(n))\exp (3,F(n+1)).$$

   Then $F(n)=\mathrm{lo}(2,g(n))$, and $F(n+1)=\mathrm{lo}(3,g(n))$. Moreover, $g(0)=6$, and

   $g(n+1)$ $=$ $\exp (2,F(n+1))\exp (3,F(n+2))$

   $=$ $\exp (2,F(n+1))\exp (3,F(n+1)+F(n))$

   $=$ $\exp (2,\mathrm{lo}(3,g(n)))\exp (3,\mathrm{lo}(3,g(n))+\mathrm{lo}(2,g(n))).$

   Thus $g$ is defined via primitive recursion from multiplication, exponentiation, and $\mathrm{lo}$, all of which primitive recursive. Therefore, $g(n)$, and consequently, $F(n)=\mathrm{lo}(2,g(n))$, is primitive recursive. The type of recursion used in defining the Fibonacci numbers is known as course-of-values recursion.

7. $\gcd (x,y)$ is the greatest common divisor of $x$ and $y$ (for convenience, we set $\gcd (x,0)=\gcd (0,y):=0$). In other words, the $\gcd$ function is defined by two cases:

   Since both $z|x$ and $z|y$ are primitive recursive (from previous example), as well as the predicate “$xy\ne 0$”, so is their conjunction. Let $c(x,y,z)$ be the corresponding characteristic function. By taking the bounded maximum, the second case of $\gcd$ is primitive recursive. Since the first case of $\gcd$ is clearly primitive recursive, hence $\gcd$ itself is primitive recursive.

8. As a result, the predicate “$x$ and $y$ are coprime” is primitive recursive, as it has the same characteristic function as the predicate “$\gcd (x,y)=1$”, and $\gcd (x,y)$ has just been shown to be primitive recursive.

9. Euler $\varphi$-function (http://planetmath.org/EulerPhifunction) is primitive recursive. Let $c(x,y)$ be the characteristic function of the primitive recursive predicate “$x$ and $y$ are coprime”. Consider the bounded sum

   $$f(x,y)=\sum _{i=0}^{y}c(x,i),$$

   which is primitive recursive. Hence $\varphi (x)=f(x,x)$ is too. Note that $\varphi (0)=0$.

Remark. It is not hard to show that, all of the functions above are in fact elementary recursive.

Title	more examples of primitive recursive functions
Canonical name	MoreExamplesOfPrimitiveRecursiveFunctions
Date of creation	2013-03-22 19:06:02
Last modified on	2013-03-22 19:06:02
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	13
Author	CWoo (3771)
Entry type	Example
Classification	msc 03D20