Finding roots of numbers quickly

Computing cube roots of two digit numbers

In summer 2018, I was teaching a math class for high school students on problem solving and algebra at Harvard. A student of mine mentioned a trick he knew for calculating a cube root of a number quickly in his head. The entire class was interested, and he gave us the following instructions:

  • Choose any two digit number you like and cube it on a calculator.
  • Tell me the number you cubed.

I pulled out my phone, cubed a number, and told the student “my number cubed is 148,877”. In a split second, he responded back “the number you cubed was 53”. I was shocked that he solved it so quickly! For a few more minutes, other students called out cubes, and the student would respond back with what number was cubed. After amazing all of us, the student was kind enough to teach us his trick. In this blog post, I’ll show the same steps so that you too can pull off this trick to impress your friends/family.

To begin with, the only bits of information you need to be able to pull off this trick are knowing the 1-digit cubes in your head. If you don’t know them, they are:

2^3=8, 3^3=27, 4^3=64, 5^3=125, 6^3=216, 7^3=343, 8^3=512, 9^3=729.

One important thing to notice in this list is that the units digit of every cube is unique.

xx^3Units digit of x^3

Since the units digit are unique, if we know what the units digit of x^3, we can look at our table above to determine the units digit of x. For example, if x^3 =148,877, then since x^3 has a units digit of 7, we know the units digit of x is 3 by looking at the table above.

Now that we know the units digit of x, all that’s left to determine is the tens digit (since we started with a 2 digit number). For this, we need to determine what two cubes the digits in the thousands place of x^3 lie between. For example, with 148,877, the digits in the thousands place are 148. We see that 125<148<216, therefore,


Hence, we know the tens digit of x is 5, so our original cube must be 53.

Let’s try another quick example, and then I’ll leave some exercises for the reader.

Suppose we want to find the two digit number, which, when cubed gives us 373,248. We begin by looking at the units digit of our cube, which is 8. We therefore know the units digit of the two digit number must be 2. Furthermore, we see that 343<373<512, therefore, the tens digit of the cube must be 7. Hence, our two digit number is


Practice Problems

Here are some exercises for the reader to try out themselves:

  • Find the two digit number, such that its cube is equal to 19,683.
  • Find the two digit number, such that its cube is equal to 29,791.
  • Find the two digit number, such that its cube is equal to 74,088.
  • Find the two digit number, such that its cube is equal to 185,193.
  • Find the two digit number, such that its cube is equal to 328,509.
  • Find the two digit number, such that its cube is equal to 614,125.
  • Find the two digit number, such that its cube is equal to 970,299.

Computing 5th roots of numbers ending in 1, 3, 7, or 9 quickly

On Dr. Ali Gurel’s YouTube channel, COOL MATH, he shows a neat trick for finding fifth roots of odd numbers up to 200, not ending in a 5. I recommend watching his video first to see some examples of the trick, and below I’ll explain the math behind why the trick works and also extend it to any three digit number.

There are four cases for the units digit of the number: either a 1, 3, 7, or 9. Notice that

1^5\equiv 1\pmod{10}, 3^5\equiv 3\pmod{10}, 7^5\equiv 7\pmod{10}, 9^5\equiv 9\pmod{10}.

Therefore, the units digit of x and x^5 are the same.

To use this trick on 5th roots of numbers between 1 and 200, you only need to memorize that 3^5=243. For larger 5th roots, you’ll need to use a table to establish bounds.

Units digit 1 case

In the case that the units digit is 1, then we can represent our number in the form 10x+1. For now, we’ll tackle the same case as in Dr. Ali’s video and assume that 0\le x\le 19.

Using the binomial theorem,


Since \binom{5}{3}=10, we see every term is a multiple of 1000, except for the last two. Therefore, when we consider the last three digits of (10x+1)^5, we get (10x+1)^5\equiv 50x+1\pmod{1000}. Since 0\le x\le 19, we see that this remainder mod 1000 is unique.

To find the original number, we take the last three digits and perform the calculation:

\frac{\text{Last Three Digits}-1}{5}+1=\frac{50x+1-1}{5}+1=10x+1.

For example, 21^5=4,084,101, which has the last three digits 101. We therefore see that the fifth root of this number was \frac{101-1}{5}+1=21.

Units digit 3 case

Now, if the number we started with ends in a 3, then we can write the number in the form 10x+3, where we assume for now that 0\le x\le 19. Using the binomial theorem,

(10x+3)^5=10^5x^5+\binom{5}{1}10^4x^4\cdot 3+\binom{5}{2}10^3x^3\cdot 3^2+\binom{5}{3}10^2x^2\cdot 3^3+\binom{5}{4}10^1x^1\cdot 3^4+3^5.

Again, we only consider the last three digits of this number, and therefore

(10x+3)^5\equiv 50x\cdot 3^4+3^5\pmod{1000}.

Notice that 50\cdot 3^4=4050, therefore we can further reduce to get

(10x+3)^5\equiv 50x+3^5\pmod{1000}.

Now if 0\le x\le 15, then 50x+3^5<1000, and we can use the same trick again:

\frac{\text{Last Three Digits}-3^5}{5}+3=\frac{50x+3^5-3^5}{5}+3=10x+3.

However, if 16\le x\le 19, then the last three digits of our number will be (50x+3^5-1000), so we have to add 1000 to get our original number:

\frac{\text{Last Three Digits}+1000-3^5}{5}+3.

As an example of this, if we want to find the fifth root of 2,073,071,593, since 593>3^5=243, we know it’s the first case and we get the fifth root as \frac{593-3^5}{5}+3=73.

Alternatively, if we want to find the fifth root of 205,236,901,143, we see that 143<3^5, therefore, we have the second case and get the fifth root as \frac{143+1000-3^5}{5}+3=183.

Units digit 7 case

If our number ends in a 7, then it can be represented as 10x-3 where 0\le x\le 19. By similar logic to the calculations before, we only consider the last three digits:

(10x-3)^5\equiv \binom{5}{4}\cdot 10x\cdot (-3)^4+\binom{5}{5}\cdot (-3)^5\pmod{1000}.

As before, since \binom{5}{4}\cdot (-3)^4=4050, this further reduces as

(10x-3)^5\equiv 50x-3^5\pmod{1000}.

Now if 19\ge x\ge 5, the last three digits of (10x-3)^5 will be 50x-3^5, so we perform the calculation

\frac{\text{Last Three Digits}+3^5}{5}-3=\frac{(50x-3^5)+3^5}{5}-3=10x-3.

As an example, if we wish to find the fifth root of 8,587,340,257, we take the last three digits, 257, and using the formula above get \frac{257+3^5}{5}-3=97, which is indeed the fifth root.

However, if 0\le x\le 4, then 50x-3^5<0, and therefore the last three digits will be (50x-3^5+1000). In this case, we subtract 1000 from our initial calculation to get:

\frac{\text{Last Three Digits}-1000+3^5}{5}-3.

As an example, if we want to find the fifth root of 69,343,957, since 957+3^5>1000, we use the calculation from the second case to get a fifth root of \frac{957-1000+3^5}{5}-3=37.

Units digit 9 case

Finally, if a number ends in a 9, then it can be represented in the form 10x-1, where 0\le x\le 19. By the same logic as before, we see that

(10x-1)^5\equiv \binom{5}{4}\cdot 10x\cdot (-1)^4+\binom{5}{5}\cdot (-1)^5\pmod{1000}\equiv 50x-1\pmod{1000}.

Therefore, to recover the original number, we can perform the following calculation:

\frac{\text{Last Three Digits}+1}{5}-1=\frac{50x-1+1}{5}-1=10x-1.

As an example, if we want to find the fifth root of 282,475,249, we take the last three digits, 249, and perform the calculation above to get a fifth root of \frac{249+1}{5}-1=49.

Practice Problems

Here are some practice problems to test out your understanding of this method. I highly recommend reviewing the sections above as you work through these tricky examples! As a hint, pay attention tot he last three digits!

  • Find the fifth root of 161,051.
  • Find the fifth root of 6,436,343.
  • Find the fifth root of 90,224,199.
  • Find the fifth root of 14,348,907.
  • Find the fifth root of 16,850,581,551.
  • Find the fifth root of 41,615,795,893.

Generalizing to larger numbers

This trick will work for all odd fifth powers ending in a 1,3,7, or 9 up until 200^5=3.2 \cdot 10^{11}. If we start with a number between 200 and 400, then the range for the fifth power is between 3.2\cdot 10^{11} and 1.024\cdot 10^{13}. In this case, we can use the same trick as above, to get a number between 1 and 200, and then add 200 to the final result.

For example, if someone tells us to find the fifth root of 3,973,195,810,651, we see this number is approximately 3.9\cdot 10^{12}, therefore the fifth root must be between 200 and 400. Using the same trick as before, we see that the number mod 200 must be \frac{651-1}{5}+1=131, and adding 200 to bring us into the correct range gives us 331 (you can verify this is the fifth root of the original number using WolframAlpha).

In general, the fifth powers fall into the ranges given in the table below.

Range of xRange of x^5
1 to 2001 to 3.2\cdot 10^{11}
200 to 4003.2\cdot 10^{11} to 1.024\cdot 10^{13}
400 to 6001.024\cdot 10^{13} to 7.776\cdot 10^{13}
600 to 800 7.776\cdot 10^{13} to 3.277\cdot 10^{14}
800 to 1000 3.277\cdot 10^{14} to 10^{15}

As a quick example, suppose you’re told to find the fifth root of 377,571,474,600,343. Using the table above, you know this number is approximately 3.776\cdot 10^{14}, which is in the bottom-most row, therefore the number which was cubed was between 800 to 1000. We look at the last three digits, 343, and since the number ends in 3, perform the calculation \frac{343-3^5}{5}+3=23 to determine the mod 200 residue of our number. We then add 800 to get our number into the desired range, and find the fifth root is 823.

Practice Problems with Larger Numbers

  • Find the fifth root of 481,170,140,857.
  • Find the fifth root of 3,303,341,057,599.
  • Find the fifth root of 14,195,130,030,907.
  • Find the fifth root of 78,410,163,603,001.
  • Find the fifth root of 872,095,812,856,093.

While these problems all look daunting at first, with some practice using the technique above, you should be able to compute the fifth roots in a matter of a few seconds! Give the method some practice and patience, and hopefully you too should be an expert on computing cube and fifth roots in your head quickly!

Social Distancing at the Bar Riddle

I came across the following puzzle yesterday (edited for relevancy):

There is a bar with 25 seats in a line. People are social-distancing so when they walk into the bar, they always try to find a seat farthest away from others. To comply with government restrictions, no two people can sit next to each other. If a person walks in and there are no available seats, they will leave. Where should the owner tell his first customer to sit in order to maximize the number of people in the bar?

In order to solve this problem, we can utilize some wishful thinking. The best-case scenario is when every person is seated exactly two away from everyone else:

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25.

How can we produce such a sequence? Well, if we had every fourth person, then the other people can sit in-between them (while still maintaining a distance of 2):

1, 5, 9, 13, 17, 21, 25.

To obtain this configuration, we take every eighth person, so the remaining people can sit a distance of four away from everyone else:

1, 9, 17, 25.

Finally, to obtain this configuration, we either need to put the first person on seat or 17. We used backtracking in order to determine the best starting seat.

For a visual solution, I created a MatLab program that would test out each starting location of the first customer and then generates how the other customers would fill out the bar.  For the original puzzle, this creates the following graph:


The y-axis is the location of the first customer seated, while the x-axis shows the seating configuration according to the bars’ rules. The starred values indicate the optimal configuration, which occurs exactly when the first person is seated at 9. The relative size of each Polkadot is the order the customer is seated in the configuration, which is why the line y=x has the largest dots.

In this case, we were able to seat \lceil \frac{25}{2}\rceil=13 people effectively. Can we always obtain this bound for a bar with n seats?

Unfortunately, the answer is no, but this isn’t obvious to see.  Plotting the number of seats against the maximum number of people seated gives the following graph:


The stars indicate when the maximum number of people seated equals \lceil \frac{n}{2}\rceil. It’s interesting to note the outliers here are when n=15, 23, 27, 28, 29, 30, 31, 39.

Let’s take one of these specific values and see what goes wrong in our backtracking approach. For n=15, the best possible scenario would be:

1, 3, 5, 7, 9, 11, 13, 15.

In order to obtain this, we take every fourth person as we did before:

1, 5, 9, 13.

To obtain this, we suspect we should seat the first customer at 9. However, plotting this shows this generates a different graph:


The sequence starting at 9 is 1, 3, 5, 7, 9, 12, 15. Why did we skip over 13? This is because our backtracking approach didn’t account for the selection mechanism.

Starting with 9, the second person selected will sit at 1. After this, the next person will sit at 15, then 5 to create the current configuration: 1, 5, 9, 15. The next person entering the bar will want to sit as far away from the other people as possible. Scanning all the seats, they’ll choose seat 12 since it’s 3 away from both 9 and 15. Therefore, 15 is a suboptimal starting value.

We noticed every value before this was optimal, which leads us to wonder if we can characterize all of the values of n that give an optimal configuration.

Expanding the search up to n=100 gives the following values that are optimal:

n=1 2 3 4 5 6 7 8 9 10 11 12 13 14 16 17 18 19 20 21 22 24 25 26 32 33 34 35 36 37 38 40 41 42 48 49 50 64 65 66 67 68 69 70 72 73 74 80 81 82 96 97 98.

I found that every number in the list above is of one of the forms

2^a, 2^a+2^b, 2^a+2^b+1, 2^a+2^b+2,

where a and b are non-negative integers. This leads me to conjecture that these forms contain all the initial values of n that produce an optimal configuration, however, this may be a case of The Strong Law of Small Numbers at work.

If how closely everyone is seated together makes you a bit uneasy in the graphs, we can expand the gap between people. For a fixed number of people in the bar, n=25, we vary the gap size, g to produce the following seating configurations:

The starred values indicate the best seat configuration. Compare these with the graph of gap size 2 earlier. Notice the best first seat varies between 1 and 9.

We can now plot the number of people seated compared to gap size:


A value is starred if the maximum number of people seated equals \lceil \frac{n}{g} \rceil. In this case, not only is length 25 optimal for a gap size of 2, but it’s optimal for every gap!

We wonder when this pattern will remain. Of the values of n above that were found to be optimal for a gap size of 2, the following are optimal for every gap size:

n=1 2 3 4 5 6 7 8 9 10 11 12 13 14 16 17 18 19 20 21 24 25 26 32 33 48 49.

An example of a value of n which gives suboptimal gap sizes is n=68:


The gap sizes of 3, 6, 7, and 9 are all suboptimal. This is the same for n=69 and 70. Similarly, for n=80, 81, and 82, we have suboptimal gap sizes of 3, 6, 7, and 11.

Since the gap size of 3 seems to produce suboptimal behaviour for several values, we plot the number of seats compared to the maximum number of seats for g=3:


The starred values indicate when the max number of people seated equals \lceil \frac{n}{3}\rceil. We see the initial part is a step function in threes, similar to g=2.


There is also a long valley around n=70 and n=80, as predicted above.

The full list of values of n that are optimal for g=3 are given below:

n=1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 24 25 26 27 28 29 30 31 32 33 36 37 38 39 48 49 50 51 52 53 54 55 56 57 60 61 62 63 72 73 74 75 96 97 98 99 100.

A few closing thoughts to the reader:

  • Can we characterize the values of n above similar to what we did for g=2?
  • Are any of these sequences on the Online Encyclopedia of Integer Sequences?
  • Has a full mathematical analysis been conducted? I’ve seen the XKCD Urinal Protocol Vulnerability, but this assumes the first person sits on the end.
  • Stay safe, and continue to practice social distancing everywhere you go!

Quick Divisibility Test for Primes up to 67

While there’s known divisibility tests for certain primes (see my notes), the following test very quickly determines if a number is divisible by any prime up to 67 by hand! The original method is due to John Conway, and I learned it from Arthur Benjamin.

Here’s a sample problem along with explanation:

63779 is the product of three primes, each less than 71. Determine their sum.

We set up the equation 63779=pqr, where p, q, and r are primes.

We begin by finding the factor of 2000 closest to 63, namely 64,000. We can therefore rewrite this as

221=2000\cdot 32-63,779.

We can quickly determine that since 2, 5\mid 2000 and 2, 5\nmid 221, 2, 5\nmid 63,779. We now add 32, the quotient in the divisibility above to both sides of the equation to produce:

253=2001\cdot 32-63,779.

Notice the factor of 32 and the left hand side have both increased, while our original number, 63779 has remained the same. Now, as any good contest math student should have the years close to the current year memorized, we know 2001=3\cdot 23\cdot 29. Therefore 3\mid 63779\iff 3\mid 253, however, 3\nmid 253. Similarly 23\mid 63779\iff 23\mid 253. This time, 253=23\cdot 11, therefore 23\mid 63779. We’ve found one prime divisor: p=23.

We could now divide 63779 by 23, however, this gives the equation 2773=qr, and we don’t have any better ideas for how to factorize 2773. Therefore, instead, we’ll use the prime factorizations of some other numbers close to 2000:

1998=2\cdot 3^3\cdot 37,   2002=2\cdot 7\cdot 11\cdot 13,   2006=2\cdot 17\cdot 59,   2009=41\cdot 49

and 2010=2\cdot 3\cdot 5\cdot 67,2013=3\cdot 11\cdot 61, 2015=5\cdot 13\cdot 31, 2021=43\cdot 47.

For instance, to determine if our number is divisible by 37, we would take the original equation and subtract 2\cdot 32 to produce 157=1998\cdot 32-63,779. Then, we know 37\mid 63779\iff 37\mid 157, however, clearly 37\nmid 157.

Similarly, to test if our number is divisible by 7, 11, or 13, we simply add 2\cdot 32 to our original equation to produce 285=2002\cdot 32-63779. Therefore, again 11\mid 285\iff 11\mid 63779, however, clearly 11\nmid 285, hence the same is true for 63779.

Next, to determine if the original number is divisible by 17 or 59, we add 6\cdot 32 to our original equation (or more simply, 4\cdot 32 to the equation in the last paragraph) to get

413=2006\cdot 32-63779.

Since 2006=2\cdot 17\cdot 59, we see 17\mid 413\iff 17\mid 63779, however, clearly 17\nmid 413. Similarly, 59\mid 413\iff 59\mid 63779. Now since 420=60\cdot 7, we see 413=59\cdot 7, hence 59\mid 413, and 59\mid 63779. We’ve therefore found a second prime factor: q=59.

At this point that we have two prime factors, we could continue on with our test, but we have a pretty good idea of what the third factor is by division: 63779=23\cdot 59\cdot r. One way to quickly compute this in our heads would be to notice

59\cdot 23=(60-1)(20+3)=1200+180-20-3=1357.

Since we know r is an integer, we attempt to bound it. We know r=\frac{63779}{1357}. We notice 40\cdot 1357=52480, while 50\cdot 1357=67850, therefore, 40<r<50.  We then subtract 40 from both sides of our equation:


While we could compute the numerator mentally, since we know 1\le r-40\le 9, we know it must be a single numerical digit! We therefore just consider the unit digit of the numerator which is 9. Since we’re dividing by a number which ends in 7, we know r-40 must be 7, since 7\cdot 7\equiv 49\equiv 9\pmod{10}. Therefore r=47.

Hence our desired sum is p+q+r=23+59+47=\boxed{129}.

Alternatively, we could verify 47\mid 63779 using the prime factorization of next year, 2021. I’ll leave this as an exercise for anyone interested.

While this method isn’t super practical, I think it’s interesting that you can essentially compute prime factors up to 67 with a quick trick in your head. The most difficult part is memorizing the prime factorizations of the numbers close to 2000, but hopefully this is familiar for any seasoned contest mathematician (who might be interested in using this).

References: Arthur Benjamin, Factoring Numbers with Conway’s 150 Method
The College Mathematics Journal, Vol. 49, No. 2, pp. 122-125, March 2018.

Similar to Fermat’s Last Theorem

Let n be a positive integer. Prove that there exist distinct positive integers x, y, z such that x^{n-1} + y^n = z^{n+1}. (Source: 1997 IMO Shortlist N6)

The equation x^{n}+y^n=z^n is known to have no nontrivial solutions for n\ge 3 due to Fermat’s Last Theorem (if you’ve not read Fermat’s Enigma I highly recommend checking it out). This very similar looking equation, however, has an infinite number of solutions. In this blog post, we’ll examine how this difficult looking problem can be solved with one simple observation: 1+8=9.

For a concrete example of this, consider the case n=3 giving the equation x^{2}+y^{3}=z^{4}. Assume we multiply the equation by a number of the form $2^{\alpha}\cdot 3^{\beta}$.  We then will have: $$2^{\alpha}\cdot 3^{\beta}+2^{\alpha+3}\cdot 3^{\beta}=2^{\alpha}\cdot 3^{\beta+2}.$$ Since we want the first part to be a perfect square, we should have $2\mid \alpha$ and $2\mid \beta$. Since the second part should be a perfect cube, we should have $3\mid (\alpha+3)$ and $3\mid \beta$. Finally, since the last part should be a perfect fourth power, $4\mid \alpha$ and $4\mid (\beta+2)$. Solving these system of linear congruences gives $\alpha=0$ and $\beta=6$! We get back the equation $3^6+3^6\cdot 2^3=3^8$, from which we read off the solution $(x,y,z)=(3^3, 3^2\cdot 2, 3^2)=(27, 18, 9)$

We now attempt to generalize this technique. We begin by multiplying 1+8=9 by 2^{\alpha}\cdot 3^{\beta} again to obtain 2^{\alpha}\cdot 3^{\beta}+2^{\alpha+3}\cdot 3^{\beta}=2^{\alpha}\cdot 3^{\beta+2}. We then want the exponents on the leftmost term to be divisible by n, on the middle term to be divisible by n+1, and on the rightmost term to be divisible by n+2. This is equivalent to:

\begin{cases} \alpha&\equiv 0\pmod{n} \\ \alpha&\equiv -3\pmod{n+1} \\ \alpha&\equiv 0\pmod{n+2} \end{cases}   and    \begin{cases} \beta&\equiv 0\pmod{n} \\ \beta&\equiv 0\pmod{n+1} \\ \beta&\equiv -2\pmod{n+2}. \end{cases}

Notice that in the first case, the first and third conditions are equivalent to \alpha\equiv 0\pmod{n(n+2)}. Since \gcd(n, n+2)=\gcd(n+1, n+2)=1, we can use the Chinese Remainder Theorem to know that \alpha has a unique solution mod \text{lcm}(n, n+1, n+2)

On the other hand, for \beta, in the case that n is even, \gcd(n, n+2)=2, therefore, we have to use an extended version of the Chinese Remainder Theorem. Thankfully, since \gcd(n, n+2)=2 in this case and 0\equiv -2\pmod{2}, we are still guaranteed a unique solution for \beta mod \text{lcm}(n, n+1, n+2).

Substituting these solutions in for \alpha and \beta gives a solution (x,y,z) to the original equation. Once we have the congruences for \alpha and \beta, we can then find an infinite parameterized version of solutions for (x,y,z).

For instance, in the case of n=3 above, we had \alpha\equiv 0\pmod{12}, \beta\equiv 6\pmod{12}. If we in general write \alpha=12\alpha' and \beta=12\beta'+6, we then find

2^{12\alpha'}\cdot 3^{12\beta'+6}+2^{12\alpha'+3}\cdot 3^{12\beta'+6}=2^{12\alpha'}\cdot 3^{12\beta'+8}.

This then translates into (x,y,z)=(2^{6\alpha'}\cdot 3^{6\beta'+3}, 2^{4\alpha'+1}\cdot 3^{2+4\beta'}, 2^{3\alpha'}\cdot 3^{3\beta'+2}). Notice for \alpha'=\beta'=0, this gives the solution triple (x,y,z)=(27, 18, 9) found above. 

It’s pretty interesting to me how when you change one small thing in the formulation of the problem (subtract 1 from the exponent on x and add 1 to the exponent of z) gives an entirely new problem, where we go from no solutions to an infinite number!

Puzzling Integral Solutions

At the falls clubs fair for the Mathematical Sciences Society at University of Alberta, we put up a poster board with two challenging integrals, offering free t-shirts to anybody who solved them. We put out several mini-whiteboards for people to work on, and to my surprise, there was quite a bit of interest (free tshirts are always a great motivator!). Here’s the solutions to two of these challenges. I really like how the first one looks symbolically challenging, but conceptually is not, while the second one looks more elementary, but involves a clever trick courtesy of Richard Feynman.

Link to Integral Solutions