递归指数幂编码

Question

递归指数幂编码

performancemathnumberslogicexponent

3

我有一个数学问题，它在某个奥林匹克比赛中出现过，我正在尝试用代码实现这个问题。问题是，我无法想出解决这个问题的逻辑。

问题是：

9^(9^(9^(9^...... 重复1001次....)))。答案的最后5位是什么？

如果有人能告诉我如何解决这个问题，我会很高兴。请注意，由于我需要在代码中实现这个问题，因此需要一个步骤更少、复杂度更低的解决方案。

不过，如果你有任何能得出正确答案的方法，我也想知道，因为我一直没有想通这个问题。

- Srimant Mishra

1

经常被问到的小事情，看看模算术和幂，例如 modpow(9,1001,100000);。 - Spektre

2

@Spektre：这个问题不是关于9^1001的。它关于塔式乘方9^9^9^9......^9，有1001个9。至少，在数学奥林匹克竞赛中就是这种类型的问题。看起来很多人在这里更感兴趣的是9^1001。 - Douglas Zare

对不起，我的回答是错误的。因为评论的缘故，我跑到了另一个轨道上。我会看看能否给出更好的答案，或者干脆删除它。D Lowel 可能说得对。 - Noctis

2

如果这样的幂塔大于15层，结果将是相同的。这是因为φ（欧拉函数）重复15次， φ（φ（...φ（10 ^ 5）..））= 1。 - Egor Skriptunoff

@DouglasZare 是的，那要复杂得多... - Spektre

显示剩余7条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Douglas Zare · Accepted Answer

看起来其他答案计算了9^1001。这不是所提出的问题。那对于奥林匹克竞赛问题来说太简单了。

定义T(a,n)，使得T(a,1)=a，T(a,n)=a^(T(a,n-1))。这被称为tetration。问题要求计算T(9,1001) mod 100,000。

要解决实际问题，不明显应该使用哪个模数。并不总是T(a,n) mod m等于T(a,n mod m) mod m。例如，T(2,3)=2^2^2=2^4=16。T(2,4)=2^16=65536。在模10下，你不能只计算T(2,3) mod 10=6，然后2^6 mod 10=64 mod 10=4。T(2,4)=65536的最后一位是6，而不是4。

然而，你可以推出9的2500次方模100000余1，所以9的100000次方也模100000余1。（通过中国剩余定理，你可以分析9的幂对2的5次方和5的5次方取模的结果。）因此，你只需要跟踪T(9,n)模2500或100000的值，就可以确定T(9,1001)模100000的值。计算t = T(9,1000)模2500，然后计算powermod(9,t,100000)。

事实上，将n映射为9的n次方模100000的函数迅速趋于一个固定点45289。9的9次方模2500是489，9的489次方模2500是2289，9的2289次方模2500是289，而9的289次方模2500又是289。由于9的289次方模100000是45289，因此T(9,4)、T(9,5)、……、T(9,1001)的末尾都是45289。

编辑：让我详细说明Egor Skriptunoff的评论。9的幂对10^5取模，周期为phi(10^5)=40000，其中phi是欧拉函数。因此，我们只需要确定T(9,1000) mod 40000。9的幂对40000取模，周期为phi(40000)=16000，因此我们只需要找到T(9,999) mod 16000等。由于phi在10^5上迭代15次为1，我们知道任何9的幂对phi^15(10^5)取模的值，因此对于任何更大的n，T(9,16) = T(9,n) mod 10^5。