# How to compare power towers in Mathematica?

First I tried it directly, but it overflowed:

In[1]:= 2^3^2^3^5^8 < 3^2^2^7^6^7
During evaluation of In[1]:= General::ovfl: Overflow occurred in computation. >>
During evaluation of In[1]:= General::ovfl: Overflow occurred in computation. >>

Out[1]= Indeterminate < Indeterminate


Using double Log did not help either:

In[2]:= Log[Log[2]] + Log[3] 2^3^5^8 < Log[Log[3]] + Log[2] 2^7^6^7
During evaluation of In[2]:= General::ovfl: Overflow occurred in computation. >>
During evaluation of In[2]:= General::ovfl: Overflow occurred in computation. >>

Out[2]= Overflow[] < Overflow[]


Then I tried to use the WolframAlpha function, and it seemed to be able to handle this and even much higher towers:

In[3]:= WolframAlpha["2^3^2^3^5^8 < 3^2^2^7^6^7", "MathematicaForms"][[2, 1]]
Out[3]= True

In[4]:= WolframAlpha["2^2^5^2^7^4^9^3^7^6^9^9^9^9^3^2 < 3^3^6^3^9^4^2^3^2^2^2^2^2^3^3^3", "MathematicaForms"][[2, 1]]
Out[4]= True


But then I discovered that it failed to perform certain comparisons:

In[5]:= WolframAlpha["4^6^8^8^9 < 3^2^3^3^3", "MathematicaForms"]
Out[5]= {}


And sometimes even gave wrong answers, even in seemingly trivial cases:

In[6]:= WolframAlpha["3^3^3^3^3 < 4^4^3^3^3", "MathematicaForms"][[2, 1]]
Out[6]= False


Can anybody suggest a correct and robust method to compare two expressions given in the form Hold[a^b^...^z], where a,b,...,z are positive integers?

• Related question. – Leonid Shifrin May 7 '13 at 20:14
• Just because it caused me a lot of consternation, the top answer on the Math Stack Exchange is mathematically incorrect. – Guillochon May 8 '13 at 0:50
• @Guillochon Both are incorrect and misleading as it is also pointed out in comments. Strange thing that they are sill there. – Kuba May 8 '13 at 1:02
• @Rojo Even if they might be seen as equal in some representations, there is actually a huge difference between them: 4^4^3^3^3 - 3^3^3^3^3 > 10^10^4591067155680. – Vladimir Reshetnikov May 8 '13 at 2:47
• I started a bounty worth +350 at math.stackexchange.com/questions/101138/… – Vladimir Reshetnikov May 8 '13 at 3:15

### The idea

The idea is that if we have

$\log(a+b),\qquad a\gg b$ ,

then we can equivalently write this as

$\log a + \log(1 + b/a)$

and the second part will be small, so that one can first compare the first part(s). The power towers with base numbers larger than 1 naturally lead to such logarithms when we repeatedly take the $\log$ of them. So, there seems to be a natural separation of a dominant part and a sub-leading part, which is what I think allows one to compare the towers in many or most cases.

### Implementation

OK, here is my attempt. To illustrate what I am going to do, first define these functions:

ClearAll[symbolicConvert];
SetAttributes[symbolicConvert, {HoldAll, Listable}];
symbolicConvert[num_] := Unevaluated[num] /. Power -> power


which replaces Power to power, and

ClearAll[log];
log[power[base_, exp_]] := exp * log[base];

log[HoldPattern[Times[args__]]] := Total@Map[log, {args}];

log[(main : (_log*_power)) + rest_] :=  log[main] + log[1 + rest/main];

log[main_ + rest : log[1 + _]] := log[main] + log[1 + rest/main];


which is a function to perform the transformation I need. Here is an illustration:

start = symbolicConvert[2^3^2^3^5^8]

(* power[2, power[3, power[2, power[3, power[5, 8]]]]]  *)


and then

NestList[log, start,4]


where I used an image since it better shows the resulting structure. The main thing to note is that the log[1+something] part will be small in (almost) all cases, because the "something" will be quite small. Therefore, the idea is to compare the parts in the sum which do not involve this log, first. If they are equal, we can compare these logs.

This function will tell us how long we will have to nest the application of log:

ClearAll[getNestingLength];
getNestingLength[expr_power] :=
Length[{expr /. power -> Sequence}] - 1;


This is a helper function we will need to extract the dominant part:

ClearAll[getMain];
getMain[main_ + log[1 + _]] := main;
getMain[x_ /; FreeQ[x, power]] := x;


This function will prepare our expressions for comparison:

ClearAll[prep];
SetAttributes[prep, HoldAll];
prep[fst_Power, sec_Power] :=
With[{nest = Max[getNestingLength /@ #]},
Map[Nest[log, #, nest] &, #]] &@symbolicConvert[{fst, sec}];


for the first examplein the question, this will produce:

prep[2^3^2^3^5^8, 3^2^2^7^6^7]


Note that so far, everything has been exact - while we represent the logs in this form, I did not employ any approximation yet.

Here is then the comparison function, which may be a bit ad hoc and might not cover all cases, but it worked on a few I tested:

ClearAll[less];
less[fst_, sec_] /; And @@ Map[
MatchQ[#, (_ + log[1 + _]) | (x_ /; FreeQ[x, power])] &,
{fst, sec}] && getMain[fst] =!= getMain[sec] :=
getMain[fst] < getMain[sec] /. log -> (If[# <= 0, 0, Log[#]] &);

less[fst : (main_ + log[1 + fr_/rmain_]), sec : (main_ + log[1 + sr_/rmain_])] :=
less[rmain + fr, rmain + sr];

less[a_log + b_/c_power, a_log + d_/c_power] := less[b, d];


### Examples

less @@ prep[2^3^2^3^5^8, 3^2^2^7^6^7]

(* True *)

less @@ prep[10^3^4^5, 3^3^4^5]

(* False *)

less @@ prep[2^2^5^2^7^4^9^3^7^6^9^9^9^9^3^2, 3^3^6^3^9^4^2^3^2^2^2^2^2^3^3^3]

(* True *)


### Remarks

It may well be that the current implementation does contain some bugs or does not cover some cases, but I think that the main idea behind it should work. Note that my approach should work in most cases except when the bases are so huge that even their logs can overcome the powers they are divided over.

• failing example: less @@ prep[2^4, 4^2] – Vladimir Reshetnikov May 8 '13 at 15:11
• @LeonidShifrin: The result seems to be incorrect (True) in this case: less @@ prep[2^2^2^2^2^2^2^2^2^2^2^2^2^2^4^2^2^2, 9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9]. I have not yet analyzed why. – Vladimir Reshetnikov May 8 '13 at 15:25
• @VladimirReshetnikov It is interesting that slightly rewriting your example less @@ prep[2^2^2^2^2^2^2^2^2^2^2^2^2^2^4^16, 9^9^9^9^9^9^9^9^9^9^9^9^9^9^9^9] gives a different result. I guess my approcimation breaks down when I take logs to many times. The "main" part of the log should be substantially larger than 1, while for this example I end up comparing 2 log[2] + log[log[2]] and log[log[9 log[9] + log[log[9]]]], both of which are really close to 1. I will add some condition for that. – Leonid Shifrin May 8 '13 at 15:42
• @LeonidShifrin You might want to publish your algorithm or just a link to this answer at math.stackexchange.com/questions/101138/… The +350 bounty ends in several hours and I think your algorithm is the best from all that were suggested and it looks having a polynomial complexity. – Vladimir Reshetnikov May 14 '13 at 17:13
• @LeonidShifrin I awarded the bounty to your answer as the best and closest to a complete solution so far. I still cannot mark it as an accepted answer because it errs on some corner cases. I hope you will find a time to make it perfect! Thanks! – Piotr Shatalin Jul 17 '13 at 20:30