Problem Solving in Automata, Languages, and Complexity

4.6 Primitive Recursive Functions^205

Solution. (a) quot(m, n) = [if n > 0 then (mini)a+# - + 1) l n > m] else 01.

(b) mod(m,n) = [if n > 0 then (mini)"(m, n) l n + i = m] else 01.

(c) prime(n) =I [(n > 2) and (vj),<j<nl - - l[mod(n, j) > O]]. cl

Remark. In the above proof of part (c), we used a more general quantifier

.

w> 2<j<n 1. 1 than the one introduced in Theorem 4.29. More formally, we

should first define a new predicate

prime’@, k> = [n > - 2 and (Vj)j<k[j - < - 1 or mod(n,j) > 01.

Then, we observe that prime(n) = prime’(n,pred(n)), and so prime is prim-

itive recursive. From this example, we see that we can extend the basic

quantifiers used in Theorem 4.29 to quantifiers of the form (3j)e(n)<j<,(n)

and (vj)l(n)<j<u(n) and still preserve primitive recursiveness, as long &-l(n)

and u(n) are primitive recursive functions.

Example 4.31 Let f(0) = 1 and, for n 2 1, f(n) = the nth digit to the right

of the decimal point of the decimal expansion of a. Prove that f is primitive

recurswe.

Solution. Let g(n) be th e integer m whose decimal expansion is equal to
f(O)f(l)f(2)... f(n) (e.g., g(3) = 1414). Then,

g(n) = (mink)k<lon+l - [(k + 1)2 > 2 l 102n],

and f(n) = mod(g(n), 10).

Exercises 4.6

1. Show that the following functions are primitive recursive:

(a) factorial(n) = n!.

.n

(b) fi(n) = 7-P

tion gl (n, m)

>

n levels

. [Hint: First consider a more
.n
= nn’

• }T-I-~ levels
  . I

general func-

(4 f2b-d = ll%, 4 l

(4 fdn) = {

1 if n is the sum of two primes,

0 otherwise.

(e) +(n) = the number of primes less than or equal to n.

(f) lcm(n,m) = th e 1 eas t common multiple of n and m.

(g) s(n) = the number of digits in the decimal representation of n.

(h) h(n9 ml = the mth most significant digit of the decimal repre-

sentation of n if 1 < - m - < s(n) (and h(n,m) = 0 if m = 0 or

m > s(n)).