解决电力塔 [英] Solving power towers

问题描述

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

像TwoTower[n]>a这样的最小n是多少?这个问题有一支笔关于Quora的答案，有没有办法在这里使用Mathematica?

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?

推荐答案

只是一些想法(没有仔细检查).如果我们遵循该链接中的建议并开始记录日志(以2为底)，那么显而易见的第一件事是，我们可以放心地忘记前置因子(3的幂)，因为

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]

其中a是2的幂，b是3的幂.然后，我们可以仅关注2的幂.如果定义log和power的版本，则: >

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

由于NestWhile的工作方式(最后一个元素已经违反条件)，我们减去1；由于在进入NestWhileList之前已经应用了3次log2，所以加了3.如果没有在网站上注册，我将无法阅读该链接中的所有评论，因此我不知道他们的答案或正确的答案.

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.

在我看来，上述解决方案可以更优雅地表达，从而完全不需要人工干预:

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

这篇关于解决电力塔的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！