27
$\begingroup$

With a computer or calculator, it is easy to show that $$ 2^{2^\sqrt{3}} = 10.000478 \ldots > 10. $$

How can we prove that $2^{2^{\sqrt3}}>10$ without a calculator?

$\endgroup$
  • 18
    $\begingroup$ Considering that $2^{2^{\sqrt{3}}} \approx 10.000478\ldots$ is very close to $10$, this will be quite a challenge. $\endgroup$ – JimmyK4542 Dec 28 '14 at 7:22
  • 8
    $\begingroup$ What does that even mean? It sounds to me ill-posed... the calculator doesn't do anything magical that I couldn't also do (laboriously) by hand: computing logarithms with proven error bounds using series, etc... $\endgroup$ – user7530 Dec 28 '14 at 7:24
  • 12
    $\begingroup$ My comment wasn't meant to be taken as a solution. I was simply pointing out that this would be a difficult task. $\endgroup$ – JimmyK4542 Dec 28 '14 at 7:25
  • 14
    $\begingroup$ What contest is this? $\endgroup$ – user7530 Jan 9 '15 at 6:28
  • 3
    $\begingroup$ I didn't use a calculator in my answer! I think the meaning is clear, and the problem is entertaining. $\endgroup$ – copper.hat Jan 9 '15 at 22:17
18
$\begingroup$

I suspect any adequate answer to this question is going to be very computation-heavy. Here's one.

First we claim that $$ \sqrt{3} > \frac{3691}{2131} \tag{1} $$ This fraction is not pulled out of a hat; rather, it is found by taking the continued fraction $\sqrt{3} = [1; 1, 2, 1, 2, 1, 2, \ldots]$ and carrying it out a while. Anyway, the above is proved directly by $$ 3 \cdot 2131^2 = 3 \cdot 4541161 = 13623483 > 13623481 = 3691^2. $$

We next claim that $$ 2^{{3691}/{2131}} > \frac{1465}{441} \tag{2} $$

To prove this, one needs to show $2^{3691} 441^{2131} > 1465^{2131}$. With repeated squaring, each term requires squaring about $12$ times, so this is doable$^{a}$ with a pencil and paper.

The last step is $$ 2^{1465/441} > 10 \tag{3} $$ Again one uses repeated squaring, and if one is working in base 10 one only needs to count the number of digits in $2^{1465}$. This should not take nearly as long as the previous computation.$^{b}$

From (1), (2), and (3), $$ 2^{2^{\sqrt{3}}} > 2^{2^{3691/2131}} > 2^{1465 / 441} > 10. \quad \square $$


$^{a}$ Honestly, this is quite a stretch. I can't guarantee it won't take like a year of work.

$^{b}$ As a rough estimate, perhaps a day or so.

$\endgroup$
  • 1
    $\begingroup$ Why is it obvious that any adequate answer would be computation-heavy? Do you have a proof lying around somewhere? :-P $\endgroup$ – Aryabhata Jan 9 '15 at 2:39
  • 1
    $\begingroup$ Well, then don't claim that $\pi + e$ isn't rational. $\endgroup$ – Aryabhata Jan 9 '15 at 2:44
  • 3
    $\begingroup$ @Aryabhata I am not at all optomistic that a proof could be found. It would involve proving that any proof of $2^{2^{\sqrt{3}}}$ must be sufficiently long. And once you start talking about all proofs of a statement, you are venturing into territory where many things are provably undecidable. $\endgroup$ – 6005 Jan 9 '15 at 2:45
  • $\begingroup$ You are missing the fact that this is a contest problem. If this was something someone just noticed while playing with a calculator, then there would be good reason to be skeptical. $\endgroup$ – Aryabhata Jan 9 '15 at 2:47
  • $\begingroup$ All I am saying is, don't state your opinions as if they were facts :-P $\endgroup$ – Aryabhata Jan 9 '15 at 2:50
12
$\begingroup$

Here is another mythical answer:

We want to prove $(\log_2 \log_2 10)^2 < 3$.

One way is to use the procedure outlined here to compute $\log_2$. The only mild complication is knowing when to stop. Since $\log_2$ is non-decreasing, it suffices to find $x\ge\log_2 10 $ and $y \ge \log_2 x$ such that $y^2 <3$.

The procedure is straightforward, I am just repeating the parts necessary to see how an upper bound is found. Given $x>0$, we first compute the integer part of $\log_2 x$ by finding the smallest $n$ such that ${x \over 2^n} \in [1,2)$, then $\log_2 x = n + \log_2 {x \over 2^n}$. Then, supposing $x \in (1,2)$, we repeatedly square $x$ until $x^{2^n} \in [2,4)$. Then we have $\log_2 x = {1 \over 2^n}(1+ \log_2 {x^{2^n} \over 2})$, where ${x^{2^n} \over 2} \in [1,2)$, and so we can repeat ad nauseam.

For the purposes of this problem, we note that in the latter step, we always have $\log_2 x \le {1 \over 2^n}(1+ 1)$, since $\log_2 {x^{2^n} \over 2} \le 1$. So by replacing $\log_2 {x^{2^n} \over 2}$ by $1$ at any stage we obtain an upper bound. The error will be $\le {1 \over 2^{n_1}} \cdots {1 \over {2^{n_k}}}$, where the $n_1,...,n_k$ are the number of 'squarings' at each step.

Then it is a matter of trial and error to find suitable $x,y$:

$x = 3+{1 \over 4} + {1 \over 16} + {1 \over 128} + {1 \over 1024} + {1 \over 2048}+{1 \over 8192}+ {1 \over 65536}+ {1 \over 65536} = {217706 \over 65536} \ge \log_2 10$.

$y = 1+{1 \over 2} + {1 \over 8} +{1 \over 32} + {1 \over 128} + {1 \over 256} + {1 \over 1024} + {1 \over 2048} + {1 \over 16384} + {1 \over 65536}+ {1 \over 65536}= { 113510 \over 65536 } \ge\log_2 x$.

We have $y^2=({ 113510 \over 65536 })^2 < 3$.

No calculators or computers were harmed during this computation.

$\endgroup$
3
$\begingroup$

There is nothing magical about a calculator: any computation performed on a calculator can be done by hand (and perhaps with extra rigor). (*)

Most special functions have series approximations that are known to converge particularly quickly; but Taylor's theorem with remainder can be applied to almost all important special functions even without knowing these specialized series. If $f(x)$ is smooth on $(a-\epsilon, b+\epsilon)$ and all derivatives $f^{(n)}$ are bounded on that interval:

$$|f^{(n)}(x)| \leq K^n\qquad \forall x\in (a-\epsilon, b+\epsilon)$$

then Taylor's theorem guarantees that

$$|f(b) - F^i(b)| \leq \frac{K^i(b-a)^{i+1}}{(i+1)!}$$ where $F^i$ is the Taylor expansion to $i$th order $$F^i(b) = \sum_{j=0}^i f^{(j)}(a) \frac{(b-a)^j}{j!}.$$

In particular if $K^n$ can be chosen to decay sufficiently quickly in $n$, and $f^{(n)}(a)$ is easy to evaluate exactly at a special value $a$, the above can be used to approximate $f(b)$ to arbitrary precision by hand.

For this particular problem, we want to show that $$\sqrt{3}\log 2 \leq \log\log 10 - \log \log 2.$$

$\sqrt{x}$ and $\log x$ can be trivially estimated using the above. $\log \log x$ can be computed by composition (this will require computing $\log x$ to high precision) or directly using Taylor expansion about $x=e$ (NB the formulas for the higher-order derivatives are not particularly pleasant).

(*) However even when guaranteed accuracy is required, the advantages of hand calculation over computer algebra packages like Mathematica with arbitrary-precision support are rather dubious.

$\endgroup$
-2
$\begingroup$

First take logs $$2^{\sqrt3}>\log_2 10$$ Then again $$\sqrt{3}>\log_2 \log_2 10$$ Now, $$\log_2(10)=\frac{\log 10}{\log 2}$$ With $\log 10\approx 2.302$ and $\log 2\approx 0.6931$, We find $$\log_2(10)\approx3.32131$$ And the $\log_2$ of that is $(\approx1.731)$ Now, $\sqrt 3\approx 1.732,$ and therefore we conclude that $$2^{2^{\sqrt3}}>10$$ Note that these values can be found with Newton's method and taylor series, though tedious to find and calculate.

$\endgroup$
  • $\begingroup$ Unfortunately, $\sqrt 3 \approx 1.732$, so your argument fails. Also, how do you get $\log_2 3.3270 \approx 1.732$, though it is correct? $\endgroup$ – Ross Millikan Jan 9 '15 at 3:38
  • $\begingroup$ I used a few terms of the taylor series of $e^\log 2 x$ and newtons method with $f(x)=2^x-3.3270$. And then I probably failed at memorizing sqrt 3 :/ I will redo my computations with more accuracy then. $\endgroup$ – Cyclohexanol. Jan 9 '15 at 5:16
  • $\begingroup$ Fixed now. I got a better estimate of $\log 10$ and that was the problem. $\endgroup$ – Cyclohexanol. Jan 9 '15 at 5:24
  • 11
    $\begingroup$ You really should be using inequalities in the correct directions instead of $\approx$. Especially since your approximations of $\log_2(10)$ and $\log_2(\log_2(10))$ are actually off in the wrong direction. (You'll need more decimal places in your approximation of $\sqrt{3}$ when you correct those.) $\endgroup$ – aes Jan 9 '15 at 5:30

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.