33
$\begingroup$

Inspired by The last digit for 3^(2019)

Can you find the first digit of $3^{2020}$ without a computer?

$\endgroup$
  • 48
    $\begingroup$ The hard thing is to post the answer here without using a computer. $\endgroup$ – Florian F Apr 15 at 19:14
  • 5
    $\begingroup$ Can I choose the base of my answer? If it has to be 10, can it still be three? My answer is 1. $\endgroup$ – Kamil Maciorowski Apr 16 at 5:56
  • 1
    $\begingroup$ I believe that there will be a pattern somewhere because I've calculated 33 numbers and there seems to be a pattern $\endgroup$ – UnidentifiedX Apr 16 at 7:52
  • 4
    $\begingroup$ @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)$). $\endgroup$ – Yanko Apr 16 at 14:37
  • 9
    $\begingroup$ @KamilMaciorowski if we can choose the base, then I will take base two. The first digit is 1. $\endgroup$ – Džuris Apr 16 at 14:54
39
$\begingroup$

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?

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ The result is correct $\endgroup$ – Qiu Apr 15 at 11:51
  • $\begingroup$ It should be possible to find $\log_{10} 3$ to sufficient precision without a table by expanding $\log_{10}$ around $\sqrt{10}$. $\endgroup$ – R.. GitHub STOP HELPING ICE Apr 16 at 2:26
  • 2
    $\begingroup$ @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. $\endgroup$ – Glorfindel Apr 16 at 6:04
  • $\begingroup$ @Glorfindel: Finding sqrt with arbitrary precision is just binary search and square (multiply). $\endgroup$ – R.. GitHub STOP HELPING ICE Apr 16 at 14:46
  • 1
    $\begingroup$ @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. $\endgroup$ – JMac Apr 16 at 15:01
34
$\begingroup$

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

EDIT Thank's 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 explain 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 answer (wrong one)

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 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 DOUBLE 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 numbers, 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 spreadsheets) before posting, since there is a no-computer 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.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ This technique is also called exponentiation by squaring. $\endgroup$ – 2012rcampion Apr 15 at 17:11
  • $\begingroup$ @2012rcampion thank's, I'll add it to my answer. $\endgroup$ – Alain Remillard Apr 15 at 17:49
  • $\begingroup$ @Glorfindel you are right. I'll post an updated answer soon. $\endgroup$ – Alain Remillard Apr 15 at 21:28
  • $\begingroup$ Also, squaring 118... would give 137...ish, not 103... $\endgroup$ – Glorfindel Apr 15 at 21:42
  • 2
    $\begingroup$ 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. $\endgroup$ – Didier L Apr 16 at 15:08
14
$\begingroup$

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$.)

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.