How many repetitions does the loop

Question

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?

Answer 1

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.

Answer 2

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.$

Answer 3

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$)

Answer 4

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)) $$