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