How many repetitions does the loop Here is the following algorithm:
for(k=2; k<n; k=k^k)

I understand that I need to check when 
$n=k^k$. 
But I'm stuck on $k=log_k(n)$
How many repetitions are performed by the loop?
 A: After the first pass we have $k=2^2=4$  If $n$ is $3$ or $4$ there will be only one pass.
After the second pass we have $k=4^4=256$.  If $4 \lt n \le 256$ there will be two passes.
After the third we have $k=256^{256}$, which is enormous-about $600$ digits.  Only if $n$ is larger than this will there be a fourth pass.  
I don't know of a nice function that can take $n$ and give back the number of passes.
A: Notice that
$$2^2=4,4^4=256,256^{256}\approx3.2317\cdot10^{616}.$$
Needless to say, the next term is astronomical.
So you take little risk by saying zero to three iterations. (If $n$ is a 32 bits integer uniformly drawn, say three and you'll be right with probability $0.999999940$)
A: We start with $k=2$. Since it is the first, let's call it $k_0$. We observe that:
$$k_0 = 2 = 2^1 = 2^{2^0}.$$
The next element of the sequence is:
$$k_1 = k_0^{k_0} = 2^2 = 2^{2^1}.$$
By continuing...
$$k_2 = k_3^{k_3} = (2^2)^{2^2} = 2^{2^3}.$$
$$k_3 = k_4^{k_4} = (2^{2^3})^{2^{2^3}} = 2^{2^{11}}.$$
$$k_4 = k_5^{k_5} = (2^{2^{11}})^{2^{2^{11}}} = 2^{2^{2059}}.$$
Let's introduce 
$s_i = \log_2 \log_2 k_i$ (i.e. $k_i = 2^{2^{s_i}})$. In our case, $s_0 = 0$, $s_1 = 1$, $s_2 = 3$, $s_3=11$, $s_4 = 2059$, ...
After a deep analysis of the showed calculation, it turns out that the $s$ sequence satisfies the following:
$$s_{i+1} = s_i + 2^{s_i},$$
with $s_0 = 0.$
A: I looked for the number of repetitions, here is the answer I thought of:
$$
2^(2^k) = n 
$$
$$
log(2^(2^k)) = log(n)
$$
$$
2^klog(2)=log(n)
$$
$$
2^k=log(n)
$$
$$
k=log(log(n))
$$
