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. 1.

    NxtPrm(n) is the smallest prime numberMathworldPlanetmath greater than or equal to n.

    Let Φ1(y) be the predicateMathworldPlanetmathy is prime” and Φ2(n,y) the predicate “ny”. Then


    where μ is the minimization operator. Since both Φ1 and Φ2 are primitive recursive, NxtPrm is recursive. From Euclid’s proof of the infinitude of primes (, two conclusionsMathworldPlanetmath can be made:

    • NxtPrm is a total functionMathworldPlanetmath, and

    • the search for y need not be unboundedPlanetmathPlanetmath: let p1,,pk be all the prime numbers less than n (suppose n>2), then p=p1pk+1 does not divide any of the pi, so must be at least n. Let q be some prime such that q|p. Then qpi for any i=1,,k, which means that nq. So what we have shown is that q is the most we need to search to find the next prime after n. Since qp=p1pk+1n!+1, we may reformulate the above expression:


    Since n!+1 is primitive recursive, we conclude that NxtPrm is primitive recursive by one application of bounded minimization and functionalPlanetmathPlanetmathPlanetmathPlanetmath composition.

  2. 2.

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

  3. 3.

    div(x,y), which is 1 if x|y, and 0 otherwise, is primitive recursive. The predicate Φ(x,y,z)x=yz” is primitive recursive, so that f(x,y):=μzxΦ(x,y,z) is primitive recursive. f(x,y) returns zx if yz=x, and x+1 otherwise. Thus “f(x,y)x” is a primitive recursive predicate, and its characteristic functionMathworldPlanetmathPlanetmath is easily seen to be 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 div is primitive recursive is by noticing that div(x,y)=1-˙sgn(rem(x,y)), where sgn is the sign function, and rem is the remainder function, both of which are primitive recursive. Since -˙ is primitive recursive, so is div.

    Remark. 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. 4.

    [x1/y], which returns the largest z (bounded by x) such that zyx, is primitive recursive, since it can be obtained by an application of bounded maximization to the predicate “zyx”.

  5. 5.

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

  6. 6.

    F(n) is the n-th Fibonacci numberDlmfMathworldPlanetmath. 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:


    Then F(n)=lo(2,g(n)), and F(n+1)=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,lo(3,g(n)))exp(3,lo(3,g(n))+lo(2,g(n))).

    Thus g is defined via primitive recursion from multiplicationPlanetmathPlanetmath, exponentiation, and lo, all of which primitive recursive. Therefore, g(n), and consequently, F(n)=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. 7.

    gcd(x,y) is the greatest common divisorMathworldPlanetmath 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:

    gcd(x,y):={0if xy=0,zif xy0 and z is the largest number x with z|x and z|y.

    Since both z|x and z|y are primitive recursive (from previous example), as well as the predicate “xy0”, so is their conjunctionMathworldPlanetmath. 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. 8.

    As a result, the predicate “x and y are coprimeMathworldPlanetmath” 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. 9.

    Euler ϕ-function ( 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


    which is primitive recursive. Hence ϕ(x)=f(x,x) is too. Note that ϕ(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