0
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$
    – Arthur
    Dec 29, 2019 at 0:42
  • 6
    $\begingroup$ 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$.) $\endgroup$
    – mjqxxxx
    Dec 29, 2019 at 0:43
  • $\begingroup$ How do we arrive at log(log(x)) times before getting to 1? $\endgroup$ Dec 29, 2019 at 2:00

3 Answers 3

5
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
3
  • 2
    $\begingroup$ I think his question is about integers, although unclear, since he specifies the number of levels $\endgroup$
    – Threnody
    Dec 29, 2019 at 1:16
  • $\begingroup$ 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? $\endgroup$ Dec 29, 2019 at 4:23
  • $\begingroup$ Then my answer still stands, infinitely many, because that will never happen unless $\alpha=0$ $\endgroup$ Dec 29, 2019 at 4:27
1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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$. $\endgroup$ Dec 29, 2019 at 1:43
  • $\begingroup$ @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. $\endgroup$ Dec 29, 2019 at 1:45
  • $\begingroup$ The OP never mentions "integer" (when it would have been trivial to do so), and "discrete mathematics" says little, if anything about integers. $\endgroup$ Dec 29, 2019 at 2:12
  • $\begingroup$ 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? $\endgroup$ Dec 29, 2019 at 4:23
  • $\begingroup$ 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$. $\endgroup$ Dec 29, 2019 at 4:30

Not the answer you're looking for? Browse other questions tagged .