14
$\begingroup$

If you want to know how much $3^{100}$ is, you can just type it into a computer and it will spit out a really big number. But that is no fun. The task is to estimate $3^{100}$ with some computation which can be checked and followed without computer aid and that can be written down on at most one sheet of paper (theoretically one could compute the exact number on paper but that is no fun either and certainly wouldn't fit on a single sheet).

Answers should be in the form of scientific notation (something like $3.45 \cdot 10^{7}$) and be within $\pm 50\%$ of the exact value which my computer tells me is around

$5.15377*10^{47}$

but just getting the correct number of digits is already non trivial.

$\endgroup$
3
  • 4
    $\begingroup$ Am I allowed to use the fact that as a child, I memorised the base-10 logarithms of the numbers from 2 to 10, to 4 decimal places? That allows me to instantly know the first digit of the answer, and how many digits there are. $\endgroup$ Oct 6, 2022 at 3:23
  • $\begingroup$ hold up.... fljx's answer is great, but how can we know it's within 50% of the exact value without a calculator? Or is that not part of the challenge? $\endgroup$
    – Wyck
    Oct 6, 2022 at 19:53
  • $\begingroup$ @Wyck One can estimate the error by hand, at least close enough to prove that it is within the 50% bounds. I will write a comment there. $\endgroup$
    – quarague
    Oct 7, 2022 at 7:22

15 Answers 15

40
$\begingroup$

An elementary approach:

$3^{100} = 9^{50} = 81^{25}$
$ \approx 80^{25}$

$ = 8^{25} \cdot 10^{25}$
$ = 2^{75} \cdot 10^{25}$
$ = (2^{10})^7 \cdot 2^5 \cdot 10^{25}$
$ = 1024^7 \cdot 32 \cdot 10^{25}$
$ \approx 1000^7 \cdot 32 \cdot 10^{25}$

$ = 10^{21} \cdot 32 \cdot 10^{25}$
$ = 32 \cdot 10^{46}$
$ = 3.2 \cdot 10^{47}$

Which is within the required margin, and could be improved by compensating for the two rounding steps.

$\endgroup$
1
  • 2
    $\begingroup$ One can prove this answer is within the required 50% bound without computers as follows. The first rounding is 1.25% to low and applied 25 times, the second rounding is 2.4% to low and applied 7 times. To first order approximation this answer is 25*1.25%+7*2.4%=37.5%+16.8%=44.3% too low. One can either stop there and say within 50% or use that to arrive at the much closer guess of 5.75*10^47. $\endgroup$
    – quarague
    Oct 7, 2022 at 7:28
43
$\begingroup$

Not sure if this counts as "pencil-and-paper" but certainly counts as "no computer..."

$$ 3^{100} = 10^{100 \log 3} $$

We can compute this logarithm using a slide rule. The D and L scales are related by $L = \log D$, so lining up the cursor with a number on the D scale shows its logarithm on the L scale.

a slide rule showing the computation of log 3

close up of the previous picture; with the cursor at 3 on the D scale, it is between the .476 and .478 tick marks on the L scale

$$ \log 3 \approx 0.477 \\ 100 \log 3 \approx 47.7 \\ 3^{100} \approx 10^{47.7} = 10^{0.7} \times 10^{47} $$

We can of course compute the antilog on the slide rule as well:

the slide rule with the cursor at .7 on the L scale, showing a hair over 5 on the D scale

$$ 10^{0.7} \approx 5 \\ \boxed{3^{100} \approx 5 \times 10^{47}} $$

$\endgroup$
4
  • $\begingroup$ This is nice, there is a reason they had these gadgets in pre computer days. What do you call them? I've seen them but forgot the name. $\endgroup$
    – quarague
    Oct 4, 2022 at 16:50
  • 18
    $\begingroup$ That gadget is called a slide rule. Until the mid 1970s or so, it was a more-or-less mandatory piece of equipment for anyone who did complex calculations regularly. $\endgroup$ Oct 4, 2022 at 17:41
  • $\begingroup$ They come in a (paper) tabular version too -- the standard logarithm tables. Which ash4fun has already shown what they look like. $\endgroup$
    – Ben Voigt
    Oct 4, 2022 at 21:33
  • $\begingroup$ I used one. But my log and antilog were table. $\endgroup$
    – Joshua
    Oct 7, 2022 at 17:56
29
$\begingroup$

Let's solve this problem using ... music!

An octave is a pair of notes whose frequencies are in a ratio of 2:1, while a perfect fifth is a pair of notes whose frequencies are in a ratio of 3:2 or $\frac32$. On a piano, if we start on a low note and jump up 12 perfect fifths, we'll find ourselves 7 octaves above where we started. Now the frequency ratio of a piano's perfect fifth is slightly imperfect, but it's close enough because of the mathematical approximation $(\frac32)^{12} \approx 2^7$ (the former is about 1.4% larger than the latter); and indeed the fact that 12 perfect fifths is super close to 7 octaves helps us remember the approximation $(\frac32)^{12} \approx 2^7$.

Because of this,

we see that $3^{12} \approx 2^{19}$, so that $3^{100} = 3^4\times(3^{12})^8 \approx 3^4\times(2^{19})^8 = 81\times2^{152}$.

But also,

the fact that $2^{10} = 1024 \approx 10^3$ tells us that $81\times2^{152} = 81\times2^2\times(2^{10})^{15} \approx 81\times2^2\times(10^3)^{15} = 324\times10^{45} \approx 3\times10^{47}$. We had various sources of error, but they were individually small enough that we stayed close enough to the true value of approximately $5\times10^{47}$.

$\endgroup$
2
  • $\begingroup$ The most creative way to do it! $\endgroup$
    – justhalf
    Oct 6, 2022 at 8:05
  • $\begingroup$ This is the approach I thought of as soon as I saw the puzzle. Treating 2^10 as 1000 will introduce an errors of 2.4%, respectively, which may be compensated using economists' "Rule of 72", which says that (1+x/100)^k is about 2^(k/72). So compensating for approximating 2^10 as 1000, 15 times, would require scaling by about 2^(30/60). $\endgroup$
    – supercat
    Oct 6, 2022 at 18:23
19
$\begingroup$

I took an extra challenge to solve this in my head without writing.

$3^{100} = 9^{50} = 10^{50} \left(1-\frac{1}{10}\right)^{50} = 10^{50} \left(\left(1-\frac{1}{10}\right)^{10}\right)^5$

From here, we can use that

$\left(1-\frac{1}{n}\right)^{n} \to \frac{1}{e}$ as $n \to \infty$ to approximate $\left(1-\frac{1}{10}\right)^{10} \approx \frac{1}{e}$ leaving us with $3^{100} \approx \frac{10^{50} }{e^5}$.

Now

with a lazy approximation of $e \approx 3$ and so $e^5 \approx 3^5 \approx 250$, we get $3^{100} \approx \frac{10^{50} }{250} = \frac{10^{50} }{10^3 / 4} = 4 \times 10^{47}$

which is quite close to the true value.

$\endgroup$
1
  • 1
    $\begingroup$ Perhaps you could also use the (well known?) fact that $e^3=20$ with an error of less than $\frac12$%. $\endgroup$
    – David
    Oct 6, 2022 at 23:02
16
$\begingroup$

This seems like a perfect application for

Logarithm tables!

Looking at

The value for $\log_{10} 3$, (row 30, column 0, no adjustment), we get approximately 0.4771.
Using the properties of logarithms:
$$\log_{10}3^{100}\\=100\log_{10}3\\=100\cdot0.4771\\=47.71$$

Now for the inverse operation:

We want to find $10^{47.71}$:
$$10^{47.71}=10^{47}\cdot10^{0.71}$$ Looking in our tables for the number whose logarithm is 0.71, we find it at row 51, column 2, with an adjustment of 7 from column 8. Thus $10^{0.71}=5.128$.

Bringing it all together,

$$3^{100}=5.128\times10^{47}$$

Error analysis:

My answer is off by 0.5%. Looking at the true answer, we can see that its mantissa is 0.7121, whereas we only had the mantissa to a precision of 0.71.
By looking at values with a mantissa between 0.705 and 0.715, we could get a small range of $[5.070\times10^{47},5.188\times10^{47}]$, guaranteed to contain the true value.

$\endgroup$
2
  • $\begingroup$ That is exactly the answer I planned to give. I was thinking not many people still know that a thing like log tables even existed. $\endgroup$
    – Florian F
    Oct 5, 2022 at 6:49
  • $\begingroup$ And those of us who went to school during the era of log tables & slide rules (probably) don't even need to look at tables for the logs of 2 or 3. ;) $\endgroup$
    – PM 2Ring
    Oct 5, 2022 at 10:27
11
$\begingroup$

Simple approach... I don't find a simple way to quantify the error:

My proposal is $6.144*10^{47}$, here is how I found it:

Let's compute first powers of 3, to find something near 10 or 100 or ...
3, 9, 27, 81, 243, 729 (Those one we know by heart)
2187, 6561, 19683, ...
ok, $3^9$ is not far from $20000=2*10^4$
So $3^{100} = 3*3^{99} = 3* (3^9)^{11}$ is not far from $3* (2*10^4)^{11}$
$(2*10^4)^{11} = 2048 * 10^{44} = 2.048 *10^{47}$
So $3^{100}$ is not far from $3*2.048*10^{44}=6.144*10^{47}$
Real value is $(19863/20000)^{11} * 6.144*10^{47}$
As said above, I don't find an easy way to quantify this $(19863/20000)^{11}$ except doing the multiply 10 times...

$\endgroup$
1
  • $\begingroup$ I can give you a hint for your last bit. You can write that term as $(1/2-a)^{11}$ with $a$ very small. So it is almost the same as $(1/2)^{11}$. You can estimate the error or just leave it as 'small'. $\endgroup$
    – quarague
    Oct 4, 2022 at 13:43
10
$\begingroup$

Second answer, using exponentiation by squaring and one (!) digit of precision:

$$ \begin{align} 3^{1} &= 3 \\ 3^{2} &= 3^{2} = 9 \\ 3^{4} &= 9^{2} = 81 \approx 8 \times 10^{1} \\ 3^{8} &\approx (8 \times 10^{1})^2 = 64 \times 10^{2} \approx 6 \times 10^{3} \\ 3^{16} &\approx (6 \times 10^{3})^{2} = 36 \times 10^{6} \approx 4 \times 10^{7} \\ 3^{32} &\approx (4 \times 10^{7})^{2} = 16 \times 10^{14} \approx 2 \times 10^{15} \\ 3^{64} &\approx (2 \times 10^{15})^{2} = 4 \times 10^{30} \end{align} $$

$$ \begin{align} 3^{100} &= 3^{64} \times 3^{32} \times 3^{4} \\ &\approx (4 \times 10^{30}) \times (2 \times 10^{15}) \times (8 \times 10^{1}) \\ &= 4 \times 2 \times 8 \times 10^{46} \\ &= 64 \times 10^{46} \approx \boxed{6 \times 10^{47}} \end{align} $$

The results is off by 20%, which is pretty good considering at one point we rounded 1.6 to 2!

$\endgroup$
7
$\begingroup$

Note first of all that

$3^2 = 9$ which isn't too different from 10. So $3^{100} = 9^{50} = 10^{50} . (9/10)^{50}$. So we need to estimate $(9/10)^{50}$.

Well,

this is $(1-1/10)^{50} = \exp 50 \log (1-1/10)$. And we know that $\log (1-x) = -x-x^2/2-\cdots$. The first term should be enough for our purposes: $\log (1-1/10) = -1/10 + \varepsilon$ where, say, $|\varepsilon|<1/150$.

Now

that factor is $\exp (5+\delta)$ where $|\delta|=50|\varepsilon|<1/3$ and so $\exp\delta$ isn't going to incur an error bigger than a factor of 2. So the question now is to estimate $\exp 5$.

At this point

it's fair to assume we know $e=2.718...$ and compute the fifth power of this by hand. $2.7^2=7.29$; the actual value of $e$ is about $1+2/300$ times as big as $2.7$ which means that the value of $e^2$ is about $1+4/300$ times as big as $7.29$, so bigger by about $0.0972$; let's overestimate slightly and call it $7.4$. The square of that is $49+5.6+0.16=54.76$; multiplying this by $2.7$ (an underestimate) gives $109.52+38.332\simeq148$. So the number we're looking for shouldn't be too far from $10^{50}/148$. We're being pretty crude here so let's call it $10^{50}/150=\frac23\cdot10^{48}\simeq6.7\times10^{47}$.

The errors here are at most about

$\exp 1/3$ times various couple-of-percent factors

so comfortably within the requested factor of 2.

$\endgroup$
2
  • 1
    $\begingroup$ What I had in mind was quite similar but I got closer to the true value with less computation. So definitely +1 but I will wait with the check mark to see whether there are more attempts. $\endgroup$
    – quarague
    Oct 4, 2022 at 11:37
  • $\begingroup$ Other approaches are definitely possible. I might post one myself :-). $\endgroup$
    – Gareth McCaughan
    Oct 4, 2022 at 14:19
7
$\begingroup$

Pretty similar to other solutions:

$3^{10} = 9^5$
$9^n = 9, 81, 729, 6561, 59048$. (Can be done on paper, or even in the head)
$3^{10} = 59048 \approx 6 \times 10^4$
$3^{100} \approx 6^{10} \times 10^{40} = 2^{10} \times 3^{10} \times 10^{40} \approx 10^{3} \times (6 \times 10^4) \times 10^{40} = 6 \times 10^{47}$

To refine the calculation, I use that between $6$ and $5.9$ there is a factor of $(1 - {1\over 60})$.
Correcting that 11 times I have to multiply my result by
$(1 - {1\over 60})^{11} \approx (1 - {11 \over 60}) = {49 \over 60}$

This gives a better approximation: $4.9 \times 10^{47}$.

$\endgroup$
5
$\begingroup$

I already posted one approach. Several others are possible. Here's one that gives a pretty accurate result. It's similar in spirit to my other answer.

First of all note that $3^{100}=81^{25}$. We'll write that as $80^{25}\cdot(1+1/80)^{25}$ and handle the two factors separately.

Now

$80^{25}=2^{75}10^{25}=32\cdot1024^7\cdot10^{25}=32\cdot(1+24/1000)^{7}\cdot10^{46}$.

So

$3^{100}=3.2\times10^{47}\cdot(1+24/100)^{7}\cdot(1+1/80)^{25}$.

We can already

remark that the second and third factors are modest in size and declare victory

but

might choose to get a bit closer. Simplest is to say $(1+x)^n\simeq1+nx$, with errors of order $\frac12n^2x^2$, getting $3.2\times10^{47}\times1.168\times1.3125\simeq4.9\times10^{47}$, good to within a few percent. If we want better, we can take the next terms in the binomial expansions or play some more fun and games with exponentials and logarithms.

$\endgroup$
1
  • 2
    $\begingroup$ Note: if you stop at the "declare victory" stage, this is the same as fljx's answer which was posted earlier than this one. Anyone who feels any inclination to upvote this one should consider upvoting fljx's, either instead or as well. $\endgroup$
    – Gareth McCaughan
    Oct 4, 2022 at 15:13
3
$\begingroup$

Short and rough:

$3^5=243\approx 250 = 10^3/2^2$
So $3^{100}\approx (10^3/2^2)^{20} = 10^{60}/2^{40}$
But $2^{10}=1024\approx 10^3$
So $2^{40}\approx 10^{12}$
Hence $3^{100}\approx 10^{48}$

$\endgroup$
3
  • $\begingroup$ That is very close to the solution I had in mind when I wrote the question. If you make some estimates of the error terms when rounding you can get that to within 10% of the exact answer. $\endgroup$
    – quarague
    Oct 5, 2022 at 11:32
  • 1
    $\begingroup$ Also nice is that this answer is an upper bound, it could be combined with the lower bound of the 81 based answers. $\endgroup$
    – Retudin
    Oct 5, 2022 at 11:37
  • $\begingroup$ FWIW, the 1st estimate that popped into my head was $5×10^47$, since $\log3=.4771$ and $\log2=.3010$ are indelibly burnt into my neural circuitry. ;) I was going to post a solution based on $(3/2)^{12}\approx2^7$, but Greg Martin beat me to it. $\endgroup$
    – PM 2Ring
    Oct 5, 2022 at 11:52
3
$\begingroup$

Another 80 based solution.

Knowing that by very good approximation $2^{10} = 10^3$ i.e. $2=10^{0.3}$ a decent approximation is $3^4 = 81 > 10*8 > 10^{1.9}$.
Then $3^{100} \approx 10^{25*1.9} = 10^{47.5}$
Rounding up $sqrt(10) \approx 4$ (since the approximation is known to be smaller) I get to $ 4*10^{47}$

$\endgroup$
2
$\begingroup$

I learned in surely you're joking mister Feynman, that one of the most powerful tools for mental arithmetic is to know some logarithms by heart. In particular with the logarithms of 2, 3, 5, 7 and 10, as well as the properties of the logarithm and the exponential you can get very far. With the precision you're asking for it is not even needed to know these logarithms with very high precision. We just need the following:

  • $\log 3 \approx 1.1$
  • $\log 10 \approx 2.3$
  • $\log 5 \approx 1.6$

Then

$$3^{100} = e^{100\log3} \approx e^{110}.$$

Now

$$110 = 2.3 \times 47 + 1.9 \approx 47\log 10 + \log 5 + 0.3,$$

and $e^{0.3} = 1 + 0.3 + 0.09/2 + \cdots \approx 1.35$, giving the approximation

$$3^{100} \approx 1.35\times 5\times 10^{47} = 6.75 \times 10^{47}.$$

$\endgroup$
1
$\begingroup$

Finding the powers of 11 doesn't count as intense computation, because the long multiplication involves adding two adjacent numbers and carrying the ones when needed. So we get $11^7/10^7 < 2$ and $11^8/10^8 > 2$. The ratio between the powers of 10 and 9 is even greater.

$3^7 = 2187$ => $441*10^4 < 9^7 < 484*10^4$
$(441+484)/2*10^4 < 9^7 < 484*10^4$
$462*10^4 < 9^7 < 484*10^4$
$9^7*2 < 10^7$
$9^{49}*2^7 < 10^{49} < 9^{49}*2^8$
$10^{49}/2^8 <9^{49} <10^{49}/2^7$
$10^{49}*9/2^8 <9^{50} <10^{49}*9/2^7$

$9*10^{49}$ is 50 digits long, so when it's divided by 128 or 256, it's 48 digits long. The power in the scientific notation must be $10^{47}$. The number's first digits can range from $3515625$ to $7031250$, so $5*10^{47}$ is a safe guess.

$\endgroup$
0
1
$\begingroup$

An interesting technique:

$3^{100}=10^{100\log_{10}3}=10^{100/\log_3 10}$

Now, $\log_3 10 = \log_3 (3^2\times \frac{10}9)$

What we want, here, is a reasonable approximation for $\log_3 \frac{10}9$. We can work this out by noting that, if our approximation is $\frac1x$, then $\left(\frac{10}9\right)^x\approx3$. To put it another way, $10^x\approx3^{2x+1}$. Note that this is actually just another restatement of our initial expression.

This narrows our search parameters nicely - essentially, at what power of 3 does the result end up one power of 10 below expectation from the approximation $3^2\approx10$? Note that odd powers of 3 are what we need to look at.

Well, let's go searching. $3^4=81$, so $3^8=6561$, and $3^9=19683$. This is close to a nice number, so let's use it. $3^9\approx2\times10^4$. Now, we get $3^{18}\approx4\times10^8$, and so $3^{19}\approx12\times10^8$. Still a little too high. Multiplying by 9 gives $3^{21}\approx108\times10^8$, so we're close. Multiplying by 9 again gives $3^{23}\approx972\times10^8<10^{11}$. From this, we can conclude that $10<x<11$. Given the values, and the fact that we rounded up a little along the way, let's use $x\approx10.5$.

Note: the true value is approximately 10.43
So we have $3^{100}\approx10^{100/(2+1/10.5)}$. Now, the power of 10 is $525/11$, which is $47+8/11$.

And finally, we have what we need: $3^{100}\approx10^{8/11}\times10^{47}$. We do have one remaining task - estimating $y=10^{8/11}$. So $y^{11}=10^8$, and since it's easy enough to approximate small powers... if $y=5$, we have $5^5\approx3\times10^3$, and so $5^{11}\approx4.5\times10^7$, and thus too small. If $y=6$, we have $6^5\approx8\times10^3$, and so $6^{11}\approx4\times10^8$, and thus too large. So $5<y<6$.

A slightly different version of the same idea can be done by using an intermediate result more directly...

We determined that $3^{21}\approx10^{10}$ and $3^{23}\approx10^{11}$ (and they bound the powers of 10) - combining these, we have $3^{44}\approx10^{21}$, and so $3^{100}=3^{12}\times3^{88}\approx3^{12}\times10^{42}$. And since $3^{12}=3^4\times3^8$, we have $3^{12}\approx80\times6400=512000=5.12\times10^5$.

Combining these, we have $3^{100}\approx5.12\times10^{47}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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