# How to find the 31st root of a large number without using calculator or logarithm in 30 seconds?

There is a recent contest in our school.

Let \begin{align} N=&\ 330450543498916787547705429904371272937979054655009\\&\ 6798365073248346973369906393714646262613023152668672 \end{align}

I am asked to find the $$31$$st root of $$N$$ without using any calculator or logarithm in $$30$$ seconds.

Since $$N$$ is a large number, I don't know how to solve this problem without using any calculator or logarithm in $$30$$ seconds, except for the fact that the $$31$$st root of $$N$$ must be even.

How can I find the $$31$$st root of $$N$$ without using any calculator or logarithm in $$30$$ seconds?

Is there any way to calculate the $$31$$st root of a large number without using any calculator or logarithm in $$30$$ seconds?

• Since there is a 30-second time limit, is this a problem from a programming contest? Or are you only allowed 30 seconds to evaluate the 31st root by hand? Commented Mar 23, 2023 at 1:36
• @WillJagy, alright, thanks. I thought you were talking to me haha. Commented Mar 23, 2023 at 1:37
• log(the number)/31~4. it ending in 8, you only have 9899/5, ~1980 to check. i imagine it taking about 30 seconds to count the digits though. lol. in for answers Commented Mar 23, 2023 at 1:38
• WA returns $N=2028^{31},$ btw. Commented Mar 23, 2023 at 1:45
• "Since $N$ is a large number, I don't know how to solve this problem " would you know how to solve it if $N$ was (a lot) smaller? Commented Mar 23, 2023 at 10:57

The number $$N$$ has $$103$$ digits in decimal, so its $$31$$th root must be a $$4$$-digit number (if it is an integer at all). The unit digit is $$8$$ of the result by modulo arithmetic. Contestants with programming experience may be familiar with the number $$2^{31} = 2\,147\,483\,648,$$ so $$2000^{31} \approx 2.1 \times 10^{102}$$, which is smaller than the desired number $$N \approx 3.3 \times 10^{102}$$ by about $$1.2 \times 10^{102}$$. Let the result be $$2000 + n$$ for some $$n \ll 2000$$ with unit digit $$8$$. Using the binomial approximation $$(2000 + n)^{31} \approx 2000^{31} + 31 \cdot 2000^{30} n$$ for $$n \ll 2000$$, we have $$n \approx \frac{1.2 \times 10^{102}}{31 \cdot 2000^{30}} \lesssim 0.04 \times 10^{102 - (90 + 9)} = 40$$ using the result $$2^{30} = 1\,073\,741\,824 \gtrsim 10^9,$$ where the inequality holds by ... quite a bit. This result follows from the value of $$2^{31}$$, which we assumed familiarity with. So $$n \lesssim 40$$ by quite a bit, and since the unit digit of $$n$$ is $$8$$, it seems that $$28$$ is a plausible guess. Indeed, it turns out that $$N = 2028^{31}$$.

Unfortunately, I cannot think of a feasible solution that only takes 30 seconds.

This approach is computable without a calculator, and arguably could be implemented in 30 seconds by someone (not me) really quick at arithmetic if they knew it beforehand.

Let the answer be $$a$$.

1. Show that $$2000 < a$$ by bounding -> Count number of digits, approximate $$2^{31} = 2 \times (2^{10})^3 \approx 2\times (10^3)^3$$. This shows that $$a$$ is "very close" to 2000.

• If desired, show that $$a < 2300$$ for rigor. Less important if we just need to be confident enough to give a numerical answer.
2. Show that $$a \equiv 48 \pmod {330}$$ via:

• $$a \equiv 0 \pmod{2}$$ -> Immediate from last digit
• $$a \equiv 0 \pmod{3}$$ -> Rule of 3, have to sum digits.
• $$a \equiv 3 \pmod{5}$$ -> Immediate from last digit. $$2 \equiv a^{31} \equiv a^{-1} \pmod{5}$$.
• $$a \equiv 4 \pmod{11}$$ -> Rule of 11, have to sum and subtract digits. $$4 \equiv a^{31} \equiv a \pmod{11}$$.
1. Hence conclude that $$a = 2028$$.

Note: We could use the Rule of 7 "Double and subtract" in place of the Rule of 11.

Original approach:

Let the answer be $$a$$.

1. Since $$a$$ has 103 digits, so $$a < 10000$$.
• In fact we can show that $$a \approx 2000$$ (and ideally bound it under 2500). There's a subsequent modification that uses this.
2. Let's consider primes $$p$$ such that $$a^{31} \equiv a \pmod{p}$$.
• If $$p \mid a$$, then $$p \mid S$$.
• If $$p \not \mid a$$, then we have $$a^{30} \equiv 1 \pmod{p}$$.
• Hence, we focus our attention on $$p = 2, 3, 7, 11, 31$$, to help us determine $$a$$.
3. Doing the divisibility calculations
• $$a \equiv 0 \pmod{2}$$,
• $$a \equiv 0 \pmod{3}$$,
• $$a \equiv 5 \pmod{7}$$,
• $$a \equiv 4 \pmod{11}$$,
• $$a \equiv 13 \pmod{31}$$.
4. Hence, $$a \equiv 2028 \pmod{14322}$$.
• Since we know $$a \approx 2000$$, we could avoid calculating mod 31, and still get $$a \equiv 180 \pmod{462}$$ to conclude that $$a = 2028$$.

This comes as an obvious answer, but if the question had appeared on a programming contest, brute force with Python allows well under $$30$$ seconds:

N = 3304505434989167875477054299043712729379790546550096798365073248346973369906393714646262613023152668672
n = 1
while n ** 31 != N:
n += 1
print(n) # 2028


Completes in about $$1$$ millisecond on my machine.

As L. F.'s answer points out, checking only $$4$$-digit numbers starting with $$1000$$ reduces the time further.

And even faster by just computing the result directly:

print(N ** (1/31)) # 2027.9999999999995


if a little floating-point inaccuracy is permitted.

Of course, let's not forget that all the tricks have been implemented for us already in a language like Python. Doing so in a low-level language such as C (in which there are integer limits) would be a different story.

• "without using any calculator". :-/ Commented Mar 23, 2023 at 9:55
• Ah, missed that. Thank you for pointing it out! Commented Mar 23, 2023 at 14:38