BIGpedia.com - McCarthy 91 function - Encyclopedia and Dictionary Online
encyclopedia search

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

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.

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
{
       static int count = -1;

       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));
       }
}


The contents of this article are licensed from Wikipedia.org under the GNU Free Documentation License.
How to see transparent copy

01-04-2007 01:21:04