Main Page | See live article | Alphabetical index

McCarthy 91 function

In discrete mathematics, the McCarthy 91 function is a recursive function which takes the value 91 for all positive integers less than 102. It was conceived by computer scientist John McCarthy.

The McCarthy 91 function is defined as

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's a sample McCarthy 91 program in Java:

public class McCarthy extends Object
{
       static int count = -1;

public McCarthy() { }

public int Mc91(int n) { count = count + 1;

System.out.println("Number after " + count + " iteration(s): " + n); if ( n < 0 ) { System.out.println("\\n Not a positive integer"); System.exit(-1); }

if ( n > 100 ) { return n-10; }

if ( n < 101 ) { return Mc91(Mc91(n+11)); }

return 0; }

public static void main(String[] args) {

McCarthy yorick1 = new McCarthy(); int yorick = Integer.parseInt(args[0]); System.out.println("\\n Number: " + yorick); System.out.println("Final Number: " + yorick1.Mc91(yorick)); } }