这篇博文对连分数理论和逼近算法做进一步研究

连分数逼近算法

连分数与渐进分数的差

x=an+1pn+pn1an+1qn+qn1 xpnqn=(1)nqn(an+1qn+qn1)xp0q0=xa0=1a1 根据前面的引理, q1=a1,qn=anqn1+qn2 (1<nN) specialaN=aNqN=qN\begin{gathered} x=\frac{a_{n+1}^{\prime} p_{n}+p_{n-1}}{a_{n+1}^{\prime} q_{n}+q_{n-1}} \\ \ \\ x-\frac{p_{n}}{q_{n}}=\frac{(-1)^{n}}{q_ n\left(a_{n+1}^{\prime} q_{n}+q_{n-1}\right)} \quad x-\frac{p_{0}}{q_{0}}=x-a_{0}=\frac{1}{a_{1}^{\prime}} \\ \ \\ \text{根据前面的引理, } q_{1}^{\prime}=a_{1}^{\prime}, \quad q_{n}^{\prime}=a_{n}^{\prime} q_{n-1}+q_{n-2} \ (1 < n \leqslant N) \\ \ \\ \textbf{special} \quad a_{N}=a_{N}^{\prime} \quad q_{N}^{\prime}=q_{N} \end{gathered}

if  1nN1,then xpnqn=(1)nqnqn+1\begin{gathered} \text{if} \ \ 1 \leqslant n \leqslant N - 1, \text{then} \\ \ \\ x-\frac{p_{n}}{q_{n}}=\frac{(-1)^{n}}{q_{n} q_{n+1}^{\prime}} \end{gathered}

aN=1,aN1=aN1+1aN=aN1+1a_{N}=1, \quad a_{N-1}^{\prime}=a_{N-1}+\frac{1}{a_{N}}=a_{N-1}+1

i)\textbf{i)}

研究 pnqnxqn=1qnqn+1pnqnx=1qn+1 注意 qn+1 的性质就可以了\begin{gathered} \text{研究} \ \left|\frac{p_{n}-q_{n} x}{q_{n}}\right|=\frac{1}{q_{n} q_{n+1}^{\prime}} \Leftrightarrow\left|p_{n}-q_{n} x\right|=\frac{1}{q_{n+1}^{\prime}} \\ \ \\ \text{注意} \ q_{n+1}^{\prime} \ \text{的性质就可以了} \end{gathered}

ii)\textbf{ii)}

q0=1,q1=a1,q2=a2q1+q0=a1a2+1q1=a1<a1<a1+1a1a2+1=q2 qn+1=an+1qn+qn1,an+1<an+1<an+1+1 1nN2,we have {qn+1=an+1qn+qn1>an+1qn+qn1=qn+1qn+1<an+1an+qn+qn1=qn+1+qnan+2qn+1+qn=qn+2\begin{gathered} q_{0}=1, \quad q_{1}=a_{1}, \quad q_{2}=a_{2} q_{1}+q_{0}=a_{1} a_{2}+1 \\ q_{1}=a_{1}<a_1^{\prime} <a_{1}+1 \leqslant a_{1} a_{2}+1=q_{2} \\ \ \\ q_{n+1}^{\prime}=a_{n+1}^{\prime} q_{n}+q_{n-1}, \quad a_{n+1}<a_{n+1}^{\prime}<a_{n+1}+1 \\ \ \\ 1 \leqslant n \leqslant N -2, \text{we have} \\ \ \\ \left\{\begin{gathered} q_{n+1}^{\prime}=a_{n+1}^{\prime} q_{n}+q_{n-1}>a_{n+1} q_{n}+q_{n-1}=q_{n+1} \\ q_{n+1}^{\prime}<a_{n+1} a_{n}+q_{n}+q_{n-1}=q_{n+1}+q_{n} \leqslant a_{n+2} q_{n+1}+q_{n}=q_{n+2} \end{gathered}\right. \end{gathered}

1qn+2<pnqnx=1qn+1<1qn+1 pNqN1x=1qN,pNqNx=0 {1qn+2<pnqnx<1qn+11qn+3<pn+1qn+1x<1qn+2\begin{gathered} \frac{1}{q_{n+2}}<\left|p_{n}-q_{n} x\right|=\frac{1}{q_{n+1}^{\prime}}<\frac{1}{q_{n+1}} \\ \ \\ \left|p_{N}-q_{N-1} x\right|=\frac{1}{q_{N}}, p_{N}-q_{N} x=0 \\ \ \\ \left\{\begin{gathered} \frac{1}{q_{n+2}}<\left|p_{n}-q_{n} x\right|<\frac{1}{q_{n+1}} \\ \frac{1}{q_{n+3}}<\left|p_{n+1}-q_{n+1} x\right|<\frac{1}{q_{ n+2}} \end{gathered}\right. \end{gathered}

qnxpn|q_nx-p_n| 呈递减关系

specially, we have  qN1=(aN1+1)qN1+qN3=qN1+qN2,aN=1 qN1=qN\begin{gathered} \text{specially, we have } \\ \ \\ q_{N-1}^{\prime}=\left(a_{N-1}+1\right) q_{N-1}+q_{N-3}=q_{N-1}+q_{N-2}, \quad a_{N}=1 \\ \ \\ q_{N-1}^{\prime}=q_{N} \end{gathered}

qNq_N 递增, 所以又有

xpnqn 递减\left.\left|x-\frac{p_{n}}{q_{n}}\right|\right. \text{ 递减}

逼近的结论

qn+1>qn,qnxpn=(1)nqn+1 qn+1=an+1qn+qn1,qn+1>qn+1 1qn+1<1qn+11qn+1=1qn+1δn(0<δn<1)\begin{gathered} q_{n+1}>q_{n}, \quad q_{n} x-p_{n}=\frac{(-1)^{n}}{q_{n+1}^{\prime}} \\ \ \\ q_{n+1}^{\prime}=a_{n+1} q_{n}+q_{n-1}, \quad q_{n+1}^{\prime}>q_{n+1} \\ \ \\ \frac{1}{q_{n+1}^{\prime}}<\frac{1}{q_{n+1}} \Rightarrow \frac{1}{q_{n+1}^{\prime}}=\frac{1}{q_{n+1}} \cdot \delta_{n} \quad\left(0<\delta_{n}<1\right) \end{gathered}

qnxpn=(1)nδnqn+1(0<δn<1)q_{n} x-p_{n}=\frac{(-1)^{n} \delta_{n}}{q_{n+1}} \quad\left(0<\delta_{n}<1\right)

连分数的极限

n>3,qnnp2nq2np2n1q2n1=1q2nq2n112n(2n1)0\begin{gathered} n>3, \quad q_n \geqslant n \\ \left|\frac{p_{2 n}}{q_{2n}}-\frac{p_{2n-1}}{q_{2 n-1}}\right|=\frac{1}{q_{2 n} q_{2 n-1}} \leqslant \frac{1}{2 n(2 n-1)} \rightarrow 0 \end{gathered}

Farey数列

重要的结论

定理1\textbf{定理1} \quad 如果h/kh / k h/k\ h^{\prime} / k^{\prime}Fn\mathfrak{F_n} 中相邻的项, 那么
khhk=1kh'-hk'=1

定理2\textbf{定理2} \quad 如果h/k, h/k, h/kh/k, \ h''/k'', \ h'/k'Fn\mathfrak{F_n}33 个相连的项, 那么

hk=h+hk+k\frac{h^{\prime \prime}}{k^{\prime \prime}}=\frac{h+h^{\prime}}{k+k^{\prime}}

定理3\textbf{定理3} \quad 如果h/kh/kh/kh'/k'Fn\mathfrak{F_n} 中相连的两项, 那么

k+k>nk+k'>n

如果定理2成立, 定理3必然成立, 因为

h+hk+k\frac{h+h^{\prime}}{k+k^{\prime}}

落在区间

(hk,hk)\left(\frac{h}{k}, \frac{h^{\prime}}{k^{\prime}}\right)

中, 除非k+k>nk+k'>n 成立, 否则违背h/k,h/kh/k, h'/k' 是相邻两项

proof1\textbf{proof1}
数学归纳法, 假设对于Fn1\mathfrak{F}_{n-1} 两个相连的项h/k,h/kh/k, h'/k' 成立, 在Fn\mathfrak{F}_n 中它们被h/kh''/ k'' 隔开

khhk=r>0,khhk=s>0根据归纳假设,khhk=1 (h,k)=1,(s,r)=1 h=sh+rh,k=sk+rk 考虑分数集合 S HK=μh+λhμk+λk,(μ,λ)=1 这是一个既约分数, 如果不是的话, 不妨设  ms(μh+λh)+t(μk+λk),s,t k(μh+λh)h(μk+λk)=λh(μh+λk)k(μh+λh)=μ mμ, mλ 在 S 中取值使得 K 最小,λ=1,μ=1h=h+h, k=k+k\begin{gathered} kh''-hk''=r > 0, \quad k''h'-h''k'=s >0 \\ \text{根据归纳假设}, \quad kh'-hk' = 1 \\ \ \\ (h'', k'') = 1, \Rightarrow (s, r)=1 \\ \ \\ \Rightarrow h'' = sh + rh', \quad k''=sk+rk' \\ \ \\ \text{考虑分数集合 }S \\ \ \\ \frac{H}{K}=\frac{\mu h+\lambda h^{\prime}}{\mu k+\lambda k^{\prime}}, \quad (\mu, \lambda) = 1\\ \ \\ \text{这是一个既约分数, 如果不是的话, 不妨设 }\\ \ \\ m | s\left(\mu h+\lambda h^{\prime}\right)+t\left(\mu k+\lambda k^{\prime}\right), \quad \forall s,t \\ \ \\ k\left(\mu h+\lambda h^{\prime}\right)-h\left(\mu k+\lambda k^{\prime}\right) = \lambda \\ h'\left(\mu h+\lambda k^{\prime}\right)-k'\left(\mu h+\lambda h^{\prime}\right) = \mu \\ \ \\ \Rightarrow m | \mu, \ m | \lambda \\ \ \\ \text{在} \ S \ \text{中取值使得} \ K \ \text{最小}, \lambda = 1, \mu = 1 \\ h''=h+h', \ k'' = k+k' \end{gathered}

proof2\textbf{proof2}
构造法, 假设h/kh/k 后面的项不是h/kh'/k' , 不妨假设是x/yx/y, 那么有

kxhy=1 因为 (h,k)=1,kxhy=1 有整数解 另一方面, h/k 和x/y 是相连的两项, 那么 k+y>ny>nky<n 方程的解不妨设为x0,y0 x0+th, y0+tk,t 成立, 满足 0nk<yn 当然可以取得到\begin{gathered} kx-hy=1 \\ \ \\ \text{因为} \ (h, k) = 1, kx-hy=1 \ \text{有整数解} \\ \ \\ \text{另一方面, }h/k \ \text{和} x /y \ \text{是相连的两项, 那么} \\ \ \\ k+y>n \Leftrightarrow y > n - k \\ y < n \\ \ \\ \text{方程的解不妨设为} x_0, y_0 \\ \ \\ x_0+th, \ y_0+tk, \forall t \text{ 成立, 满足} \\ \ \\ 0 \leqslant n - k < y \leqslant n \ \text{当然可以取得到} \end{gathered}

kxhy=1xy=hk+1ky>hk kxhy1,x/y 位于 h/k 的后面 三个 Farey 项的排列是 {hk,hk,xy} xyhk=kxhyky1ky hkhk=hkkhkk1kk 1ky=kxhyky=xyhk1ky+1kk=k+ykky>nkky1ky 矛盾, 所以x/y=h/k\begin{gathered} kx-hy = 1 \Leftrightarrow \frac{x}{y}=\frac{h}{k}+\frac{1}{k y}>\frac{h}{k} \\ \ \\ kx-hy \geqslant 1, \quad x/y \ \text{位于} \ h/k \ \text{的后面} \\ \ \\ \text{三个}\text{ Farey }\text{项的排列是} \ \{\frac{h}{k}, \frac{h'}{k'}, \frac{x}{y}\} \\ \ \\ \frac{x}{y}-\frac{h^{\prime}}{k^{\prime}}=\frac{k^{\prime} x-h^{\prime} y}{k^{\prime} y} \geqslant \frac{1}{k^{\prime} y} \\ \ \\ \frac{h^{\prime}}{k^{\prime}}-\frac{h}{k}=\frac{h^{\prime} k-k^{\prime} h}{k k^{\prime}} \geqslant \frac{1}{k k^{\prime}} \\ \ \\ \frac{1}{k y}=\frac{k x-h y}{k y}=\frac{x}{y}-\frac{h}{k} \geqslant \frac{1}{k^{\prime} y}+\frac{1}{k k^{\prime}}=\frac{k+y}{k k^{\prime} y} >\frac{n}{k k^{\prime} y} \geqslant \frac{1}{k y} \\ \ \\ \text{矛盾, 所以} x/y= h'/k' \end{gathered}

Farey算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void findNext() {
example: 4/9

get one solution of 9x-4y=1
(x0, y0) = (1, 2)

let 13-9 < 2+9r < 13

enumerate r = 1
x = 1 + 4r = 5
y = 2 + 9r = 11

5/11 is the answer
}

初等数论相关算法

素数筛法

Eratosthenes筛法,用v[x]标记合数\textbf{Eratosthenes筛法,用v[x]标记合数}

从 x 开始 {x2,(x+1)x,,[N/x]x}标记为合数\begin{gathered} \text{从} \ x \ \text{开始} \\ \ \\ \{x^2, (x+1)x, \ldots , [N/x]\cdot x\} \text{标记为合数} \end{gathered}

1
2
3
4
5
6
7
8
9
int v[maxn];
void primes(int n) {
Set(v, 0);
_rep(i, 2, n) {
if(v[i]) continue;
cout << i << endl;
_rep(j, i, n / i) v[i * j] = 1;
}
}

线性筛法,标记最小素因子\textbf{线性筛法,标记最小素因子}

i) 记录当前数的最小素因子 v[x] ii) 用递增素数列 primes 维护[2,x] 已产生的素数集合 iii) pprimes,p=primes[j], 在 x 的基础上, 累乘一个最小质因子 p需满足, pv[x],p 是 ip 的最小素因子\begin{gathered} \textbf{i)} \ \text{记录当前数的最小素因子} \ v[x] \\ \ \\ \textbf{ii)} \ \text{用递增素数列} \ \textbf{primes} \ \text{维护} [2, x]\text{ 已产生的素数集合} \\ \ \\ \textbf{iii)} \ p \in \text{primes}, p = \text{primes}[j], \ \text{在} \ x \ \text{的基础上, 累乘一个最小质因子} \ p \\ \text{需满足, } p \leqslant v[x], p \ \text{是} \ i \cdot p \ \text{的最小素因子} \end{gathered}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int v[maxn];
void primes(int n) {
Set(v, 0);
vector<int> prime;

_rep(x, 2, n) {
if(v[x] == 0) {
v[x] = x;
prime.push_back(x);
}
_for(i, 0, prime.size()) {
if(prime[i] > n / x || prime[i] > v[x]) break;
v[x * prime[i]] = prime[i];
}
}

_for(i, 0, prime.size()) cout << prime[i] << endl;
}

Fermat数用于逼近

Fn=22n+1 没有大于1的公约数\begin{gathered} F_{n}=2^{2^n}+1 \\ \ \\ \text{没有大于1的公约数} \end{gathered}

x=22n Fn+k2Fn=22n+k122n+1=x2k1x+1 =x2k1x2k2+1 mFn,mFn+k,m(Fn+k2) m2,2̸Fnm=1\begin{gathered} x=2^{2^{n}} \\ \ \\ \frac{F_{n+k}-2}{F_{n}}=\frac{2^{2^{n+k}}-1}{2^{2^{n}}+1}=\frac{x^{2^{k}}-1}{x+1} \\ \ \\ =x^{2^k-1}-x^{2^k-2}+\cdots-1 \\ \ \\ m\left|F_{n}, \quad m\right| F_{n+k}, \quad \Rightarrow m |\left(F_{n+k}-2\right) \\ \ \\ \Rightarrow m | 2, \quad 2 \not \mathop{|} F_{n} \Rightarrow m=1 \end{gathered}

{F1,F2,,Fn}能够被一个奇素数整除, 并且这些奇素数互不相同 pn+1Fn=22n+1\begin{gathered} \{F_1, F_2, \cdots, F_n\} \text{能够被一个奇素数整除, 并且这些奇素数互不相同} \\ \ \\ p_{n +1} \leqslant F_n = 2^{2^n}+1 \end{gathered}

代数恒等式\textbf{代数恒等式}

akl+1al+1=a(k1)la(k2)l++1\frac{a^{kl}+1}{a^{l}+1}=a^{(k-1) l}-a^{(k-2) l}+\dots+1

Euclid定理的代数证明\textbf{Euclid定理的代数证明}
N(x)表示不超过 x , 并且不能被任何 p>pj 素数整除的数 n 的个数N(x)\text{表示不超过} \ x \ \text{, 并且不能被任何} \ p > p_j \ \text{素数整除的数} \ n \ \text{的个数}

n=n12m, m 无平方因子 m=2b13b2pjbj, bj={0,1}, 有 2j 种不同的取值 n12nxn1nx m有 2j 种取值, n1x种取值, N(x)2jx\begin{gathered} n = n_1^2m, \ m \ \text{无平方因子} \\ \ \\ m=2^{b_{1}} 3^{b_{2}} \ldots p_{j}^{b_{j}} , \ b_j = \{0, 1\}\text{, 有} \ 2^j \ \text{种不同的取值} \\ \ \\ n_{1}^{2} \leqslant n \leqslant x \Rightarrow n_{1} \leqslant \sqrt{n} \leqslant \sqrt{x} \\ \ \\ m \text{有} \ 2^j \ \text{种取值, }n_1 \text{有} \sqrt{x} \text{种取值, }N(x) \leqslant 2^{j} \sqrt{x} \end{gathered}

如果素数有限, 那么设所有素数为 {2,3,,pj} 对于每个  x  , 要么被 [2,pj] 中的一个整除, 要么 x 本身是素数 N(x)=x, x2jxx222j,这个对 x222j+1 不成立\begin{gathered} \text{如果素数有限, 那么设所有素数为 }\{2,3,\cdots, p_j\} \\ \ \\ \text{对于每个 }\ x \ \text{ , 要么被 }[2, p_j] \text{ 中的一个整除, 要么} \ x \ \text{本身是素数} \\ \ \\ N(x) = x, \ \Rightarrow x \leqslant 2^j \sqrt{x} \\ x \leqslant 2^{2^{2j}}, \text{这个对} \ x \geqslant 2^{2^{2j}} + 1 \ \text{不成立} \end{gathered}

素数相关的级数的敛散性\textbf{素数相关的级数的敛散性}

1p=12+13+15+17+ 发散, 证明如下 xN(x) 表示{nx}中能够被{pj+1,pj+2,}整除的数的个数 xpi+1+xpj+2+<12x,xN(x)<12x 12x<N(x)2jx,x<22j+2 let x22j+2, 结论不成立\begin{gathered} \sum \frac{1}{p}=\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+\frac{1}{7}+\dots \\ \ \\ \text{发散, 证明如下} \\ \ \\ x-N(x) \ \text{表示} \{\cdots n \cdots x\} \text{中能够被} \{p_{j+1}, p_{j+2}, \cdots \} \text{整除的数的个数} \\ \ \\ \frac{x}{p_{i+1}}+\frac{x}{p_{j+2}}+\ldots<\frac{1}{2} x, \quad x-N(x)<\frac{1}{2} x \\ \ \\ \frac{1}{2} x<N(x) \leqslant 2^j \sqrt{x}, \quad x<2^{2j+2} \\ \ \\ \text{let} \ x \geqslant 2^{2j+2} \text{, 结论不成立} \end{gathered}

π(x)性质\pi(x) \textbf{性质}
π(x)表示不超过 x 的素数的个数\pi(x) \text{表示不超过} \ x \ \text{的素数的个数}

let j=π(x),这个 j 是可以取到的, we have pj+1>x,N(x)=x x=N(x)2π(x)x2π(x)x π(x)lnx2ln2 x=pn,π(x)=npn4n\begin{gathered} \text{let} \ j = \pi(x), \text{这个} \ j \ \text{是可以取到的, }\text{we have} \\ \ \\ p_{j+1} > x, \quad N(x) = x \\ \ \\ x = N(x) \leqslant 2^{\pi(x)} \sqrt{x} \quad \Rightarrow 2^{\pi(x)} \geqslant \sqrt{x} \\ \ \\ \pi(x) \geqslant \frac{\ln x}{2 \ln 2} \\ \ \\ x = p_n, \quad \pi(x) = n \Rightarrow p_n \leqslant 4^n \end{gathered}

素数公式进一步结果

不存在任何非常数的整系数多项式f(n)f(n), 使得它对充分大的nn, 都取素数值
proof\text{proof}

x>N,f(x)=a0xk+=y>1 r,f(ry+x)=a0(y+x)k+=a0(y)k++(a0xk+) yf(ry+x),r,f(ry+x) f(n)取的到无穷多合数\begin{gathered} x>N, \quad f(x)=a_{0} x^{k}+\ldots=y>1 \\ \ \\ \forall r, \quad f(r y+x)=a_{0}(y+x)^{k}+\ldots=a_{0}(y)^{k}+\cdots+\left(a_{0} x^{k}+\cdots\right) \\ \ \\ y | f(ry + x), r \rightarrow \infty, f(r y+x) \rightarrow \infty \\ \ \\ f(n) \text{取的到无穷多合数} \end{gathered}

整数模

除了00 模以外, 任何模都是某个正数dd 的整数倍构成的集合

aS,bS,xa+ybS d 是 S 中的最小正数, z,nzdS 记余数是 c ,0c<d,假设 d 最小, 因此 c=0,n=zd\begin{gathered} a \in S, \quad b \in S, \quad \Rightarrow \quad x a+y b \in S \\ \ \\ d\ \text{是}\ S\ \text{中的最小正数, }\forall z, \quad n-z d \in S \\ \ \\ \text{记余数是} \ c \ , 0 \leqslant c < d, \text{假设} \ d \ \text{最小, 因此} \\ \ \\ c = 0, \quad n = zd \end{gathered}

Galois理论角度理解

能以多于一种方式分解成素数乘积的数称为非正规数

设 n 是最小的非正规数, 同一个素数 p 不可能同时在因式分解中出现 否则 n/p 就是非正规数, n/p<n we haven=p1p2p3=q1q2,  piqj p12n, q12np1q1 p1q1<n N=np1q1, 0<N<n,N为正规数 p1N,q1N,  (p1q1)N (p1q1)n q1(n/p1),but (n/p1)<n 为正规数 n/p1有唯一的素数分解 p2p3n=p1p2唯一\begin{gathered} \text{设} \ n \ \text{是最小的非正规数, 同一个素数} \ p \ \text{不可能同时在因式分解中出现} \\ \ \\ \text{否则} \ n / p \ \text{就是非正规数, } n /p < n \\ \ \\ \text{we have} \quad n = p_1p_2p_3 \cdots = q_1q_2\cdots, \ \ p_i \neq q_j \\ \ \\ p_1^2\leqslant n, \ q_1^2 \leqslant n \stackrel{p_{1} \neq q_{1}}{\Longrightarrow} \ p_1q_1 < n \\ \ \\ N = n - p_1q_1, \ 0 < N < n, N \text{为正规数} \\ \ \\ p_1 | N, q_1 | N, \ \ \Rightarrow (p_1q_1) | N \ \Rightarrow (p_1q_1) | n \\ \ \\ q_1 | (n / p_1), \text{but} \ (n / p_1) < n \ \text{为正规数} \\ \ \\ n / p_1 \text{有唯一的素数分解} \ p_2p_3\cdots \Rightarrow n = p_1p_2\cdots \text{唯一} \end{gathered}