Encyclopedia > McCarthy 91 function

  Article Content

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. 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 <math>\le</math> 100
       = M(100) since 110 > 100
       = M(M(111)) since 100 <math>\le</math> 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));
        }
 }



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Alfredo Stroessner

... the end of US aid to Stroessner regime. Stroessner's own Colorado Party grew angry with him, and he was deposed on 1989 by a member of the Colorado Party, General Andrés ...