The computer can't do anything I couldn't do with pen and paper

Question

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.

Answer 1

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.

Answer 2

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.

$$ \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:

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

Answer 3

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

Answer 4

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.

Answer 5

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.

Answer 6

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

Answer 7

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!

Answer 8

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.

Answer 9

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

Answer 10

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.

Answer 11

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}$

Answer 12

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}$

Answer 13

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

Answer 14

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.

Answer 15

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