# First digit of 3^2020

Inspired by The last digit for 3^(2019)

Can you find the first digit of 32020 without a computer?

• The hard thing is to post the answer here without using a computer. Apr 15 '20 at 19:14
• Can I choose the base of my answer? If it has to be 10, can it still be three? My answer is 1. Apr 16 '20 at 5:56
• I believe that there will be a pattern somewhere because I've calculated 33 numbers and there seems to be a pattern Apr 16 '20 at 7:52
• @UnidentifiedX there is no pattern. There's a mathematical proof for that. Observe that $a\cdot 10^k < 3^n < (a+1)\cdot 10^k$ means that the first digit is $a$, taking $\log=\log_{10}$ we see that $\log a + k < n \log 3 < log(a+1) + k$. Now consider the fraction part, we see that the first digit is $a$ iff $\{ n \log3\} \in (\log a, \log(a+1))$. However $\log 3$ is an irrational number and therefore $\{n\cdot \log 3\}$ uniformly distributing in $(0,1)$. (All first digits appear, randomly with different distribution. The probability that $a$ appears is $\log(a+1)-\log(a)$). Apr 16 '20 at 14:37
• @KamilMaciorowski if we can choose the base, then I will take base two. The first digit is 1. Apr 16 '20 at 14:54

I think it's a

6

Explanation:

$$3^{2020} = 10^{\log_{10}(3^{2020})} = 10^{2020 \log_{10}3}$$

According to my calculator (this answer was posted before the tag was added),

$$2020 \log_{10}3 = 963.784934533718123$$ and $$10^{963.784934533718123} = 10^{963} \times 10^{0.784934533718123} = 10^{963} \times 6.094450215462886$$ Multiplying by $$10^{963}$$ doesn't influence the first digit, only the 'length', so the answer is 6.

If we're not allowed to use computers, I would

still use the same trick. $$\log_{10}3$$ is common enough to be listed in a logarithm table, I must have one in my library. Multiplying by 2020 is doable by hand, and it's easy to verify with the logarithm table that the fractional part (0.785) lies between $$\log_{10}6$$ and $$\log_{10}7$$, so the first digit must be a 6.

The same trick is used to solve similar questions on our sister site Mathematics: Finding the first digit of $$2015^{2015}$$ and What's the first digit of 2410^2410?

• The result is correct
– Qiu
Apr 15 '20 at 11:51
• It should be possible to find $\log_{10} 3$ to sufficient precision without a table by expanding $\log_{10}$ around $\sqrt{10}$. Apr 16 '20 at 2:26
• @R..GitHubSTOPHELPINGICE wouldn't that shift the problem to finding $\sqrt{10}$ with sufficient precision (which is admittedly easier, but still)? Feel free to write your own answer, by the way; it's quite common on Stack Exchange (and especially on Puzzling) to base answers off one another. Apr 16 '20 at 6:04
• @Glorfindel: Finding sqrt with arbitrary precision is just binary search and square (multiply). Apr 16 '20 at 14:46
• @Glorfindel There are plenty of techniques for finding roots by hand. You could probably find one for log too; but for square roots it's fairly trivial and a really well studied problem.
– JMac
Apr 16 '20 at 15:01

This is one way to do it with the help of binary numbers. It is called exponentiation by squaring.

EDIT
Thanks to the few comments that pointed out the mistakes in my calculations. I was very lucky to get the right answer. While revising, I also noticed a mathematical mistake that explains why I need 4 digits to get the right answer. I'll leave the old answer, then explain why it didn't work. And finally, I'll add a new answer that works.

First, $$2020$$ is $$11111100100$$ in binary. So $$3^{2020}=3^{1024}3^{512}3^{256}3^{128}3^{64}3^{32}3^{4}$$ Now we find $$3^{2^n}$$, by squaring the previous one. $$\begin{array}n&3^{2^n}&\text{value}\\0&3^1&3\\1&3^2&9\\2&3^4&81\\3&3^8&6561\end{array}$$ Starting from $$3^8$$ the values are too big, we keep only the first three digits. By doing so, we have a relative error of less than one in a thousand. We have about 20 multiplications to do, so the relative error of the answer will be less than 2%. $$\begin{array}n&3^{2^n}&\text{first 3 digits rounded}\\0&3^1&3\\1&3^2&9\\2&3^4&81\\3&3^8&656\\4&3^{16}&430\\5&3^{32}&185\\6&3^{64}&342\\7&3^{128}&117\\8&3^{256}&137\\9&3^{512}&188\\10&3^{1024}&353\end{array}$$ To find the final value, we multiply the one we need \begin{align}3^{2020}&=3^{1024}3^{512}3^{256}3^{128}3^{64}3^{32}3^{4}\\3^{2020}&=(353)(188)(137)(117)(342)(185)(81)\\3^{2020}&=545\ldots\end{align} The first digit of $$3^{2020}$$ is $$5$$ (wrong).

Why it didn't work

My mistake is when I check the relative error. The relative error on $$3^8$$ is around 0.1%. Then, the error doubled every time I squared. Since I squared 7 times, the relative error of $$3^{1024}$$ is around 12.8%, which is way too high. We need a fourth digit to find the answer.

New version

First, $$2020$$ is $$11111100100$$ in binary. So $$3^{2020}=3^{1024}3^{512}3^{256}3^{128}3^{64}3^{32}3^{4}$$ Now we find $$3^{2^n}$$, by squaring the previous one.

Now if we keep 4 digits for every number, we have $$\begin{array}n&3^{2^n}&\text{first 4 digits rounded}\\0&3^1&3\\1&3^2&9\\2&3^4&81\\3&3^8&6561\\4&3^{16}&4305\\5&3^{32}&1853\\6&3^{64}&3434\\7&3^{128}&1179\\8&3^{256}&1390\\9&3^{512}&1932\\10&3^{1024}&3733\end{array}$$ To find the final value, we multiply the one we need \begin{align}3^{2020}&=3^{1024}3^{512}3^{256}3^{128}3^{64}3^{32}3^{4}\\3^{2020}&=(3733)(1932)(1390)(1179)(3434)(1853)(81)\\3^{2020}&=60919\ldots\end{align} The first digit of $$3^{2020}$$ is $$6$$.

Conclusion

This method works, but could need a lot of work. I did it by hand (and double checked with a spreadsheet) before posting, since there is a tag.

Since the real value of $$3^{2020}$$ is $$6.0945\times10^{963}$$, we need a relative error below 1% to find the right answer. We may need to verify our answer by keeping 5 digits.

EDIT 2 Suggestion from @DidierL.

As suggested in the comments, we could use a division to reduce the multiplications by one. $$3^{2020}=\frac{3^{2048}}{3^{16}3^83^4}$$ $$3^{2048}$$ start with $$13935$$, with the same logic as before. And $$3^{16}3^83^4=(4305)(6561)(81)=2288$$ Keeping only the first four digits. Finally $$13935\div2288=60904\ldots$$ Once again, I tried it by hand (double check with calculator) before posting.

• This technique is also called exponentiation by squaring. Apr 15 '20 at 17:11
• @2012rcampion thank's, I'll add it to my answer. Apr 15 '20 at 17:49
• @Glorfindel you are right. I'll post an updated answer soon. Apr 15 '20 at 21:28
• Also, squaring 118... would give 137...ish, not 103... Apr 15 '20 at 21:42
• You could trade 3 multiplications for a division by computing 3^2048 / 3^(16+8+4). As you are only interested in the first digit, you don't even need to compute the full division. Apr 16 '20 at 15:08

With no computers and a calculator used only to check some easy arithmetic:

First of all, calculate some small powers of $$3$$ looking for things that might be easy to work with. I notice that $$3^{13} = 1594323$$ which is close to $$1600000$$, and powers of $$2$$ and $$10$$ are nice. The relative error is about $$5000/160000$$ or $$1/320$$.

In particular, $$2^{10}$$ is approximately a power of $$10$$. So let's take the fifth power, so we get $$3^{65} \approx 16^5 \cdot 10^{25} \cdot \left(1-\frac 1{320}\right)^5 \approx 2^{20} \cdot 10^{25} \cdot \left(1-\frac 1{64}\right)$$. And we know that $$2^{20} = 1048576 \approx 10^6 \cdot (1+0.0486)$$, so $$3^{65} \approx 10^{31} \cdot 1.033 \approx 10^{31} \cdot \left(1+\frac 1{30}\right)$$. (Why $$1.033$$? Because $$1/64 = 0.015625$$; multiplying number near $$1 \approx$$ adding differences from $$1$$, and $$0.0486-0.0156 = 0.033$$.)

That factor of $$1+1/30$$ is a bit of a nuisance. What can we do with it? Well, it's well known that $$(1+1/n)^n$$ is roughly $$e$$ for largeish $$n$$. So let's take the $$30^\text{th}$$ power, which conveniently comes close to $$2020$$: $$3^{1950} \approx 10^{930}e$$. This is a slight overestimate because $$0.033$$ is a little smaller than $$1/30$$ and because $$(1+1/n)^n$$ is a little smaller than $$e$$.

We're $$70$$ short, and we happen to have something pretty good for $$65$$, so let's multiply by $$3^{65}$$. $$3^{2015} \approx 10^{961}(1+1/30)e$$ And $$3^5$$ is a nice small number so let's just throw that in: $$3^{2020} \approx 10^{961} * \left(1+\frac 1{30}\right)e(243) \approx 10^{963}\left(1+\frac 1{30}\right)e(2.43)$$

Finally, just do some arithmetic. $$2.72 \times 2.43 \approx 5.44 \times 1.21 \approx 5.44 + 1.09 \approx 6.5$$ (because $$.2 = 1/5$$); the $$1+1/30$$ factor turns this into about $$6.7$$.

None of that was super-accurate, but the most estimate-y bit of it is known to be an overestimate and I don't see any way we could be out by more than $$+0.3$$ or $$-0.7$$. So the first digit is $$6$$. (Which indeed it turns out to be, and indeed this was an overestimate; the number actually begins $$60944$$.)