The amount of times a number need to be squared rooted

Question

Consider the following recursive function $f()$

def f(x,n=0):
   if x<2:
     return n
   return f(math.sqrt(x),n+1)

$f(x)$ calculates the number of square-root operations that need to be taken such that the result is less than 2

Is there a way to calculate that analytically with a formula ?

Answer 1

The square root of $x$ is $x^{1/2}$. If you take the square root $n$ times, you get $((x^{1/2})^{\dots})^{1/2} = x^{1/(2^n)}$. We want the minimum integer value of $n$ such that $x^{1/(2^n)} < 2$.

Taking the logarithm (base $2$) of both sides, we want $\frac{1}{2^n}\log_2(x)< 1$, which is equivalent to $2^n > \log_2(x)$, and (taking another logarithm) $n>\log_2(\log_2(x))$. So the minimum integer value of $n$ satisfying this inequality is $\lceil \log_2(\log_2(x))\rceil$.

Answer 2

The logarithm of a number is defined as $\log_b{a}=c$ when $a=b^c$. In your case, taking the square root implies $$ \log_b{\sqrt{x}} = \frac{1}{2}\log_b{x} $$ Iterating $n$ times implies $$ \log_b{\sqrt{\dots\sqrt{x}}} = \frac{1}{2^n}\log_{b}{x}. $$ Now, the logarithm is increasing, so $$ \log_b{x}>\log_b{y} \iff x>y. $$ Hence the $n$th square root of $x$ is less than $2$ when $$ \log_b 2 > \frac{1}{2^n}\log_b{x},\\ \iff \log_b{x} < 2^n\log_b{2} $$ Now let's choose $b$. An obvious one is $b=2$, since $\log_2{2}=1$ by definition, and we have then $$ \log_2{x} < 2^n. $$ Taking logs again in base $2$, we find that $$ n>\log_2{\log_2{x}}. $$ Exactly the same argument shows that the reverse inequality works the same way, so you need $n>\lceil\log_2{\log_2{x}} \rceil$, the first integer larger than $\log_2{\log_2{x}}$.