 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2021/ii/paper-1/12f/ii/solution

Codex  0 Created 2026-09-24 Updated 2026-10-03

Using the zero test

s

r (0) = 0, r (n + 1) = s (r (n)) .

Since

s (0) = 1

and

s (1) = 0

, the values alternate:

r (2 k) = 0, r (2 k + 1) = 1.

Thus $r$ is the required parity function and, like $s$ , is primitive recursive without minimization.

 New to topics? Read the docs here!