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:
is the smallest prime number greater than or equal to .
Let be the predicate “ is prime” and the predicate “”. Then
where is the minimization operator. Since both and are primitive recursive, is recursive. From Euclid’s proof of the infinitude of primes (http://planetmath.org/ProofThatThereAreInfinitelyManyPrimes), two conclusions can be made:
is a total function, and
the search for need not be unbounded: let be all the prime numbers less than (suppose ), then does not divide any of the , so must be at least . Let be some prime such that . Then for any , which means that . So what we have shown is that is the most we need to search to find the next prime after . Since , we may reformulate the above expression:
is the -th prime number, and . Again, this is a total function. To see that is primitive recursive, we simply note that .
, which is if , and otherwise, is primitive recursive. The predicate “” is primitive recursive, so that is primitive recursive. returns if , and otherwise. Thus “” is a primitive recursive predicate, and its characteristic function is easily seen to be , hence primitive recursive.
Note that the least such that is also the only satisfying the equation. An alternative, more direct (without bounded minimization) way to prove that is primitive recursive is by noticing that , where is the sign function, and is the remainder function, both of which are primitive recursive. Since is primitive recursive, so is .
Remark. is also the characteristic function of the predicate “”, which shows that “ divides ” is a primitive recursive predicate.
, which returns the largest (bounded by ) such that , is primitive recursive, since it can be obtained by an application of bounded maximization to the predicate “”.
Then , and . Moreover, , and
Thus is defined via primitive recursion from multiplication, exponentiation, and , all of which primitive recursive. Therefore, , and consequently, , is primitive recursive. The type of recursion used in defining the Fibonacci numbers is known as course-of-values recursion.
is the greatest common divisor of and (for convenience, we set ). In other words, the function is defined by two cases:
Since both and are primitive recursive (from previous example), as well as the predicate “”, so is their conjunction. Let be the corresponding characteristic function. By taking the bounded maximum, the second case of is primitive recursive. Since the first case of is clearly primitive recursive, hence itself is primitive recursive.
As a result, the predicate “ and are coprime” is primitive recursive, as it has the same characteristic function as the predicate “”, and has just been shown to be primitive recursive.
Euler -function (http://planetmath.org/EulerPhifunction) is primitive recursive. Let be the characteristic function of the primitive recursive predicate “ and are coprime”. Consider the bounded sum
which is primitive recursive. Hence is too. Note that .
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|
|Date of creation||2013-03-22 19:06:02|
|Last modified on||2013-03-22 19:06:02|
|Last modified by||CWoo (3771)|