根据OEIS A246959的信息，$n\ge 3$时有
$$C(n)=8\times12^{\frac{3^{n-2}-3}{2}}=2^{3^{n-2}}\times 3^{\frac{3^{n-2}-3}{2}}.$$
令$\varphi$为欧拉Totient函数，直接计算出$\varphi(13^8)$、$\varphi(\varphi(13^8))$、$\varphi(\varphi(\varphi(13^8)))$、$\ldots$再递归求幂即可得最终结果$324681947$。
注：以下为Python 3代码，因Python 3中的pow直接实现了快速幂。
t=[815730721,752982204,231686832,71288256,21934848,6749184,2076672,638976,196608]
def cal(s,n,m):
if s==0:
return n%t[m]
p=pow(3,cal(s-1,n,m+2)-2,t[m+1])
return (pow(2,p,t[m])*pow(3,(p-3)//2,t[m]))%t[m]
print(cal(3,10000,0))
|
