Knuth Numbers recursion

[brandonio21]

Hey Miriam, good to see you here and welcome to BP Forums!


So I was looking into your problem, and I was having a lot of difficulty with it, too. That is, until I researched the definition of Knuth numbers. According to WolframAlpha, the Knuth numbers are actually defined as:


That is, Kn+1 = 1 + min(2Ka, 3Kb) where:
a = floor(n/2)
b = floor(n/3)

Thus, using floor instead of ceil, we are able to simplify the algorithm to something like this:

Code:

public class KnuthNumbers
{
 public static int knuthNumber(final int n)
 {
   if (n == 0)
     return 1;

   int a = (n-1) / 2;
   int b = (n-1) / 3;

   return 1 + Math.min(2*knuthNumber(a), 3*knuthNumber(b));
 }
}

As you can see, there are a few things that have changed from your definition. I'll outline them below:

• I have changed the parameter to an int because n will never be a double since it is an index.
  
• The problem specifies the base case to be K0 = 1, so I changed the base case from what you had to match the base case in the problem.
  
• Instead of using Math.ceil as specified in the problem, since Wolfram's definition specifies that it is floor instead, we can simply use integer division, which automatically gives us the floor value.
  
• Your final return statement did not seem to match the definition of Knuth's numbers as given in the problem, so I changed that.
  

I realize that I left out your DataFormat statements, but I wanted to keep the answer as barebones as possible.

I hope this helped!