# How fast can all nth roots of an integer be computed?

I mean that for every $$i$$ from 2 to $$\lceil \log_2n\rceil$$ I want to know $$\lfloor \sqrt[i]{n}\rfloor$$. Could this be done faster than computing the roots one by one?

• What did you try? Are you able to come up with one different method? By the way, is there any significance about $\lceil\log_2 n\rceil$ here? Why not just an arbitrary integer $m\ge2$? – Apass.Jack Feb 6 at 22:56
• The significance of $\left\lceil \log_2 n \right\rceil$ is left as an exercise to the reader. – Pseudonym Feb 6 at 23:05
• @Appas.Jack Well I tried googling and thinking and didn't come up with anything. That number is significant because for all m above it the result will just be 1. – Q.Q Feb 7 at 0:07
• @Q.Q What is the range of $n$ you are interested in? Up to $2^{31}$? $2^{63}$? $2^{2^{10}}$? Really arbitrarily large? – Apass.Jack Feb 8 at 15:52
• @Apass.Jack of course arbitrarily large, otherwise the result could be computed in $O(1)$ – Q.Q Feb 8 at 20:36

Let's say n is very large, say around $$2^{1000}$$. In theory, you can calculate the k-th root of n by calculating $$2^{(\log n) / k}$$. Doing this for multiple k means you calculate $$\log n$$ only once, so you save some time here.