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
Lake Ronkonkoma, New York

... 5.85% of the population are Hispanic or Latino of any race. There are 6,700 households out of which 35.6% have children under the age of 18 living with them, 59.8% are ...

 
 
 
This page was created in 79.6 ms