McCarthy 91 function

From Freepedia

In discrete mathematics, the McCarthy 91 function is a recursive function which returns 91 for all positive integer arguments n ≤ 101 and returns <math>n - 10</math> for n > 101. It was conceived by computer scientist John McCarthy.

The McCarthy 91 function is defined as

<math>M(n)=\left\{\begin{matrix} n - 10, & \mbox{if }n > 100\mbox{ } \\ M(M(n+11)), & \mbox{if }n \le 100\mbox{ } \end{matrix}\right.</math>

Examples:

M(99) = M(M(110)) since 99 ≤ 100
      = M(100)    since 110 > 100
      = M(M(111)) since 100 ≤ 100
      = M(101)    since 111 > 100
      = 91        since 101 > 100

M(87) = M(M(98))
      = M(M(M(109)))
      = M(M(99))
      = M(M(M(110)))
      = M(M(100))
      = M(M(M(111)))
      = M(M(101))
      = M(91)
      = M(M(102))
      = M(92)
      = M(M(103))
      = M(93)
   .... Pattern continues
      = M(99)
     (same as above proof)
      = 91

Here is how John McCarthy may have written this function himself, in the language he invented. Here is the function written in Lisp:

(defun mc91 (n)
  (cond ((< n 1) (error "Function only defined for positive values of n"))
        ((<= n 100) (mc91 (mc91 (+ n 11))))
        (t (- n 10))))

And, here is an iterative implementation of the McCarthy 91 function written in C++:

int mccarthy(int n)
{
    for (int c = 1; c != 0; ) {
        if (n > 100) {
            n = n - 10;
            c--;
        } else {
            n = n + 11;
            c++;
        }
    }
    return n;
}

Here is a proof that the function behaves as expected.

For 90 ≤ n < 101,

M(n) = M(M(n + 11))
     = M(n + 11 - 10), since n >= 90 so n + 11 >= 101
     = M(n + 1)

So M(n) = 91 for 90 ≤ n < 101.

We can use this as a base case for induction on blocks of 11 numbers, like so:

Assume that M(n) = 91 for a ≤ n < a + 11.

Then, for any n such that a - 11 ≤ n < a,

M(n) = M(M(n + 11))
     = M(91), by hypothesis, since a ≤ n + 11 < a + 11
     = 91, by the base case.

Now by induction M(n) = 91 for any n in such a block. There are no holes between the blocks, so M(n) = 91 for n < 101. We can also add n = 101 as a special case.