Project Euler 809
Project Euler 809
题目
Rational Recurrence Relation
The following is a function defined for all positive rational values of \(x\).
\[f(x)=\begin{cases} x &x\text{ is integral}\\ f\left(\dfrac 1{1-x}\right) &x \lt 1\\ f\left(\dfrac 1{\lceil x\rceil -x}-1+f(x-1)\right) &\text{otherwise} \end{cases}\]
For example, \(f(3/2)=3\), \(f(1/6) = 65533\) and \(f(13/10) = 7625597484985\).
Find \(f(22/7)\). Give your answer modulo \(10^{15}\).
解决方案
从递归定义可以直接看出\(f\)函数的值域是整数域：
- 若 \(x\) 为整数，则 \(f(x)=x\) 是整数；
- 若 \(x\) 非整数，则递归调用的是 \(f(\cdot)\)，并没有直接产生非整数输出。
只要递归最终会到达整数输入，那么 \(f(x)\) 必为整数。
注意到本题目标\(\dfrac{22}{7}=3+\dfrac{1}7\)恰好属于形如 \(a+\dfrac{1}{b}\) 的形式，其中 \(a\ge 0\) 为整数，\(b\ge 1\) 为整数。
因此定义二维函数\(\displaystyle{F(a,b)=f\left(a+\dfrac{1}b\right)(a\in\mathbb Z_{\ge0},b\in\mathbb Z_{\ge1}).}\)接下来把原递归完整翻译成对 \(F(a,b)\) 的递推。
当 \(b=1\)时，此时\(a+\dfrac{1}{1}=a+1\)是整数，因此\(F(a,1)=a+1.\)
当 \(a=0,b>1\)时，此时 \(x=\dfrac{1}{b}<1\)，用第二条递归：\(F(0,b)=f\left(\dfrac{1}b\right)=f\left(\dfrac{1}{1-\frac{1}b}\right)=f\left(\dfrac{b}{b-1}\right).\)而\(\dfrac{b}{b-1}=1+\dfrac{1}{b-1},\)所以\(F(0,b)=F(1,b-1).\)
当 \(a\ge 1,b\ge 2\)时，此时 \(x=a+\dfrac{1}{b}>1\) 且非整数，进入第三条递归。先算出 \(\lceil x\rceil=a+1\)，于是\(\lceil x\rceil-x=(a+1)-\left(a+\dfrac{1}{b}\right)=1-\dfrac{1}{b}=\dfrac{b-1}{b}.\)
因此\(\dfrac{1}{\lceil x\rceil-x}=\dfrac{1}{(b-1)/b}=\dfrac{b}{b-1}=1+\dfrac{1}{b-1},\)所以\(\dfrac{1}{\lceil x\rceil-x}-1=\dfrac{1}{b-1}.\)另外\(x-1=(a-1)+\dfrac{1}b,\)
于是第三条递归化为
\[ F(a,b) =f\left(\dfrac{1}{b-1}+f\left((a-1)+\dfrac{1}b\right)\right) =f\left(\dfrac{1}{b-1}+F(a-1,b)\right). \]
而 \(F(a-1,b)\) 是整数（由递推结构可归纳得到），记为 \(N\)，则括号内为\(N+\dfrac{1}{b-1},\)
因此
\[ F(a,b)=F\left(F(a-1,b),b-1\right). \]
至此得到对所有 \(a\ge 0,b\ge 1\) 的完整递推：
\[ F(a,b)= \begin{cases} a+1 & b=1,\\ F(1,b-1) & a=0,b>1,\\ F\left(F(a-1,b),b-1\right) & a\ge 1,b\ge 2. \end{cases} \]
这个形式与 Ackermann 函数极为接近。不过标准 Ackermann 函数 \(A(m,n)\) 定义为
\[\begin{aligned} A(0,n)&=n+1,\\ A(m,0)&=A(m-1,1)\quad(m\ge 1),\\ A(m,n)&=A(m-1,A(m,n-1))\quad(m\ge 1,n\ge 1). \end{aligned} \]
令\(G(m,n)=F(n,m+1).\)
把 \(F\) 的三条递推改写成 \(G\)：
- 若 \(m=0\)，即 \(b=1\)：\(G(0,n)=F(n,1)=n+1.\)
- 若 \(n=0,m\ge 1\)，即 \(a=0,b=m+1>1\)：\(G(m,0)=F(0,m+1)=F(1,m)=G(m-1,1).\)
- 若 \(m\ge 1,n\ge 1\)：\(G(m,n)=F(n,m+1)=F(F(n-1,m+1),m)=G(m-1,G(m,n-1)).\)
这与 Ackermann 的递推完全一致，因此\(G(m,n)=A(m,n),\)也就是\(F(a,b)=A(b-1,a).\)换回原函数，有：\(f\left(a+\dfrac{1}b\right)=A(b-1,a).\)
因为\(\frac{22}{7}=3+\dfrac{1}{7},\)所以 \(a=3,b=7\)，从而\(f\left(\dfrac{22}{7}\right)=A(6,3).\)
接下来要计算 \(A(6,3)\bmod M,M=10^{15}\)。
我们使用Knuth 上箭头表示法表达Ackermann 函数。对固定 \(m\)，记\(A_m(n)=A(m,n).\)前几层可以直接展开得到：
- \(A_0(n)=n+1\)
- \(A_1(n)=n+2\)
- \(A_2(n)=2n+3\)
- \(A_3(n)=2^{n+3}-3\)
- \(A_4(n)=2\uparrow\uparrow(n+3)-3\)
更一般地，从 \(m=3\) 开始，每提升一层 \(m\)，就把“运算层级”提高一级，满足
\[ A(m,n)=2\uparrow^{(m-2)}(n+3)-3(m\ge 3), \]
其中 \(\uparrow^{(k)}\) 表示 \(k\) 个上箭头。
因此\(A(6,3)=2\uparrow\uparrow\uparrow\uparrow 6-3.\)这是一个极其巨大、远超任何显式整数表示范围的数。
由于本题仅计算\(A(6,3)\bmod M\)。因此考虑函数\(T(x)=2^x \bmod M.\)对任意初值 \(x_0\)，构造序列\(x_{k+1}=T(x_k)=2^{x_k}\bmod M\)由于状态空间有限，必然进入循环。对该模数\(M\)，实际会非常快进入一个不动点，即存在 \(L\) 使得\(L\equiv 2^L \pmod{M}.\)
并且当幂塔高度足够大时，\(2\uparrow\uparrow h \equiv L \pmod{M}\)恒成立（因为从某一层开始，继续往上加一层就是再套一次 \(T(\cdot)\)，而不动点意味着结果不再变化）。对 \(M\)，从较小起点迭代即可得到稳定值\(L\)。
而 \(2\uparrow\uparrow\uparrow\uparrow 6\) 的规模远远超过“足够大”的高度阈值，所以必然满足 \(2\uparrow\uparrow\uparrow\uparrow 6 \equiv L\pmod{M}.\)于是
\[ f\left(\frac{22}{7}\right)=A(6,3)\equiv L-3\pmod{M}. \]
代码
1 | def solve(): |