7

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?

Scene
  • 1,566
Thirdy Yabata
  • 558

3 Answers3

10

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.

L. F.
  • 1,940
7

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$.
Calvin Lin
  • 68,864
4

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.

Scene
  • 1,566