《计算模型导引》第一章习题

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}$