Solving power towers

Question

a=2^Power[10^6, 10^9] 3^Power[4^9, 7^5]
TwoTower[n_] := Nest[2^# &, 1, n]

What's the smallest n such that TwoTower[n]>a? This question had a pen-and-paper answer on Quora, is there a way to use Mathematica here?

Answer 1

Just some thoughts (did not carefully check). If we follow the suggestion in that link and start taking logs (base 2), first thing which seems obvious is that we can safely forget the prefactor (the power of 3), since

Log[Log[a*b]] = Log[Log[a]+Log[b]] = Log[Log[a]]+Log[1+Log[b]/Log[a]] = 
= Log[Log[a]] + Log[b]/Log[a] + O((Log[b]/Log[a])^2), Log[b]<<Log[a]

where a is a power of 2 and b is a power of 3. Then, we can focus on just the power of 2. If we define our version of log and power:

Clear[log2,power];
log2[2] = 1;
log2[1] = 0;
log2[a_*b_] := log2[a] + log2[b];
log2[a_^b_] := b*log2[a];
log2[power[a_, b_]] := b*log2[a]; 

Then the following seems to give the answer:

In[62]:= 
    Length[NestWhileList[N[Log[2, #]] &,log2[log2[log2[ 2^power[10^6, 10^9]]]] /. 
           log2 -> (N[Log[2, #]]&), # > 1 &]] - 1 + 3

Out[62]= 7

We subtract 1 due to the way NestWhile works (the last element already violates the condition), and add 3 because we applied log2 3 times already, before entering NestWhileList. I was not able to read all the comments in that link without registering on the site, so I don't know their answer or what is the correct answer.

Edit:

It occured to me that the above solution can be expressed a little more elegantly so that no human interaction is at all needed:

ClearAll[log2, power];
log2[2] = 1;
log2[1] = 0;
log2[a_*b_] := log2[a] + log2[b];
log2[(power | Power)[a_, b_]] := b*log2[a];
log2[x : (_Integer | _Real)] := N[Log[2, x]];
power[a_, b_] :=
   With[{eval = Quiet[Check[Power[a, b], $Failed]]},
     eval /; (eval =!= $Failed)]

Then, the solution itself looks a bit easier:

In[8]:=Length[NestWhileList[log2,2^power[10^6, 10^9], ! FreeQ[#, power] || # > 1 &]] - 1

Out[8] = 7