I'm having trouble figuring out how to compute the iterated logarithm (log-star) by hand without using a calculator or programming language. I wrote out the following program in Java to check my answers as I practice but can't seem to wrap my head around how to do this without a computer.
public class Recurrences { public static void main(String[] args) { // Compute log-star (base 2) of 100,000 System.out.println((int) logStar(100000, 2)); } /** * log-star recursive method * @param n Value of input * @param base Base value for the logarithm (i.e. log base 2 would give 2) * @return If n > 1.0, return 1 + logStar( log2(n) ), else return 0. */ public static double logStar(double n, int base) { if (n > 1.0) { // Recursive case return 1.0 + logStar((Math.log(n)) / (Math.log(base)), base); } else { // Base case. If n <= 1, return 0. return 0; } }
}Do you have any tips as to how you would calculate log-star of say, 100000? My program says the answer should be 5 but I don't know how I would go about getting that answer with pen and paper. Also, as shown above in the code, I'm working in log base 2.
Edit: here is a link that explains the concept. Sorry for the initial lack of info.
$\endgroup$ 91 Answer
$\begingroup$By hand
$2^{16} =65536 \lt 100000 \le 131072=2^{17}$
$2^4 \le 16 \lt \log_2(100000) \le 17 \le 2^5$
$2^2 \le 4 \lt \log_2(\log_2(100000)) \le 5 \le 2^3$
$2^1 \le 2 \lt \log_2(\log_2(\log_2(100000))) \le 3 \le 2^2$
$2^0 \le 1 \lt \log_2(\log_2(\log_2(\log_2(100000)))) \le 2 \le 2^1$
$0 \lt \log_2(\log_2(\log_2(\log_2(\log_2(100000))))) \le 1$
Five $\log_2$s in the final expression
$\endgroup$ 2
