# How many times can an integer be square rooted? [closed]

I know that we can divide an integer greater than 1, let's say $$n$$, $$\log_b(n)$$ times by $$b$$. But how many times can we square root an integer until we reach reach $$\sqrt(2)$$? What about cube roots and so forth?

This problem emerged in my head when studying algorithms and finding out the number of levels in a recursion tree with an input size that divides by $$b$$ at every recursion.

• Can you clarify exactly what you mean? For instance, $1000$ can't be divided by $3$ at all, and certainly not $6.29$ times, whatever that's supposed to mean. Dec 29, 2019 at 0:42
• Working in integers, and rounding if necessary, you should be able to take the square root of $x$ something like $\log \log x$ times before getting to $1$. (If you're not working in integers, I'm not sure what your stopping condition is.... you can square root forever, getting closer and closer to $1$.) Dec 29, 2019 at 0:43
• How do we arrive at log(log(x)) times before getting to 1? Dec 29, 2019 at 2:00

Hmm I definitely agree with Rhys Hugest. If you take a number $$n \geq 1$$ you can take the square root of the number infinitely many times because any number greater than 1 will always have a square root greater than one as well.

Since you're studying algorithms, it might be good to analyze complexity. I think what you're actually trying to ask is how many times can you take the square root of a number, n, before you reach a constant.

For simplicity sake let's say you want to know how many times you can take the square root of a number before we hit $$\leq \sqrt(2)$$

$$\sqrt(\sqrt(...\sqrt(n) \leq \sqrt(2)$$ Let's say that the number of times we can take the square root until we have $$\leq \sqrt(2)$$ is m

$$n^{{1/2}^{m}} \leq 2^{1/2}$$ Raising both sides to the $${{2}^{m}}$$ power $$n \leq 2^{2^{m-1}}$$ We want to isolate m now $$log(log(n)) + 1 \leq m$$

We can use the same reasoning for cube roots and so forth.

$$\forall \alpha>0; \sqrt{1+\alpha}=1+\frac\alpha2-\frac{\alpha^2}{8}+\frac{\alpha^3}{16}-...=1+\beta, 0<\beta<\alpha$$

In other words, infinitely many times.

• I think his question is about integers, although unclear, since he specifies the number of levels Dec 29, 2019 at 1:16
• Sorry, I guess I should've worded my question better. I meant how many times can I take the square root of a number, n, before I hit less than or equal to one? Dec 29, 2019 at 4:23
• Then my answer still stands, infinitely many, because that will never happen unless $\alpha=0$ Dec 29, 2019 at 4:27

If you factor a number $$n$$ into primes you get something like $$n=p^aq^br^c$$. You can divide it by $$p\ a$$ times and get a whole number, but no more. This is sometimes written $$\operatorname{ord_p}(n)$$

For the number of square roots, take the $$\gcd$$ of the exponents, $$a,b,c$$ in my example. Then take $$\operatorname{ord_2}(\gcd(a,b,c))$$, so if $$\gcd(a,b,c)$$ is a multiple of $$16=2^4$$ you can take four square roots.

• If you're dealing with real numbers, then of course you can "square root it" an infinite number of times... with an answer approaching $1.0$. Dec 29, 2019 at 1:43
• @DavidG.Stork: I thought it was clear OP was interested in integer results in both cases. The tags support that and the question seems to, though it is not explicit. Dec 29, 2019 at 1:45
• The OP never mentions "integer" (when it would have been trivial to do so), and "discrete mathematics" says little, if anything about integers. Dec 29, 2019 at 2:12
• Sorry, I guess I should've worded my question better. I meant how many times can I take the square root of a number, n, before I hit less than or equal to one? Dec 29, 2019 at 4:23
• You never get less than $1$ with a square (or any other) root. The square root of any number greater than $1$ is again greater than $1$. Dec 29, 2019 at 4:30