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
DB

... is the abbreviation of Dominion Breweries[?], a major beer brewing company of New Zealand. This is a disambiguation page; that is, one that just points to other pages ...

 
 
 
This page was created in 23.7 ms