3
$\begingroup$

Let $x=[x_1,x_2,...,x_n]$ be a finite list of positive real numbers, and define $\tau x$ as the power tower formed by these numbers. The function $\tau$ can be recursively defined by the following two equations:

$$\tau [x_1] = x_1$$

$$\tau [x_1,x_2,...]=x_1^{\tau [x_2,...]}$$

For example,

$$\tau [2,3,0.5,\pi]=2^{3^{0.5^\pi}}$$

I’m trying to find an algorithm which, given two finite ordered lists $x,y$ consisting only of $2$s and $3$s (e.g. $[2,2,3,2,3,3,3]$), determines which of $\tau x$ and $\tau y$ is larger, without explicitly calculating their values (the values quickly get much too big for most computers).

My thoughts so far: if $x$ and $y$ start with the same number, then we can eliminate this first number and just compare the subsequent entries of $x$ and $y$. This means that the only “interesting” cases are (WLOG) comparisons of the form $2^{\tau x’}$ and $3^{\tau y’}$, where $x’$ and $y’$ are formed by deleting the first entries of $x$ and $y$ respectively.

My intuition tells me that all reasonably tall distinct power towers of $2$s and $3$s will be “very far apart,” and in most cases determining which of $2^{\tau x’}$ and $3^{\tau y’}$ is greater will just boil down to determining which of $\tau x’$ and $\tau y’$ is greater. However, I’m having trouble formally determining exactly when this will be the case and what the exceptions will be.

Can anyone figure out a way to make my intuition rigorous, or suggest a different approach to finding an algorithm for comparing these power towers?

DISCLAIMER: This question arose while I was messing around with power towers. It’s not from a homework assignment or competition - purely a product of my personal math shenanigans. (For that reason, I can’t guarantee that it has a simple solution.)

$\endgroup$
  • 1
    $\begingroup$ When posting this kind of problems, it is better to give the source of the problem, as people might suspect that it comes from an ongoing programming contest (not that I'm suspecting, but just to be sure). $\endgroup$ – WhatsUp Sep 1 '20 at 22:26
  • $\begingroup$ @WhatsUp Thanks for the suggestion. I’ve added a “disclaimer” to the end. $\endgroup$ – Franklin Pezzuti Dyer Sep 1 '20 at 22:30
  • $\begingroup$ A very rough heuristic is that the first thing that matters is the height of the tower. If the numbers are "reasonable" nothing else can compete with that. If the height of the towers is the same, the top numbers matter much more than the bottom ones, so compare them downwards and declare success when you find a difference. You can be wrong, but only when there is an "unreasonably large" number in the tower $\endgroup$ – Ross Millikan Sep 2 '20 at 3:16
1
$\begingroup$

Just some quick thoughts:

I think the only natural thing to do here is to take logarithm. This leads to a more general problem: comparing $\ln(a)\cdot\tau x$ and $\ln(b) \cdot \tau y$, where $a, b\in\{2, 3\}$.

Taking logarithm again leads to comparing $\ln(a)\cdot \tau x + \ln(\ln(c))$ and $\ln(b) \cdot\tau y + \ln(\ln(d))$, where $a, b, c, d \in\{2, 3\}$.

Here comes a possible optimization: $\ln(\ln(c))$ and $\ln(\ln(d))$ are quite small numbers, compared to the supposedly huge $\tau x$ and $\tau y$. Hence if we can produce an inequality of the type $\ln(a) \tau x < (1 + \epsilon) \ln(b) \tau y$, even for some very tiny $\epsilon$, then a rough estimation on the size of $\tau y$ should be enough to give our willing inequality.


To summerize, we define the following process:

Checking_Process

Input: two lists, $x$ and $y$, and a positive real number $\alpha$

Output: a boolean value, true means $\alpha \cdot \tau x < \tau y$ and false means we don't know.

In Checking_Process, we write $x = [a, x']$ and $y = [b, y']$, and take a number $\alpha'$ that is "a tiny bit larger" than $\frac {\ln(a)}{\ln(b)}$.

We then recursively call Checking_Process on the inputs $x', y', \alpha'$. If the return is true, then we know that $\alpha' \tau x' < \tau y'$, which (with a suitable choice of $\alpha'$) implies $$\frac{\ln \alpha}{\ln(b)} + \frac {\ln(a)}{\ln(b)} \tau x' < \alpha' \tau x' < \tau y',$$ hence $\alpha \cdot \tau x < \tau y$ and we return true.

Otherwise, we return false to mean we don't know.


Now we just glue two pieces of Checking_Process: call Checking_Process on $x, y, 1$ and $y, x, 1$. Hopefully one of them will return true, and we are done.

In case both return false, it means that the inputs are in a very tricky situation. Since all the entries are $2$ and $3$, I think the chance of encountering this case should be negligible.

$\endgroup$
0
$\begingroup$

Since all we want are comparing $2$'s and $3$'s, the only issue is when one base is $2$ and the other is $3$ (otherwise just compare the exponents).

The key to comparing $2^x$ and $3^y$ is to compare their logarithms. If we take the base $2$ logarithm, we end up comparing $x$ and $y\log_2(3)\approx1.585y$.

We will need to then push further another step. Let $(x,y)=(i^m,j^n)$. We apply one more logarithm to get $m$ and $n\log_i(j)+\log_i(\log_2(3))$. This is the point where we have to start introducing possible errors in the answer. If $m$ or $n$ can be directly calculated, then it suffices to... just calculate them. Otherwise, we may use the following:

If $m=n\log_i(j)$ is true, then $2^x<3^y$. (This can only be discerned exactly if $i=j$).

Otherwise, we just compare $m$ and $n\log_i(j)$ and ignore the $\log_i(\log_2(3))$ term. Note that this allows us to once again take a logarithm and reduce another power.


The actual algorithm

In short, this is essentially:

$$2^x<3^y\iff x\le y$$

$$2^x>3^y\iff x>y$$

where we can stop earlier to directly calculate values by taking the logarithm twice.

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