3
$\begingroup$

Let's say I want to compare two numbers that are stacked powers of different bases:

$a^{b^{c^{d^e}}}$ compared to $f^{g^{h^{i^j}}}$

where all ten values will be integers in the range $[1,10]$.

Important note: $a^{b^{c^{d^e}}}$ is $a^\left({b^\left({c^\left({d^e}\right)}\right)}\right)$, not $(((a^b)^c)^d)^e$.

What would be a possible approach for this? I know how to do it with just three numbers stacked on top of each other using logarithms:

$a^{b^c}$ compared to $d^{e^f}$ can be done by comparing $\log_2{a}×{b^c}$ to $\log_2{d}×{e^f}$. But how to use it with more exponents on top of one another?

PS: I'm not that familiar with most of the Math jargon and formulas used in most of the answers/questions on this website and only know the very basics of MathJax, so if you are to post any complex(-looking) formulas, could you also add an ELI5 explanation for me? :)


EDIT: The goal is to have a general approach/formula I can use in a computer program (i.e. in Java or Python) to give a truthy/falsey result for $a^{b^{c^{d^e}}}<f^{g^{h^{i^j}}}$, given the ten integers (within 10 seconds on a regular PC). This question was posted as a challenge on the Codegolf stackexchange a few hours ago. Because the same user also posed the $a^{b^c}<d^{e^f}$ challenge earlier, it is not very well-received. Regardless, I'm curious to see what approach can be used in general for this problem, hence my question here.

$\endgroup$
2
$\begingroup$

Assume the lowest bases aren't 1. If they are, comparing expressions is trivial, since $1^x=1<2^y$ for any $x,y\in[1,10]$.

Let's start by tackling 3 powers. As you noted, $a^{b^c}$ can be easily compared to $f^{g^h}$ by taking the log, which massively reduces the size of the numbers we are working with. We get $b^c\log(a)$ compared to $g^h\log(b)$, which are now reasonable to try and compute.

For 4 powers, we again take the log. This reduces the problem to comparing $b^{c^d}\log(a)$ and $g^{h^i}\log(f)$. By taking the log again, we get $c^d\log(b)+\log(\log(a))$ and $h^i\log(g)+\log(\log(f))$. This is also very reasonable to compute. One can also see that $\log(\log(x))$ is almost nearly irrelevant. The difference between $\log(\log(2))$ and $\log(\log(10))$ is only about $0.5$ if we use base ten for our logarithms.

For 5 powers, taking log twice gets us to $c^{d^e}\log(b)+\log(\log(a))$ and $h^{i^j}\log(g)+\log(\log(f))$. If we ignore the double log term, we can take another log to get $d^e\log(c)+\log(\log(b))$ and $i^j\log(h)+\log(\log(g))$. And as long as these two are far enough apart, we can ignore the dropped terms. How far apart? Assume wlog that $d^e\log(c)+\log(\log(b))\le i^j\log(h)+\log(\log(g))$. Then we let $y=\log(\log(f))-\log(\log(a))$$=\log(\log(f)/\log(a))$. The question is then a matter of what $\log(x)-\log(x+y)=-\log(1+y/x)$ is i.e. how far off are we when we ignore this term when taking the log of both sides. For simplicity, we use the natural log, base $e$. We then have the readily tight bounds of

$$\frac y{x+y}\le\ln\left(1+\frac yx\right)\le\frac yx$$

which is most nearly zero for large values of $x$. I strongly doubt that this will come into play, unless everything except the dropped terms come out to be equal.

$\endgroup$
  • $\begingroup$ I saw your Ruby answer on Code-golf just yet, and it indeed works. So I've accepted this answer. :) Well done. $\endgroup$ – Kevin Cruijssen May 16 at 9:44
0
$\begingroup$

Suppose you want to test whether these big numbers are equal. If $a=1,3,5,6,7$, then $f=a$. If $a=2,4,8$, then $f=2,4,8$. If $a=9$ then $f=3,9$. This leads to subcases for the towers of height $4$, for height $3$, etc. You could put all these posibilities in a tree, if you want (and like a little bit of programming) to impose conditions on all the integers.

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