《计算模型导引》第一章习题
21
习题1.21
设\(f:\mathbb{N}\rightarrow\mathbb{N}\)，\(f\) 为单射（1-1）且满射（onto），证明： \(f\in\mathcal{GRF}\Leftrightarrow f^{-1}\in\mathcal{GRF}\) 。
证：
由于 \(f\) 为单射（1-1）且满射（onto），故任给 \(y\in\mathbb{N}\)，都存在唯一根 \(x\)使得\(f(x)=y\)，即\(x=f^{-1}(y)\).
故
\[
f^{-1}(y)=\mu z. [f(z)\ddot- y]
\]
因此 \(f\in\mathcal{GRF}\Rightarrow f^{-1}\in\mathcal{GRF}\).
同理 \(f^{-1}\in\mathcal{GRF}\Rightarrow f\in\mathcal{GRF}\).
22
习题1.22
设 \(p(x)\) 为整系数多项式，令 \(f:\mathbb{N}\rightarrow\mathbb{N}\) 定义为 \(f(a)=p(x)-a\) 对于 \(x\) 的最小非负整数根，证明： \(f\in\mathcal{RF}\) 。
证：
\[
f(a)=\mu x. [p(x)\ddot-a]
\]
故\(f\in\mathcal{RF}\).
23
习题1.23
设
$$
f(x,y)=
\begin{cases}
x/y, &\text{若}y\not= 0\text{且}y|x,\\
\uparrow,&\text{否则}.
\end{cases}
$$
证明： \(f\in\mathcal{RF}\) 。
证：
\[
f(x,y)=\mu z. [zy=x\text{且}y\not=0]=\mu z. [(zy\ddot-x)N(y)]
\]
故\(f\in\mathcal{RF}\).
24
习题1.24
设 \(g:\mathbb{N}\rightarrow\mathbb{N}\) 满足
$$
\begin{align}
g(0) &= 1, \\
g(1) &= 1, \\
g(n+2) &= \text{rs}((2002g(n+1)+2003g(n)),2005),
\end{align}
$$
(1) 试求\(g(2006)\);
(2) 证明\(g\in\mathcal{EF}\).
证：
（1）
设
\[
\begin{align}
h(0) &= 1, \\\\
h(1) &= 1, \\\\
h(n+2) &= -3h(n+1)-2h(n),
\end{align}
\]
由数学归纳法可证 \(g(n)=\text{rs}(h(n),2005)\).
\(h(n)\)的特征方程为 \(\lambda^2=-3\lambda-2\)，根为\(-1,-2\). 故\(h(n)\)呈形 \(a(-1)^n+b(-2)^n\). 由\(h(0)=0,h(1)=1\)得\(a=1,b=-1\)，故 \(h(n)=(-1)^n-(-2)^n\).
故 \(g(n)=\text{rs}((-1)^n-(-2)^n, 2005)\).
费马小定理
假如 \(p\) 是质数，且 \((a,p)=1\), 那么 \(a^{p-1}\equiv 1 (\mod p)\)
\(2005=5\times 401\)
由费马小定理，令 \(p=401,a=2\)，得到 \(2^{400}\equiv 1(\mod 401)\)；令 \(p=5,a=2^{100}\)，得到 \((2^{100})^{4}=2^{400}\equiv 1(\mod 5)\).
由于 \((5,401)=1\)，故 \(2^{400}\equiv 1(\mod 5\cdot 401)\)，即 \(\text{rs}(2^{400},2005)=1\).
提示
\(2^{400}-1\)既能被5整除，又能被401整除，而5和401互素，故能被\(5\times 401\)整除。
下面证明 \(g(n)\)的周期为400，即\(g(n+400)=g(n)\).
当 \(n\) 为偶数时，
\[
\begin{align}
g(n+400) &= \text{rs}((-1)^{n+400}-(-2)^{n+400},2005) \\\\
&= \text{rs}((-1)^{n}-2^{n+400}+2^n-2^n,2005) \\\\
&= \text{rs}((-1)^{n}-2^n(2^{400}-1)-2^n,2005) \\\\
&= \text{rs}((-1)^{n}-2^n,2005) \\\\
&= g(n)
\end{align}
\]
其中倒数第二个等号由\(\text{rs}(2^{400}-1,2005)=0\).
当 \(n\) 为奇数是同理。
故 \(g(2006)=g(6)=\text{rs}((-1)^6-(-2)^6, 2005)=1942\)
（2）
\(h(n)=(-1)^{n+1}(2^n\dot-1)\)，故
\[
\begin{align}
g(n) &=
\begin{cases}
2005\dot-\text{rs}(2^n\dot-1,2005), &n为偶数\\\\
\text{rs}(2^n\dot-1,2005), &n为奇数
\end{cases}\\\\
&=(2005\dot-\text{rs}(2^n\dot-1,2005))N(\text{rs}(n,2)) \\\\
&\quad +(\text{rs}(2^n\dot-1,2005))N^2(\text{rs}(n,2))
\end{align}
\]
故\(g\in\mathcal{EF}\).
25
习题1.22
设 \(f:\mathbb{N}\rightarrow\mathbb{N}\) 定义为
$$
f(n)=\pi 的十进制展开式中第n位数字
$$
例如\(f(0)=3\),\(f(1)=1\),\(f(2)=4\). 证明： \(f\in\mathcal{GRF}\) 。
证：
由 Hutton's Formula
\[
\frac{\pi}{4}=2\arctan\frac{1}{3}+\arctan\frac{1}{7}
\]
故
\[
\pi = 8\arctan\frac{1}{3}+4\arctan\frac{1}{7}
\]
\(\arctan x\)可由如下积分计算：
\[
\arctan x=\int^x_0\frac{dt}{1+t^2}
\]
根据等比数列求和公式，有
\[
\sum_{i=0}^n(-t^2)^i=\frac{1-(-t^2)^{n+1}}{1+t^2}
\]
故
\[
\frac{1}{1+t^2}=\sum_{i=0}^n(-t^2)^i+\frac{(-t^2)^{n+1}}{1+t^2}
\]
故
\[
\begin{align}
\arctan x &=\int^x_0\frac{dt}{1+t^2} \\\\
&=\sum_{i=0}^n(-1)^i\int^x_0t^{2i}\text{d}t+\int^x_0\frac{(-t^2)^{n+1}}{1+t^2}\text{d}t \\\\
&=\sum_{i=0}^n(-1)^i\frac{x^{2i+1}}{2i+1}+(-1)^{n+1}\int^x_0\frac{t^{2n+2}}{1+t^2}\text{d}t \\\\
\end{align}
\]
为了使余项为正，取 \(n=2k+1\)，则
\[
\begin{align}
\pi =& 8\sum_{i=0}^{2k+1}\frac{(-1)^i}{(2i+1)3^{2i+1}}+8\int^{\frac{1}{3}}_0\frac{t^{4k+4}}{1+t^2}\text{d}t \\\\
&{}+4\sum_{i=0}^{2k+1}\frac{(-1)^i}{(2i+1)7^{2i+1}}+4\int^{\frac{1}{7}}_0\frac{t^{4k+4}}{1+t^2}\text{d}t
\end{align}
\]
令
\[
t_k=8\sum_{i=0}^{2k+1}\frac{(-1)^i}{(2i+1)3^{2i+1}}+4\sum_{i=0}^{2k+1}\frac{(-1)^i}{(2i+1)7^{2i+1}} \\
r_k=8\int^{\frac{1}{3}}_0\frac{t^{4k+4}}{1+t^2}\text{d}t+4\int^{\frac{1}{7}}_0\frac{t^{4k+4}}{1+t^2}\text{d}t
\]
令 \(h(n,k)=\lfloor n\times t_k\rfloor\)，下证 \(h\in\mathcal{EF}\).
\[
\begin{align}
h(n,k)&= \left\lfloor 8n\sum_{i=0}^{2k+1}\frac{(-1)^i}{(2i+1)3^{2i+1}}+4n\sum_{i=0}^{2k+1}\frac{(-1)^i}{(2i+1)7^{2i+1}} \right\rfloor \\\\
&= \left\lfloor n\sum_{i=0}^{2k+1}\frac{(-1)^i}{(2i+1)}(\frac{8}{3^{2i+1}}+\frac{4}{7^{2i+1}}) \right\rfloor \\\\
&= \left\lfloor \frac{n}{3^{4k+3}7^{4k+3}(4k+3)!}\sum_{i=0}^{2k+1}\frac{(-1)^i(4k+3)!}{(2i+1)}(8\times 3^{4k+2-2i}+4\times 7^{4k+2-2i}) \right\rfloor \\\\
&= \left\lfloor \frac{n}{3^{4k+3}7^{4k+3}(4k+3)!}\left(\sum_{i=0}^{2k+1}\frac{N(\text{rs}(i,2))(4k+3)!}{(2i+1)}(8\times 3^{4k+2-2i}+4\times 7^{4k+2-2i}) \\\\
-\sum_{i=0}^{2k+1}\frac{\text{rs}(i,2)(4k+3)!}{(2i+1)}(8\times 3^{4k+2-2i}+4\times 7^{4k+2-2i})\right) \right\rfloor \\\\
&= \left\lfloor \frac{n}{3^{4k+3}7^{4k+3}(4k+3)!}\left\lfloor\sum_{i=0}^{2k+1}\frac{N(\text{rs}(i,2))(4k+3)!}{(2i+1)}(8\times 3^{4k+2-2i}+4\times 7^{4k+2-2i}) \\\\
-\sum_{i=0}^{2k+1}\frac{\text{rs}(i,2)(4k+3)!}{(2i+1)}(8\times 3^{4k+2-2i}+4\times 7^{4k+2-2i})\right\rfloor \right\rfloor \\\\
\end{align}
\]
故\(h\in\mathcal{EF}\).
我们可以通过 \(h\)，求 \(t_k\)的第 \(n\) 位小数为：
\[
h(10^n,k)\dot-10h(10^{n\dot-1},k)=\lfloor 10^n t_k\rfloor\dot-10\lfloor 10^{n\dot-1} t_k\rfloor
\]
令 \(a(n,k)=h(10^n,k)\dot-10h(10^{n\dot-1},k)\)，则 \(a(n,k)\) 为 \(t_k\)的第 \(n\) 位小数，其中 \(n\geq 1\).
下面我们要根据余项确定 \(k\)。倘若我们要求 \(\pi\) 的第 \(n\) 位有效数字，即第 \(n-1\) 个小数，需要保证余项不会影响这一位小数。具体地，如果 \(t_k\)的第 \(n-1\) 位及之后的小数为 \(59998\cdots\)，即第\(n-1\)位为\(5\)，之后是三个 \(9\)，之后是\(8\)。我们需要余项小于 \(10^{-(n+3)}\)，这样最多在 \(8\)上加 \(1\)，不产生进位，从而第\(n-1\)位\(5\)不受影响。
因此，我们计算 \(t_k\)的第 \(n\) 位小数之后第一个不是 \(9\)的小数位，即
\[
l(n, k)=\mu l. ((l\geq n+1)\wedge \prod_{i=n+1}^lN(a(i,k)\ddot-9))
\]
则 \(l\in\mathcal{GRF}\).
下面我们求余项 \(r_k\)的上界：
\[
\begin{align}
r_k
&=8\int^{\frac{1}{3}}_0\frac{t^{4k+4}}{1+t^2}\text{d}t+4\int^{\frac{1}{7}}_0\frac{t^{4k+4}}{1+t^2}\text{d}t\\\\
&\leq 8\int^{\frac{1}{3}}_0t^{4k+4}\text{d}t+4\int^{\frac{1}{7}}_0t^{4k+4}\text{d}t\\\\
&\leq 8\cdot\frac{1}{3}\cdot \frac{1}{3^{4k+4}}+4\cdot\frac{1}{7}\cdot\frac{1}{7^{4k+4}}\\\\
&\leq \frac{1}{3^{4k}}\\\\
&\leq \frac{1}{80^{k}}\\\\
\end{align}
\]
故
\[
\begin{align}
k(n)&=\mu k.\frac{1}{80^{k}}\leq 10^{-l(n,k)}\\\\
&=\mu k.10^{l(n,k)}\leq 80^{k}
\end{align}
\]
综上，当 \(n=0\)时，\(f(0)=3\)，当 \(n\geq 1\) 时，
\[
f(n)=a(n,k(n))
\]
故 \(f\in\mathcal{GRF}\)