阿克曼函数
|
阿克曼函数$A(m,n)$的定义如下：
$$A(m, n) =
\begin{cases}
n+1 & m = 0, \\
A(m-1,1) & m>0, n=0, \\
A(m-1, A(m, n-1)) & m>0, n>0, \\
\end{cases}$$
其中m,n都是非负整数。
可以验证，$A(1,0)=2, A(2,2)=7, A(3,4)=125$。
求$\sum\limits_{n = 0}^6A(n,n)$模$14^8$的余数。
|
本题难度:
|
解答
|
$A(n,n)$的值在OEIS A046859给出，$n=0,1,2,3$时的值分别是$1,3,7,61$。
而$A(4,4)=2\uparrow^27-3$, $A(5,5)=2\uparrow^38-3$, $A(6,6)=2\uparrow^38-3$均十分巨大（$\uparrow$为高德纳箭头记号）。
记$\varphi$为欧拉Totient函数，则模$m$乘法群的$\varphi(m)$，从而若$\gcd(a,m)=1$，则有$a^b=a^{b\mod \varphi(m)} \pmod m$，以及若$\gcd(a,m)\neq 1$，则$a^b=a^{b\mod \varphi(m)+\varphi(m)} \pmod m$。
简单试算可以发现当$x\ge 10$，$2\uparrow\uparrow x$模$14^8$的余数都相同，因此对$n=5$和$6$只需计算$2\uparrow\uparrow 10-3$。
$2\uparrow\uparrow x$可以递归计算，最终结果是$1098988351$。
m=14**8
phi=6*(14**7)
f=lambda x,m: 1 << x if x <= 2 else pow(2,f(x-1,phi),m)
print((1+3+7+61+f(7,m)+2*f(10,m)-9)%m)
|
| |
