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
Battle Creek, Michigan

... average family size is 3.04. In the city the population is spread out with 27.2% under the age of 18, 8.7% from 18 to 24, 29.5% from 25 to 44, 21.0% from 45 to 64, and ...

 
 
 
This page was created in 42.1 ms