https://projecteuler.net/problem=84
玩大富翁
有一些位置会触发跳转（跳转逻辑贼复杂）
问落在哪三个位置的概率最大
我都不想贴代码，这玩意真是靠大量数据“算”概率的咯。
所以伪随机数还是能作为概率意义上的“随机数”是因为 题目假设赛子均匀，而随机数分布的期望是均匀，数据量大了就符合统计逻辑？
想说有不少是模拟 行走去 记录次数然后处以总步数，然而这样的操作如果把4面换到6面很大才能 收敛到题目已经告诉你的102400
所以虽然4面可以比较小的数就 得到答案，但感觉更多是因为小，所以“猜”对的。
感觉还是应该 所有点 2.5%，然后每一轮进行所有格子走一次，直接计算概率转移，而不是模拟random，从而直到收敛（这也是能判断的了，不像上面计次 难以判断是否收敛，只能靠设置大，更大，再大的步数）。
疑惑的是，很多题目都是给小数据，要求大数据，怎么这一道题是给6求4。
其实读题,题太长才是我觉得的问题。XD
https://projecteuler.net/problem=100
$\frac{x(x-1)}{y(y-1)} = \frac{1}{2}$,x,y均为正整数，求首个满足表达式且$x>10^{12}$的x的值
显然 通过等式变换的基本操作 有
$(2y-1)^2-2(2x-1)^2 = -1$
这不就是 project euler的66题很像的pell 方程吗！
一点比较好的是$10^{12}$,其实可以双指针暴搜,O(x)时间复杂度，O(1)空间暴力算几个小时算出来,但当然如果是暴力也就不会写这篇文章了
稍加搜索也能搜到这个 https://www.alpertron.com.ar/QUAD.HTM 也就是说$ax^2+bxy+cy^2+dx+ey+f=0$的等式 都能解，
当然直接用网页也不需要这篇文章了，本文还是以证明为核心
考虑 $ax^2+bxy+cy^2+dx+ey+f=0$ 二元二次方程(以下过程中所有字母均为整数)
因为对称性，我们只考虑$a \neq 0$，否则交换x和y。
不然就是形如$axy+bx+cy+d=0$的方程了，而这类方程总能化为$(ax+b)(cy+d) = e$的形式，变为拆分e的。众所周知比较容易，本文就不涉及细节了。
$4a(ax^2+bxy+cy^2+dx+ey+f)=0$
$4a^2x^2+4abxy+4acy^2+4adx+4aey+4af=0$
$(2ax+by+d)^2 +(4ac-b^2)y^2+(4ae-2bd)y+(4af-d^2)= 0$
这形如
$x^2+ay^2+by+c=0$, 如果这里$y^2$的系数$a=0$,那么也是$x^2+ay+b=0$的简单情况，讨论$x \in [0,a)$，这里不细聊了,以下只考虑$a\neq 0$
$4a^2(x^2+ay^2+by+c) = 0$
$(2ax)^2+4a^3y^2+4a^2by+4a^2c = 0$
$(2ax)^2+a(2ay+b)^2+(4a^2c-ab^2) = 0$
这形如
$x^2+ay^2+c=0$
最终又回到了 这个式子，如果这里的a是正数，显然是一个椭圆方程，有限范围内的一些尝试,不是本次讨论的，暂时不展开了
那么最终回到了
$x^2-dy^2 = k$,其中$d > 0,k \neq 0$, $d$为非平方数,否则是平方数间隔问题
看看之前project euler 66 的证明过程
对比有
1&2不再是一定存在的，我们会讨论如果存在，那么具有性质和基础解
3只涉及连分数的性质，之前证明可复用
4同样只涉及连分数和不等式，最终结论任何最简分数$\frac{h}{k}$如果满足 $|\sqrt{d} - \frac{h}{k}| < \frac{1}{2k^2}$ 那么它是个渐进分数,同样复用
5,6都是连分数循环性质，reduced性质和二次无理数的关系，可复用
7是根号n的连分数表示性质，和$h_{n-1}^2-dk_{n-1}^2=(-1)^nQ_n$的证明，可复用
8再回到$x^2-dy^2=k$
若存在$(x_0,y_0),x_0 > 0,y_0 > 0$使得 $x_0^2-dy_0^2 = k$, 因为有最小的$(x_1,y_1)$满足$x_1^2-dy_1^2=1$ (证明见pe 66的证明)
那么通过$(x_0+y_0\sqrt{d})(x_1+y_1\sqrt{d})$能得到新的解
$(x_0^2-dy_0^2)(x_1^2-dy_1^2) = (x_0x_1+dy_0y_1)^2 - d(x_0y_1+x_1y_0)^2 = k$，所以如果有解那么有无限组解
设$(x_i,y_i)$是满足$x^2-dy^2 = k$的最小解,$(x_j,y_j)$是另一个满足方程的解,有$x_i<x_j,y_i<y_j$
若$(x_j,y_j)$不是由最小的$(x_i,y_i)$和$(x_1,y_1)$生成的,则
$(x_i+y_i\sqrt{d})(x_1+y_1\sqrt{d})^n < (x_j+y_j\sqrt{d}) < (x_i+y_i\sqrt{d})(x_1+y_1\sqrt{d})^{n+1}$
同时乘$(x_1-y_1\sqrt{d})^n$
$x_i+y_i\sqrt{d} < (x_j+y_j\sqrt{d})(x_1-y_1\sqrt{d})^n < (x_i+y_i\sqrt{d})(x_1+y_1\sqrt{d})$
因为中间的也满足 $x+y\sqrt{d}$的形式
若$(x_j+y_j\sqrt{d})(x_1-y_1\sqrt{d})^n$ 也是一组生成的解
令$(x_j+y_j\sqrt{d})(x_1-y_1\sqrt{d})^n = x_p+y_p\sqrt{d}$
有$(x_j-y_j\sqrt{d})(x_1+y_1\sqrt{d})^n = x_p-y_p\sqrt{d}$
有$(x_j-y_j\sqrt{d})(x_1+y_1\sqrt{d})^n = x_p-y_p\sqrt{d}$
** TODO 不会证明了 失败 **
$1=\frac{x_0^2-dy_0^2}{x_1^2-dy_1^2} $
$= \frac{x_0+y_0\sqrt{d}}{x_1+y_1\sqrt{d}} \cdot \frac{x_0-y_0\sqrt{d}}{x_1-y_1\sqrt{d}}$
$= \frac{(x_0+y_0\sqrt{d})(x_1-y_1\sqrt{d})}{-1} \cdot \frac{(x_0-y_0\sqrt{d})(x_1+y_1\sqrt{d})}{-1}$
$= ((x_0x_1-y_0y_1d)+(x_1y_0-x_0y_1)\sqrt{d})((x_0x_1-y_0y_1d)-(x_1y_0-x_0y_1)\sqrt{d})$
$= (x_0x_1-y_0y_1d)^2-(x_1y_0-x_0y_1)^2 d $
说明两个不同的-1的解 一定是通过乘一个=1的解得到的
说明存在一个=-1的基础解，其它解是靠基础解乘上(=1的基础解的幂次)得到的
同时我们在66证明过 $h_{n-1}^2-dk_{n-1}^2 = (-1)^nQ_n$
**注记：最开始66那一版本,的渐进分数的部分直接使用的是pell方程中$\sqrt{d}$,其中d是非平方正整数，但下面的部分证明和证明实际上只需要保证 其中部分的参数只要是无理数即可。所以进行了修改 **
若$x^2-\alpha^2 y^2 = \beta$, 且存在解，若$|\beta| < \alpha $,则$\frac{x}{y}$ 一定是 $\alpha$的渐近分数。
证明
若$\beta > 0$,有 $x^2-\alpha^2y^2 > 0 $即$x>y\alpha$
有$|\frac{x}{y} - \alpha| = \frac{\beta}{y(x+y\alpha)} < \frac{\beta}{2y^2\alpha} < \frac{1}{2y^2}$
前面证明过(66的6.2.3.8)满足这个表达式 的 对应的最简分数$\frac{x}{y}$ 一定是渐近连分数
若$\beta < 0$
$y^2 - \frac{1}{\alpha^2}x^2 = \frac{-\beta}{\alpha^2}$,注意到$|\frac{-\beta}{\alpha^2}| < \frac{1}{ \alpha } $ 也就回到上面的情况
综上，证毕。
以上的证明说明了 如果$x^2-dy^2=-1$如果有解,那么 一定是一个最简分数
同样根据66的过程 我们 连分类讨论的内容都能复用
$h_{n-1}^2-dk_{n-1}^2=(-1)^nQ_n = (-1)^n, n = kl $,l为$\sqrt{d}$的 最小周期长度,
也就是再看个奇偶，最后得到了pell方程和连分数比较紧密的结论
$l$长度为偶数无解
$l$长度为奇数, $(x,y) = {h_{(2m+1)l-1},k_{(2m+1)l-1}}$,m为非负整数
$x^2-2y^2 = -1$
关于$\sqrt{2}$的连分数展开众所周知了也(66连分数开篇就是)
从前面得到的结论看 也可以通过$(x_0+\sqrt{d}y_0)(x_1+\sqrt{d}y_1)^n$来生成
$(1+\sqrt{2})(3+2\sqrt{2})^n$
$(x+y\sqrt{2})(3+2\sqrt{2})^n$
$(x_n,y_n) = (3x_{n-1}+4y_{n-1},2x_{n-1}+3y_{n-1})$
嗯 高亮有点问题 整除识别成注释了
1 | x = 1 |
https://en.wikipedia.org/wiki/Pell%27s_equation#The_negative_Pell_equation
https://mathworld.wolfram.com/PellEquation.html
有搜到有人通过枚举前面的小解，发现了增长比例有趋近于定值的趋势。哎 我连找规律也不会了吗
没聊到其它非1和非-1时的情况
似乎$x^2-34y^2=-1$不存在解,所以可能无法证明它一定有解，但是如果有解，上面证明了一定是通过连分数的渐进分数找到的,也可以通过基础解生成
https://projecteuler.net/problem=78
4 = 4 = 3+1 = 2+2 = 2+1+1=1+1+1+1,p(4)=5
5 = 5 = 4+1 = 3+2 = 3+1+1 = 2+2+1 = 2+1+1+1 = 1+1+1+1+1,p(5)=7
求最小的n使得 p(n) % 1_000_000 = 0
dp递推暴力似乎并不可解,警告 下面的代码 只要没找到答案就会一直增加vector大小，所以建议尽早掐断，不然会吃很大内存XD,可能造成系统卡死或者假卡死
1 | use std::cmp; |
实际上可以把n看成，拆了$a_1$个1,$a_2$个2…
所以$p(n)$可以看成 $n = 1a_1+2a_2+3a_3+…+na_n$的解 $(a_1,a_2,…,a_n)$的个数
也是 $(1+x+x^2+x^3+…)(1+x^2+x^4+x^6+…)(1+x^3+x^6+x^9+…)…$ 结果中 $x^n$的系数,因为相当于从每个括号中选取了一项 假设第i个括号选取的是$x^{ij}$ 那么对应上面 $a_i = j$，也对应到相关的解
也就是 $\sum_{n=0}^{\infty} p(n)x^n = (1+x+x^2+…)(1+x^2+x^4+…)… = \frac{1}{1-x} \frac{1}{1-x^2} … = \prod_{n=1}^{\infty} \frac{1}{1-x^n} $
如果分拆结果要求 不能出现相同的数字(互异分拆 partitions into distinct parts)，则相当于上面$a_i$增加限制$a_i\in\{0,1\}$
也就是 $\sum_{n=0}^{\infty} q(n)x^n = (1+x)(1+x^2)… = \prod_{n=1}^{\infty} (1+x^n) $
$p(n) = $拆分成偶数个互异的数的方案数 + 拆分成奇数个互异的数方案数
考虑一个互异分拆$n=n_1+n_2+…+n_s$ (注意这里是$n_i$不是$a_i$,实际是$a_{n_i} = 1$的那些)
$x^{n} = x^{n_1}x^{n_2}…x^{n_s}$
$(-1)^sx^{n} = (-x^{n_1})(-x^{n_2})…(-x^{n_s})$
考虑 $\sum_{n=0}^{\infty} g(n)x^n = (1-x)(1-x^2)… = \prod_{n=1}^{\infty} (1-x^n) $ 从值的构成上 它依然表示的是互异分拆
注意到:$a_{n_i} = 0$在乘积贡献上是1,$a_{n_i}=1$在乘积贡献上是$-1$,所以 上述 每个互异分拆 对$g(n)$的贡献 是 $(-1)^s$
也就是$g(n) = $拆分成偶数个互异的数方案数 - 拆分成奇数个互异的数方案数
下面我们要看看欧拉大佬的神之推导
先上 Ferrer 图
比如 $ 11 = 5+4+2$
1 | xxxxx |
只考虑互异分拆，把底部的长度记为b(上图是1),从最大递减1的长度记为s(上图是5,4 所以s=2)
如果 一个图 $s \le b$,那么可以把最下面一排移到右侧,上图变为
1 | xxxxx x |
注意性质
移动以后，因为少了一行，分拆的奇偶性变了。
b至少增加1, s = 原来的b ，所以 新的图是 s>b的。
仅有一种情况是不能移动的（因为要移动的最后一行点数比移动后剩余的行数大1） 如下,注意到需要s排满和s排满，所以对于分拆的一个n，至多出现一次，学过等差数列求和的也可以看出满足这种的n的公式。
$n = \frac{s(s+(2s-1))}{2}$
1 | xxxxx |
以上 说明除了这特殊的以外，所有$s \le b$的 都有唯一对应的 $s > b$的互异ferrer图
再看 $s>b$的,例如(s=3,b=2)
1 | xxxxxx |
我们把右侧45度的点移到下面一排，有
1 | xxxxx |
同样有性质
同样有特殊的$s+1=b$的排满时，不能移动（否则移动后最下两行点数相等）
1 | xxxxxx |
同样学过等差数列求和的，对于一个n最多有一个，n的表达式也呼之欲出了
$n = \frac{s((s+1)+2s)}{2}$
综上 除了两种特殊的情况，其它的 都能找到一一对应的，所以偶奇相减除了特殊的外结果为0
所以就有神奇的展开
$\prod_{n=1}^{\infty}(1-x^n) = 1+\sum_{s=1}^{\infty} (-1)^s(x^{\frac{3s^2-s}{2}}+x^{\frac{3s^2+s}{2}})$
$(\sum_{n=0}^{\infty} p(n)x^n)(\cdot \prod_{n=1}^{\infty} 1-x^n) = (\prod_{n=1}^{\infty} )\cdot(\frac{1}{1-x^n} \cdot \prod_{n=1}^{\infty} 1-x^n) = 1 $ (…真的能这样乘吗。。
$(\sum_{n=0}^{\infty} p(n)x^n)(1+\sum_{s=1}^{\infty} (-1)^s(x^{\frac{3s^2-s}{2}}+x^{\frac{3s^2+s}{2}})) = 1 $
也就意味着左边 乘以后 对于$n>0$ 乘积后的系数都是$a_n = 0$
$a_n x^n = (p(n)x^n\cdot 1 + \sum_{s=1}^{\frac{3s^2-s}{2} \le n}[ p(n-\frac{3s^2-s}{2}) x^{n-\frac{3s^2-s}{2}} (-1)^s \cdot x^{\frac{3s^2-s}{2}} ]+ \sum_{s=1}^{\frac{3s^2+s}{2} \le n}[ p(n-\frac{3s^2+s}{2}) x^{n-\frac{3s^2+s}{2}} (-1)^s \cdot x^{\frac{3s^2+s}{2}} ])$
$0=a_n = p(n) + \sum_{s=1}^{\frac{3s^2-s}{2} \le n}[ p(n-\frac{3s^2-s}{2}) (-1)^s ]+ \sum_{s=1}^{\frac{3s^2+s}{2} \le n}[ p(n-\frac{3s^2+s}{2}) (-1)^s ])$
由此 我们有了$p(n)$的递推式,时间复杂度像是$n^1.5$(因为 s与n的不等式 是s平方增长 ，空间就只需要$O(n)$
$p(n) = \sum_{s=1}^{\frac{3s^2-s}{2} \le n}[(-1)^{s+1} p(n-\frac{3s^2-s}{2})]+ \sum_{s=1}^{\frac{3s^2+s}{2} \le n}[(-1)^{s+1} p(n-\frac{3s^2+s}{2}) ])$
只需要初始化$p(0) = 1$
至此就已经可以编码了
有的地方会采取 $t=-s$的带入第一个求和，把上面两个求和合并成一个,也就是 s取非零的正负整数
$p(n) = \sum_{s\neq 0,s\in Z,\frac{3s^2+s}{2}\le n} [(-1)^{s+1}p(n-\frac{3s^2+s}{2})] $
然后就是五边形数相关的东西了,在这道题看来 不是必须的
1 | fn main() { |
秒出
不过看结果和我第一遍卡爆内存的值一比，我想是不是多点内存也是暴力可行的XD。
互异分拆方案数=拆分成全是奇数个的方案数 ,$(1+x+x^2+…)(1+x^3+x^6+…)(1+x^5+x^{10}+…)…$
$\prod_{n=1}^{\infty} \sum_{k=0}^{\infty} x^{k*(2n-1)}$
$= \prod_{n=1}^{\infty} \frac{1}{1-x^{2n-1}}$
$= \prod_{n=1}^{\infty} \frac{1}{1-x^{2n-1}} \frac{\prod_{n=1}^{\infty} 1-x^{2n}}{\prod_{n=1}^{\infty} 1-x^{2n}}$
$= \frac{1}{\prod_{n=1}^{\infty} 1-x^{2n-1}}\frac{\prod_{n=1}^{\infty} (1-x^n)(1+x^n)}{\prod_{n=1}^{\infty} 1-x^{2n}}$
$ = \prod_{n=1}^{\infty} (1+x^n)$ (这。。。无限项这样拆分相消科学吗
就有了wikipedia上面那个公式 $\sum _{n=0}^{\infty }q(n)x^{n}=\prod _{k=1}^{\infty }(1+x^{k})=\prod _{k=1}^{\infty }{\frac {1}{1-x^{2k-1}}}.$
https://en.wikipedia.org/wiki/Partition_(number_theory)
https://en.wikipedia.org/wiki/Pentagonal_number_theorem
https://projecteuler.net/problem=75
$12=3+4+5,3^2+4^2=5^2;$
有些整数 有唯一拆分，可以拆分成直角三角形的三条边
看上去 枚举中间长度，二分最短长度，估算一下 (n*n/4 log n)，
1 | use std::thread; |
答案每新增1000 输出一次当前i，但运行了3min+ (x8核) 我把它掐了,准备学一学 如何数学角度优化
1 | time ./p075 |
如果有正整数对$(a,b,c)$满足$a^2+b^2=c^2$那么 这是一组勾股数
我们可以有$(ka,kb,kc)$也是勾股数，对于$gcd(a,b,c) = 1$的情况 称作素勾股数字
若$m>n$且$gcd(m,n)=1$ , m,n一个奇一个偶。
则令 $a=m^2-n^2$,$b=2mn$,$c=m^2+n^2$ ，则$(a,b,c)$是 素勾股数
充分性显然，上述表达满足勾股定理,且根据gcd运算规则是素勾股数
下面再证明必要，也就是所有素勾股数都能拆解成上面的m和n,
因为$gcd(a,b,c) = 1$ 说明两两$gcd = 1$(否则如果两个gcd不为1,运算过程 会导致另一个变量也是这个gcd的倍数 )
因此 必定a,b一个奇一个偶
根据轮换性质，不妨设 a奇 b偶 c奇
有$(c-a)(c+a)=b^2$
令 $\frac{m}{n} = \frac{c+a}{b} = \frac{b}{c-a}$
下面解 方程组$\frac{c}{b} + \frac{a}{b} = \frac{m}{n}, \frac{c}{b}-\frac{a}{b}=\frac{n}{m}$
得到$\frac{c}{b}=\frac{m^2+n^2}{2mn},\frac{a}{b}=\frac{m^2-n^2}{2mn}$
所以 素勾股数字总能写成上述m,n的形式
以上证明了 素勾股数 和 m,n 形式的充要关系
注意到 $c=m^2+n^2$
所以 最大的只用枚举到 $\sqrt{\frac{l}{2}}$
上面感觉很突兀,
看了一下 https://personal.math.ubc.ca/~cass/courses/m446-03/pl322/parametrization.html 的文章发现了来源
如果 a,b,c 能构成, 那么 (a/c,b/c) 在单位圆上, 且是 有理点, 那么和(1,0)的斜率也是有理数
令为(A,B), (B-0)/(A-1) = m, A^2+B^2=1, 解这个方程组
!! 没有根号, A=(m^2-1)/(m^2+1), B=-2m/(m^2+1)
令 m = -p/q, 带进去 就很自然了
这样的话 ,对于椭圆 x^2+by^2=z^2
同样是(x/z,y/z) 在椭圆上, 然后过(1,0)
就可以搞Project Euler 195了
1 | use std::thread; |
https://en.wikipedia.org/wiki/Pythagorean_triple
https://en.wikipedia.org/wiki/Formulas_for_generating_Pythagorean_triples
https://personal.math.ubc.ca/~cass/courses/m446-03/pl322/parametrization.html
从2020 02 09 挖的坑，中间很长一段时间鸽了，终于在05 29写完了.
https://projecteuler.net/problem=66
d = 1->1000，d是非平方数
对于每个d 求最小的正整数x使得$x^2-dy^2=1$，其中x,y都是正整数,
最后对所有这些x求最大的x
抽屉原理
二元一次方程
绝对值
有理数/无理数
模运算
矩阵运算
数列/递推数列
二项式展开
反证法
归纳法
不等式(缩放，三角不等式)
共轭实数(不太知道怎么翻译比较好，还是对偶实数？ 描述的就是$a+b\sqrt{m}$与$a-b\sqrt{m}$
如果质数p是d的因子，那么$x^2 = 1 (\bmod p)$,由此$x = 1 (\bmod p)$ 或者$x=p-1(\bmod p)$
所以我们可以按d的最大质因子的倍数 加减1去搜，能快个常数倍
显然有$(x-1)(x+1) = dy^2$
令$d=d_1 \cdot d_2$
令$y=y_1 \cdot y_2$
根据对称性必然有 $d_1 \cdot {y_1}^2 - d_2 \cdot {y_2}^2 = (x+1) - (x-1) = 2$
一定程度上能减少搜索量，优化最多也就最大质数常数倍，也是最多100倍的优化
另外就是MOD 4的性质，用处不大，2倍左右常数优化
然后就是1-100内的尝试是d=61最大1766319049
如果d0能找到x0，那么d0和y0因子平方的组合最多是x0,也是优化不大
1 | N = 1000 |
我给它掐断了,跑了两小时，虽然是单核的，但是还有284个数没算出来
值过大,需要big/int
写了一个可分段，可并行，可”断点”计算的
第一遍把1到1000直接跑，每次找到值都会输出剩余表
没统计计算时间，反正很久，每次运算的结果可以去替换slowv和ans
1 | package main |
这时就体现出当数学家可以推出结论，而计算机拥有的只是“蛮力”。
如果$x^2-d \cdot y^2=1$ 平方得 $x^4+d^2 \cdot y^4-2dx^2y^2=1$
$x^4+2dx^2y^2+d^2 \cdot y^4-d \cdot 4x^2y^2=1$
$(x^2+dy^2)^2 - d \cdot (2xy)^2=1$
即当我们有一个解时，通过平方能得到新的解
又$(x+\sqrt{d} \cdot y)\cdot (x-\sqrt{d} \cdot y)=1$
可得$((x+\sqrt{d} \cdot y)\cdot (x-\sqrt{d} \cdot y))^n=1$
$(x+\sqrt{d} \cdot y)^n\cdot (x-\sqrt{d} \cdot y)^n=1$
根据二项式展开有
若 $(x+\sqrt{d} \cdot y)^n = A + B\cdot{d}$
则 $(x-\sqrt{d} \cdot y)^n = A - B\cdot{d}$ 即是 $A^2-d \cdot B^2=1$
也就是它的n次方展开的系数也是一组解
同样,假设有两组解：(x1,y1)和(x2,y2)的，它们也可以通过上述乘积方法，合成一组新的解
下面证明所有解都是最小解生成的
因为y越大x越大,设$(x_1,y_1)$为最小解,$(x_k,y_k)$不是由最小解上述幂次方法生成的一个解
根据y越大x越大的性质，则存在一个整数n
$(x_1+y_1 \cdot \sqrt{d})^n < (x_k+y_k \cdot \sqrt{d}) < (x_1+y_1 \cdot \sqrt{d})^{n+1} $
同时乘$(x_1-y_1 \cdot \sqrt{d})^n$有
$1 < (x_k+y_k \cdot \sqrt{d}) \cdot (x_1-y_1 \cdot \sqrt{d})^n < (x_1+y_1 \cdot \sqrt{d}) $
注意到中间的表达式 也是满足参数形式的 也是一组解(并且因为$\frac{x_1}{y_1} = \sqrt{\frac{1}{y_1^2}+d} > \sqrt{\frac{1}{y_k^2}+d} = \frac{x_k}{y_k}$,所以参数均为正数 )
这与最小解定义冲突，所以所有解都是最小解生成的
存在无穷多对整数(x,y)满足 $|x-y\sqrt{d}|<\frac 1y$
取正整数$q_0 > 1$
取$t=1,…,q_0+1$ 共计$q_0+1$个
把区间$[0,1)$等分为$q_0$部分，则每部分长度为$\frac 1{q_0}$,考虑 $t \sqrt{d}$的小数部分(t为整数)，必定有两个落在同一区间 所以存在$0\leq i<j\leq q_0$使得 $| \{t_i \sqrt{d}\} - \{t_j \sqrt{d}\} | <\frac 1{q_0}$
即$|x-(t_j-t_i)\sqrt{d}| = | \{t_i \sqrt{d}\} - \{ t_j \sqrt{d}\} | < \frac 1{q_0} \leq \frac 1{t_j-t_i}$
这里要注意的是我们知道i<j,和它们的小数部分落在同一个区间，所以这里应该是它们的小数部分相减的绝对值，而不是相减的绝对值的小数部分，例如q取2, 一个取0.4,一个1.3,它们都在[0,0.5)的区间里，但是如果$|1.3-0.4|$ 再取绝对值的小数部分，得到的是0.9而不是0.1,对于x来说，只要增减1就能在最终的值上切换成功.
把$t_j-t_i$ 看作y得到一个解
取$\frac 1{q_1} < |x-(t_j-t_i)\sqrt{d}|$
可以得到新的解(因为同一个y最多有两种 $|x-y\sqrt{d}|$的小数部分，反复如此可生成无限个解
取$|x_3-y_3\sqrt{d}| <\frac 1{q_3} < |x_2-y_2 \sqrt{d}| < \frac 1{q_2} < |x_1-y_1\sqrt{d}| <\frac 1{q_1} < |x_0-y_0 \sqrt{d}| < \frac 1{q_0} $
对于这无限个解
0 < $\left|x^2-dy^2\right|=\left|x+y\sqrt{d}\right|\cdot\left|x-y\sqrt{d}\right|=\left|x-y\sqrt{d}+2y\sqrt{d}\right|\cdot\left|x-y\sqrt{d}\right|\leq (\left|x-y\sqrt{d}\right|+\left|2y\sqrt{d}\right|)\cdot\left|x-y\sqrt{d}\right|<\left(2y\sqrt{d}+\frac{1}{y}\right)\cdot\frac{1}{y}\le 2\sqrt{d}+\frac 1{y^2}$
说明这无限个(x,y)的取值,对$|x^2-dy^2|$的计算结果是有限范围内的整数
再一次根据抽屉原理，存在正整数k,使得$|x^2-dy^2|=k$的解有无限个
考虑这些解$(x \bmod k,y \bmod k)$ , 可以的方案数$\leq k^2$,也是有限的，
再根据抽屉原理，存在$(M_x,M_y)$，使得无限个i， $s.t. (x_i \bmod k, y_i \bmod k) = (M_x,M_y)$,在这无限组中取两组$(x_1,y_1),(x_2,y_2)$
令 $X=|\frac{x_1x_2-y_1y_2d}{k}|,Y=|\frac{x_2y_1-x_1y_2}{k}|$
有 $X^2-d \cdot Y^2 = \frac{(x_1^2-d \cdot y_1^2)(x_2^2-d \cdot y_2^2)}{k^2} = 1$
因为 $(x_2y_1-x_1y_2)\bmod k = (x_1y_1-x_1y_1) \bmod k = 0 \bmod k = 0$,所以Y是整数
因为$X$是有理数且满足pell方程，所以它是整数
显然$X = \sqrt{1+dY^2}$ 不为0
注意到 $x^2-dy^2$ 的取值范围为 $\pm k$ (有限个 ，2个)，但可取的$(x,y)$有无限对，再一次抽屉原理,因此存在$(x_i,y_i)\neq(x_j,y_j)$使得 $x_i^2-dy_i^2=x_j^2-dy_j^2$ 这时 $\frac{x_i}{y_i} \neq \frac{x_j}{y_j}$ (否则代入前式子得到$x_i=x_j$), 即Y不为0,Y为正整数
综上，一定存在解
关于 pell方程 ，我们现在有了 一定存在解，且存在一个最小解的基础解，两个结论，下面开始看看连分数。
形如
$\alpha = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \cfrac{1}{\ddots,}}}} $
例如
$ \sqrt{2} = 1 + \frac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2 + \ddots}}}}}} $
展开的剩余部分是在[0,1)之间
证明：如果一个数是有理数，把它写成分数的形式，再按照连分数的方式展开，你会发现这过程就是辗转相除，分子分母单调递减 所以一定有限，它的逆否命题就是要证明的性质
渐进分数，把上述表示无理数$\alpha$的连分数部分截断所得到的分数
假设h,k分别为渐进分数的分子和分母,根据简化为分数的过程
$\begin{bmatrix} h_n & k_n \end{bmatrix} = \begin{bmatrix} 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_n & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{n-1} & 1 \\ 1 & 0 \end{bmatrix} \cdots \begin{bmatrix} a_0 & 1 \\ 1 & 0 \end{bmatrix} $
然而这不好建立递推关系,稍做变形
$\begin{bmatrix} h_n & k_n \\ ? & ? \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} a_n & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{n-1} & 1 \\ 1 & 0 \end{bmatrix} \cdots \begin{bmatrix} a_0 & 1 \\ 1 & 0 \end{bmatrix} $
$\begin{bmatrix} h_n & k_n \\ ? & ? \end{bmatrix} = \begin{bmatrix} a_n & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{n-1} & 1 \\ 1 & 0 \end{bmatrix} \cdots \begin{bmatrix} a_0 & 1 \\ 1 & 0 \end{bmatrix} $
$\begin{bmatrix} h_n & k_n \\ ? & ? \end{bmatrix} = \begin{bmatrix} a_n & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} h_{n-1} & k_{n-1} \\ ? & ? \end{bmatrix} $
显然左式的底部可以确定
$\begin{bmatrix} h_n & k_n \\ h_{n-1} & k_{n-1} \end{bmatrix} = \begin{bmatrix} a_n & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} h_{n-1} & k_{n-1} \\ ? & ? \end{bmatrix} $
又因为递推关系，右边式子相当于左式带入n-1
$\begin{bmatrix} h_n & k_n \\ h_{n-1} & k_{n-1} \end{bmatrix} = \begin{bmatrix} a_n & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} h_{n-1} & k_{n-1} \\ h_{n-2} & k_{n-2} \end{bmatrix} $
综上
$h_n = a_n \cdot h_{n-1} + h_{n-2}$
$k_n = a_n \cdot k_{n-1} + k_{n-2}$
渐进值 $\frac{h_n}{k_n} = \frac{a_n \cdot h_{n-1} + h_{n-2}}{a_n \cdot k_{n-1} + k_{n-2}}$
且根据计算过程，可知 $h_n,k_n$互质
由上面的递推关系再递推有
$k_nh_{n-1}-k_{n-1}h_n=-(k_{n-1}h_{n-2}-k_{n-2}h_{n-1})=(-1)^n $,
$k_nh_{n-2}-k_{n-2}h_n=a_n(k_{n-1}h_{n-2}-k_{n-2}h_{n-1})=a_n(-1)^{n-1} $,
设无理数$\alpha$ 的精确表示为$[a_0,a_1,…,a_n,x_{n+1}]$,即是最后$a_{n+1}$替换为精确的非整数值$x_{n+1}$,有$1\leq a_{n+1}<x_{n+1}<a_{n+1}+1,(n>=1)$
根据上方计算渐进值得到的公式，同理递推式有
$\alpha =\frac{x_{n+1}h_n+h_{n-1}}{x_{n+1}k_n+k_{n-1}} $
$\alpha - \frac{h_n}{k_n} =\frac{x_{n+1}h_n+h_{n-1}}{x_{n+1}k_n+k_{n-1}} -\frac{h_n}{k_n} $
$=\frac{h_{n-1}k_{n}-h_nk_{n-1}}{k_n(x_{n+1}k_n+k_{n-1})}$
$=\frac{(-1)^n}{k_n(x_{n+1}k_n+k_{n-1})}$
$|\alpha -\frac{h_n}{k_n}| =\frac{1}{k_n(x_{n+1}k_n+k_{n-1})} < \frac{1}{k_n(a_{n+1}k_n+k_{n-1})} = \frac{1}{k_nk_{n+1}}$
注意到k的递推式，容易发现它是单调递增的正整数,所以渐进分数真的是趋近(n趋于无限大，渐进分数趋进原无理数)
$|k_n\alpha - h_n|$单调递减。
证明:
$|k_n\alpha - h_n| - |k_{n-1}\alpha - h_{n-1}|$
$ = |k_n(\alpha - \frac{h_n}{k_n})| - |k_{n-1}(\alpha - \frac{h_{n-1}}{k_{n-1}})|$
$ = \frac 1{x_{n+1}k_n+k_{n-1}} - \frac 1{x_{n}k_{n-1}+k_{n-2}} $
$ = \frac {(x_{n}k_{n-1}+k_{n-2})-(x_{n+1}k_n+k_{n-1})}{(x_{n+1}k_n+k_{n-1})(x_{n}k_{n-1}+k_{n-2})}$
$ = \frac {((a_n+\frac 1{x_{n+1}})k_{n-1}+k_{n-2})-(x_{n+1}k_n+k_{n-1})}{(x_{n+1}k_n+k_{n-1})(x_{n}k_{n-1}+k_{n-2})}$
$ = \frac {(x_{n+1}(a_nk_{n-1}+k_{n-2})+k_{n-1})-x_{n+1}(x_{n+1}k_n+k_{n-1})}{x_{n+1}(x_{n+1}k_n+k_{n-1})(x_{n}k_{n-1}+k_{n-2})}$
$ = \frac {(x_{n+1}k_n+k_{n-1})-x_{n+1}(x_{n+1}k_n+k_{n-1})}{x_{n+1}(x_{n+1}k_n+k_{n-1})(x_{n}k_{n-1}+k_{n-2})}$
$ = \frac {(1-x_{n+1})(x_{n+1}k_n+k_{n-1})}{x_{n+1}(x_{n+1}k_n+k_{n-1})(x_{n}k_{n-1}+k_{n-2})} < 0$
由此也可知$|\alpha - \frac{h_n}{k_n}|$单调递减
$|\alpha - \frac{h_n}{k_n}|-|\alpha -\frac{h_{n-1}}{k_{n-1}}|$
$=\frac {|{k_n}\alpha-{h_n}|-\frac {k_n}{k_{n-1}}|{k_{n-1}}\alpha-{h_{n-1}}|}{k_n}$
$<\frac {|{k_n}\alpha-{h_n}|-|{k_{n-1}}\alpha-{h_{n-1}}|}{k_n} < 0$
// 或者因为$k_n$单调递增
若$(h_n,k_n)$是一个渐进分数，则对于分母$k_n$,分子取$h_n$时，整个分数最接近原无理数
取任意$h\neq h_n$,根据三角不等式
$|\alpha -\frac{h}{k_n}| \geq |\frac{h-h_n}{k_n}| - |\alpha - \frac{h_n}{k_n}|$
$>\frac 1{k_n} - \frac 1{k_nk_{n+1}} $,因为n足够大 $k_{n+1}>=3$有
$> \frac 1{k_n} - \frac 1{2k_n} $
$=\frac 1{2k_n} $
$> \frac 1{k_nk_{n+1}} > |\alpha -\frac{h_n}{k_n}|$
证明了$h_n$是最接近的分子
即 $|k_n\alpha - h|$在 $h=h_n$时取最小值
下面证明在$(0<k\leq k_n)$中，对于所有$(h,k)$，有$|k_n\alpha - h_n|$为最小值
考虑任意$(h,k),(0<k<k_n)$，且$\frac hk$的最简分数不是渐进数，（因为已经证明了渐进数随着n增大$|k\alpha - h|$单调递减，且渐进数分子分母互质，所以如果最简分数是渐进数则对应渐进数的该表达式 更大，又是分子分母是渐进数的倍数，则该表达式的结果还要乘上倍数会更大）
// 同时它是最简分数，因为上表达式 带入分数和其最简分数得到的值刚好是其分子和其最简分数的分子的比值的倍数
设二元一次方程组
$h_nx+h_{n-1}y=h$
$k_nx+k_{n-1}y=k$
则有$(x,y)=(\frac {hk_{n-1}-kh_{n-1}}{h_nk_{n-1}-h_{n-1}k_n},\frac {hk_{n}-kh_{n}}{h_nk_{n-1}-h_{n-1}k_n}) = ((-1)^{n-1}(hk_{n-1}-kh_{n-1}),(-1)^{n-1}(hk_{n}-kh_{n}))$
因为$\frac hk$不是渐进分数，所以$x,y$都是非零整数，又因为$k<k_n$和$k_nx+k_{n-1}y=k$有:$x,y$异号
因为$\alpha - \frac {h_n}{k_n}$的分子为$(-1)^n$,分母为正数,
因此$\alpha - \frac {h_n}{k_n}$和$\alpha - \frac {h_{n-1}}{k_{n-1}}$异号
$k_n\alpha - {h_n}$和$k_{n-1}\alpha - {h_{n-1}}$异号
$x(k_n\alpha - {h_n})$和$y(k_{n-1}\alpha - {h_{n-1}})$同号
$|k\alpha -h| = |(k_nx+k_{n-1}y)\alpha - (h_nx+h_{n-1}y)|$
$= |x(k_n\alpha - {h_n}) + y(k_{n-1}\alpha - {h_{n-1}})|$,因为同号：
$= |x(k_n\alpha - {h_n})|+|y(k_{n-1}\alpha - {h_{n-1}})|$，因为$x,y$非零整数:
$|k\alpha - h| > |k_n\alpha - {h_n}|$且$|k\alpha -h|>|k_{n-1}\alpha - {h_{n-1}}|$
内容得证
至于为什么是这个标题 见后面的部分
连续的两个渐进数中至少有一个满足，$|\alpha - \frac hk|<\frac 1{2k^2}$
证明:
假设都不满足，有
$0 \leq |\alpha-\frac{h_{n+1}}{k_{n+1}}| - \frac{1}{2k_{n+1}^2} + |\alpha-\frac{h_{n}}{k_{n}}|-\frac{1}{2k_{n}^2}$, 因为$\alpha - \frac{h_{n}}{k_{n}}$正负交替,所以
$ = |\frac{h_{n+1}}{k_{n+1}}-\frac{h_{n}}{k_{n}}|-\frac 1{2k_{n+1}^2} -\frac 1{2k_{n}^2}$
$ = |\frac{h_{n+1}k_{n}-h_{n}k_{n+1}}{k_{n+1}k_{n}}|-\frac 1{2k_{n+1}^2} -\frac 1{2k_{n}^2}$
$ = \frac 1{k_nk_{n+1}} -\frac 1{2k_{n+1}^2} -\frac 1{2k_{n}^2}$
$ = \frac 1{k_nk_{n+1}} -\frac 1{2k_{n+1}^2} -\frac 1{2k_{n}^2}$
$ = \frac {-(k_n-k_{n+1})^2}{2k_{n}^2k_{n+1}^2} < 0$
矛盾
因此至少有一个大于满足 得证
任何最简分数如果满足$|\alpha - \frac hk|<\frac 1{2k^2}$，那么它是个渐进分数
证明
设$\frac hk$满足不等式$|\alpha - \frac hk|<\frac 1{2k^2}$，则存在n使得渐进数分母满足 $k_{n+2}>k>=k_n $且$\frac {h_n}{k_n}$满足$|\alpha - \frac hk|<\frac 1{2k^2}$(因为相邻渐进数必有一个满足,这里是取n和n+2之间)，根据上面的不等式 有$|k_n\alpha- h_n| < |k\alpha - h|$，若$\frac hk \neq \frac{h_n}{k_n}$,即$k_n < k$
$0 \leq \frac{|hk_n-h_nk|-1}{kk_n}$
$= |\frac{h}{k}-\frac{h_n}{k_n}|-\frac{1}{kk_n}$,因为三角不等式，有
$\leq |\alpha -\frac{h}{k}|+|\alpha -\frac{h_n}{k_n}|-\frac{1}{kk_n}$, 因为假设满足的不等式
$< \frac 1{2k^2} + \frac 1{k_n}|k_n\alpha - h_n|-\frac{1}{kk_n}$,因为上面的最小接近
$< \frac 1{2k^2} + \frac 1{k_n}|k\alpha - h|-\frac{1}{kk_n}$
$= \frac 1{2k^2} + \frac {k}{k_n}|\alpha - \frac hk|-\frac{1}{kk_n}$因为假设满足的不等式
$< \frac 1{2k^2} + \frac {k}{k_n}\cdot \frac 1{2k^2}-\frac{1}{kk_n}$
$= \frac {k_n-k}{2k^2k_n} < 0$
矛盾，因此$\frac hk$和某个渐进数相等
注记：最开始该文的版本，的渐进分数的部分直接使用的是pell方程中$\sqrt{d}$,其中d是非平方正整数，但为了写100需要的证明，需要把它扩充到实数，（当然也是成立的），所以这部分改写了一次
quadratic irrational(二次无理数) : 二次整式多项式的根 $\frac{-b\pm \sqrt{b^2-4ac}}{2a}$ 或者形如$\frac{P+\sqrt{D}}{Q}$
An irrational number is quadratic irrational if and only if its continued fraction is periodic.
先证明简单的一侧，循环连分数一定是二次根式的根。
按照连分数的写法，将循环节设为t
显然还原为分数,有$x=\frac{a t + b}{c t +d},t = \frac{et+f}{gt+h}$ 变换左表达式t是x的函数，带入右侧表达式得到$\frac{ix+j}{kx+l} = \frac{mx+n}{ox+p}$,其中字母$a-p$均为整数，且注意到x为无理数，所以化简后一定是二次方程
再证明二次根式的根一定能表达为有循环节的连分数
定义,u对于无理数x
$f(x) = x-1 (x>1)$
$f(x) = \frac{1}{\frac{1}{x}-1} , (x<1)$
对应到连分展开，即是将首个数字减少1,(x>1时就是a0减去1,x<1时就是a1减去1)
令$x1=x,x_{n+1}=f(x_n)$,可以知道 这是一个无限数列
如果x满足$ax^2+bx+c=0$,写作$x\in[a,b,c]$
那么x-1 满足$a(x-1)^2+(2a+b)(x-1)+(a+b+c) = ax^2+b+c=0$
那么$\frac{x}{1-x}$ 满足$(a+b+c)(\frac{x}{1-x})^2+(b+2c)\frac{x}{1-x}+c = 0$
所以f(x)满足 $f(x)\in [a,2a+b,a+b+c]$ 或 $f(x)\in [a+b+c,b+2c,c]$
不失一般性，写作$x_n\in[s_n,t_n,u_n]$,有 $s_n > 0$, 否则把三元组同时换号
注意到上式 $(2a+b)^2-4a(a+b+c)=b^2-4ac=(b+2c)^2-4(a+b+c)c$
说明了 $t_n^2-4s_nu_n$是和n无关的值
如果只有有限个$u<0$,那么从某一处开始，$s>0,u>0$且$t<0$(因为 x > 0)
那么意味着 $-t$ 严格单调递减并且非负，(因为 t的变化关系是 t=2s+t或者 t=t+2u),矛盾
所以有无限个$s_nu_n<0$
注意到 $t_n^2-4s_nu_n$是常数，所以 至少有一个三元组$[s_n,t_n,u_n]$ 出现了三次,一个二次方程有两个解，所以有满足的$x_n=x_m,m>n$
得证 连分数展开有循环
Theorem 1. If x is a positive quadratic irrational then its continued fraction is eventually periodic.
Definition 1.24. x 是二次无理数的根，$\overline{x}$ 是另一个根，那么如果 x > 1 且 $-1 < \overline{x} < 0$.那么称 x 为 reduced
Theorem 1.25. (Galois’ Theorem) 无理数a. a是纯循环连分数（从a0开始的循环节），当且仅当 x is reduced. If $x = [\overline{a_0, a_1, a_2, . . . , a_{l−1}}]$ and $\overline{x}$ 是它共轭实数, then $-\frac{1}{x} = [\overline{a_{l−1}, . . . , a_2, a_1}].$
设二次无理数$x=[a_0,a_1,…,a_n], x>1,-1<\overline{x}<0$
那么有 $x_{n+1}=\frac{1}{x_n-a_n}$ // 表示 按照展开从n处向后取值
$\overline{x_{n+1}} = \frac{1}{\overline{x_n-a_n}} = \frac{1}{\overline{x_n}-a_n}$,(因为 两个形如$A+B\sqrt{C}$的无理数相乘为有理数，说明相乘后的无理数的系数为0,所以更改其中一个无理数的系数的正负，另一个无理数系数的正负更改即可)
注意到$x_1 \ge 1$有$a_0 \ge 1$,所以 $a_n \ge 1$
下面归纳证明 $-1 < \overline{x_n} < 0 $
若 $-1 < \overline{x_n} < 0$
有 $\frac{1}{\overline{x_{n+1}}} = \overline{x_n} - a_n < -1$
即 $-1 < \overline{x_{n+1}} < 0$，得证
$-1 < \overline{x_n} = \frac{1}{\overline{x_{n+1}}}+a_n < 0$
$ 1 > -\frac{1}{\overline{x_{n+1}}}-a_n > 0$
$ a_n = [ -\frac{1}{\overline{x_{n+1}}} ] $ // 也就是$a_n$等于分式的整数部分
因为上面已经证明 如果是二次无理数，那么必定有循环节，所以存在$x_i = x_j,(i < j )$
即$\overline{x_i}=\overline{x_j}$
即$a_{i-1}=[-\frac{1}{\overline{x_i}}]=[-\frac{1}{\overline{x_j}}] = a_{j-1}$
即$x_{i-1}=a_{i-1}+\frac{1}{x_i} = a_{j-1}+\frac{1}{x_j} = x_{j-1}$, 意义就是如果两个后缀相等，那么它们各向前一个 也相等，综上逐步迭代$a_0 =a_{j-i}$
因此证明了 如果一个二次无理数是 reduced，那么它是个纯循环连分数
首先有循环节的连分数一定是二次无理数（上面证过了)
因为是纯循环，所以$a_0 \ge 1$,所以$a_n \ge 1$,有$x > 1$
假设周期为n, 有 $x_n = x = [\overline{a_0,a_1,…,a_{n-1}}]$
根据上面推过的递推式 $x = \frac{x_nh_{n-1}+h_{n-2}}{x_nk_{n-1}+k_{n-2}} = \frac{xh_{n-1}+h_{n-2}}{xk_{n-1}+k_{n-2}}$
化简 $k_{n-1}x^2+(k_{n-2}-h_{n-1})x-h_{n-2}=0$
也就是证明这个方程除了x (我们已经有 $x>1$了)的另一个根$\overline{x}$满足$-1 < \overline{x} < 0$
$x = 0$时 原式子 $=-h_{n-2} < 0$
$x = 1$时 原式子
$= k_{n-1}+(h_{n-1}-k_{n-2})-h_{n-2}$
$= (a_{n-1}k_{n-2}+k_{n-3}) + (a_{n-1}h_{n-2}+h_{n-3}) -k_{n-2}-h_{n-2}$
$= (a_{n-1}-1)(h_{n-2}+k_{n-2}) + (h_{n-3}+k_{n-3}) $
$ > 0 $
说明了另一个根$-1 < \overline{x} < 0$
至此我们证明了 reduced 和 纯循环之间的 充要
最后证明 If $x = [\overline{a_0, a_1, a_2, . . . , a_{l−1}}]$ and $\overline{x}$ 是它共轭实数, then $-\frac{1}{x} = [\overline{a_{l−1}, . . . , a_2, a_1,a_0}].$
Step 1
考虑有限的连分数 $x = [a_0,a_1,…,a_n], y=[a_n,a_{n-1},…,a_0] , a_i > 0$
$h_n,k_n$为x的分子分母，$h_n’,k_n’$为y的分子分母
要证明 $\frac{h_n}{h_{n-1}} = \frac{h_n’}{k_n’}$ 且 $\frac{k_n}{k_{n-1}} = \frac{h_{n-1}’}{k_{n-1}’}, n \ge 1$ 且分子分母对应相等(因为是最简分数，所以只要证明了分数相等就有对应相等了)
注意到上面 $h_n = a_n \cdot h_{n-1} + h_{n-2}$,同时除以 $h_{n-1}$
$\frac{h_n}{h_{n-1}} = a_n + \frac{1}{\frac{h_{n-1}}{h_{n-2}}}$
递归展开 可以得到 $\frac{h_n}{h_{n-1}} = [a_n,a_{n-1},…,a_0]$,
注意到 $k_n = a_n \cdot k_{n-1} + k_{n-2}$,同理 $\frac{k_n}{k_{n-1}} = [a_n,a_{n-1},…,a_1] $(注意是$a_1$不是$a_0$)
根据上面的递归展开的结论 和 y的分子分母定义有
$\frac{h_{n+1}}{h_n} = [a_{n+1},a_n,…,a_0] = \frac{h_{n+1}’}{k_{n+1}’}$
$\frac{k_{n+1}}{h_n} = [a_{n+1},a_n,…,a_1] = \frac{h_{n}’}{k_{n}’}$
且分子分母对应相等
Step 2
若x 是纯循环连分数数(即reduced 二次无理数)，那么显然$-\frac{1}{\overline{x}}$也是 reduced的二次无理数，那么它也是纯循环
假设直接取 n+1 = 两个循环节长度的最小公倍数
$k_{n}x^2+(k_{n-1}-h_{n})x-h_{n-1}=0$
令
$y = [\overline{a_n,a_{n-1},…,a_0}] = [a_n,a_{n-1},…,a_0,y]$
$y = \frac{h_n’y+h_{n-1}’}{k_n’y+k_{n-1}’}$
因为Step 1 我们证明了对应相等$h_n=h_n’,k_{n-1}=k_{n-1}’, h_{n-1}=k_{n}’,h_{n-1}’=k_n$
所以做对应替换,$y = \frac{h_ny+k_{n}}{h_{n-1}y+k_{n-1}}$
$k_{n}{(-\frac{1}{y})}^2+(k_{n-1}-h_{n})(-\frac{1}{y})-h_{n-1}=0$
$-\frac{1}{y} = \overline{x}$ 得证(y为正 所以 不可能等于x)
至此 Theorem 1.25. (Galois’ Theorem) 无理数a. a是纯循环连分数（从a0开始的循环节），当且仅当 x is reduced. If $x = [\overline{a_0, a_1, a_2, . . . , a_{l−1}}]$ and $\overline{x}$ 是它共轭实数, then $-\frac{1}{\overline{x}} = [\overline{a_{l−1}, . . . , a_2, a_1}].$ 得证
Theorem 1.26 d是非平方数,那么$\sqrt{d} = [\lfloor \sqrt{d} \rfloor,\overline{a_1,a_2,…,a_2,a_1,2\lfloor \sqrt{d} \rfloor}]$
也就是 是从第二位开始循环节，且循环节最后一个是它的整部的2倍，且剩余部分是回文
令$x=\lfloor \sqrt{d} \rfloor + \sqrt{d}$ 则$\overline{x} = \lfloor \sqrt{d} \rfloor - \sqrt{d}$
注意它们的取值范围发现x是reduced 二次无理数
因此 $ x = \lfloor \sqrt{d} \rfloor + \sqrt{d} = [\overline{2\lfloor \sqrt{d} \rfloor,a_1,a_2,…,a_{l-1}}]$
$ = [2\lfloor \sqrt{d} \rfloor,\overline{a_1,a_2,…,a_{l-1},2\lfloor \sqrt{d} \rfloor}]$
$ \sqrt{d}= [\lfloor \sqrt{d} \rfloor,\overline{a_1,a_2,…,a_{l-1},2\lfloor \sqrt{d} \rfloor}]$
根据Galois’ Theorem我们有
$\frac{1}{\sqrt{d}-\lfloor \sqrt{d} \rfloor} = -\frac{1}{\overline{x}} = [\overline{a_{l-1},…,a_2,a_1,2\lfloor \sqrt{d} \rfloor}]$
也就是$\sqrt{d} = [\lfloor \sqrt{d} \rfloor,\frac{1}{\sqrt{d}-\lfloor \sqrt{d} \rfloor}]$
$ = [\lfloor \sqrt{d} \rfloor,\overline{a_{l-1},…,a_2,a_1,2\lfloor \sqrt{d} \rfloor}]$
因此得证 循环内容和 回文性质
因为平方带来的对称性，只考虑(x>0,y>0)的解
若d为非平方数，$x=\sqrt{d}$,
则对于任意n，存在整数$Q_n,P_n$满足$ x_n=\frac{P_n+\sqrt{d}}{Q_n}$和$d-P_n^2 = 0 (\bmod Q_n)$
显然n=0时$(P_0,Q_0) = (0,1)$满足,然后归纳法，若 n时能满足上述两点性质，则
$x_{n+1} = \frac{1}{x_n-a_n}$
$=\frac{1}{\frac{P_n+\sqrt{d}}{Q_n}-a_n}$
$=\frac{Q_n}{P_n+\sqrt{d}-a_n{Q_n}}$ (通过分母有理化:
$=\frac{Q_n(P_n-a_nQ_n-\sqrt{d})}{(P_n-a_nQ_n)^2-d}$
$=\frac{a_nQ_n-P_n+\sqrt{d}}{\frac{d-(P_n-a_nQ_n)^2}{Q_n}}$
$(Q_{n+1},P_{n+1}) = (\frac{d-(P_n-a_nQ_n)^2}{Q_n},a_nQ_n-P_n)$
现在要证明的就是 它是满足$\frac{P_{n+1}+\sqrt{d}}{Q_{n+1}}$的形式,并且满足上面的取模
也就是要证明$P_{n+1}$是整数(显然) 和 $Q_{n+1}$是整数
$Q_{n+1} = \frac{d-P_n^2}{Q_n}+2a_nP_n-a_n^2Q_n$
因为n时有 $d-P_n^2 = 0 (\bmod Q_n)$所以 $Q_{n+1}$是整数
又因为$Q_nQ_{n+1}=d-P_{n+1}^2$ 所以 $d-P_{n+1}^2 = 0 (\bmod Q_{n+1})$ 得证
对于$n \ge 2$ 要证明 $h_{n-1}^2-d k_{n-1}^2=(-1)^n Q_n$
证明:
$\sqrt{d} = \frac{x_n h_{n-1}+h_{n-2}}{x_nk_{n-1}+k_{n-2}}$
把$ x_n = \frac{P_n+\sqrt{d}}{Q_n}$带入并通分化简
$(P_nk_{n-1}+Q_nk_{n-2}-h_{n-1})\sqrt{d} = P_nh_{n-1}+h_{n-2}Q_n-k_{n-1}d$
即 $P_nk_{n-1}+Q_nk_{n-2}=h_{n-1}$ 且 $P_nh_{n-1}+h_{n-2}Q_n=k_{n-1}d$
所以有 $h_{n-1}^2-dk_{n-1}^2 = h_{n-1}(P_nk_{n-1}+Q_nk_{n-2})-k_{n-1}(P_nh_{n-1}+h_{n-2}Q_n)$
$= Q_n(h_{n-1}k_{n-2}-h_{n-2}k_{n-1})$
$= (-1)^nQ_n$
首先假设 (x,y)是 pell方程$x^2-dy^2=1$的解$(d>1,x>y>0)$，所以
$|\sqrt{d} - \frac{x}{y}| = |\frac{dy^2-x}{y^2(\sqrt{d}+\frac{x}{y})}| < \frac{1}{2y^2}$ (从一定程度上说明了 为什么前面要去证明 小于$\frac{1}{2y^2}$
根据前面推的 我们知道满足这个表达式的一定是 渐进值
(Yang.pdf那个paper下面的部分蛮多笔误的 不过能看懂证明思路)
因为我们上面有 $h_{n-1}^2-dk_{n-1}^2=(-1)^nQ_n$ 也就是如果要满足pell方程 那么$|Q_n|=1$，分类讨论$Q_n$
假设 $\sqrt{d}$的 最小周期长度为l
$Q_n \neq -1, n > 0$
证明
注意到上面根据$\sqrt{d}$的表达式 证明了$n>0$时，$x_n$是纯循环连分数，也就是reduced
如果$Q_n = -1$ 因为$x_n=\frac{P_n+\sqrt{d}}{Q_n}$,所以有 $x_n=-P_n-\sqrt{d} > 1$,有$-1<-P_n+\sqrt{d} < 0$ (Galois)
有 $\sqrt{d} < P_n < -\sqrt{d} - 1$ 矛盾 所以$Q_n \neq -1$, 对于$Q_0 = 1$也满足,得证
$Q_n = 1$当且仅当n为循环节长度的倍数才有
证明
若于$n>1$若$Q_n=1$那么有$x_n=P_n+\sqrt{d}$，它的共轭 $-1 < P_n-\sqrt{d} < 0$ 即 $P_n=\lfloor \sqrt{d} \rfloor$所以 $x_n = \lfloor \sqrt{d} \rfloor + \sqrt{d}$
$ \lfloor \sqrt{d} \rfloor +\sqrt{d} = x_n = 2\lfloor\sqrt{d}\rfloor + \frac{1}{\frac{1}{\sqrt{d} - \lfloor \sqrt{d} \rfloor}} $ 即 $ x_{n+1} = \frac{1}{\sqrt{d} - \lfloor \sqrt{d} \rfloor}$
$ \sqrt{d} = x_0 = \lfloor \sqrt{d} \rfloor + \frac{1}{\frac{1}{\sqrt{d} - \lfloor \sqrt{d} \rfloor}}$ 即 $x_1 = \frac{1}{\sqrt{d} - \lfloor \sqrt{d} \rfloor}$
说明了 它的下一个数$x_{n+1} $和$x_1$相等, 这说明如果$Q_n = 1$ 那么n是当且仅当循环节长度的倍数(如果为1则循环节长度)
如果n是循环节倍数 有
$\frac{P_{kl}+\sqrt{d}}{Q_{kl}} = x_{kl} = [\overline{2\lfloor \sqrt{d} \rfloor,a_1,a_2,…,a_{l-1}}] = \sqrt{d}+\lfloor\sqrt{d}\rfloor,(k>0)$
$(P_{kl},Q_{kl}) = (\lfloor\sqrt{d}\rfloor,1)$
对于n=0也满足，充要得证
最后回到这里 $h_{n-1}^2-dk_{n-1}^2=(-1)^nQ_n = (-1)^n $ 也就是再看个奇偶，最后得到了pell方程和连分数比较紧密的结论
假设 $\sqrt{d}$的 最小周期长度为l
那么对应pell 方程的最小解
$(x,y) = {h_{l-1},k_{l-1}}$ 长度为偶数
$(x,y) = {h_{2l-1},k_{2l-1}}$ 长度为奇数
方法涉及
然后还有很多整数的离散性质
证明过程感受
似乎还不足以写代码?，下面的问题是 如何得到根号n的连分数呢？ 手工三元组(分母整数，有理分子整数，无理分子的系数整数)是一个办法，有没有更好的办法呢。
但我们至少说能证明了这个结论
python3
1 | def gcd(a, b): |
可以看到x的值会达到十进制的38位，暴力不可取!即使用了上面分析出的一些晓得性质最多优化661倍 依然是能有10的35次方的数量级。
millersville periodic-continued-fractions
YouTube:Number Theory:Pell’s Equation part 1
A short proof and generalization of Lagrange’s theorem on continued fractions
purely periodic continued fractions
有些结论在证明过程中其实是缩小了范围，有些结论其实放大定义域之类也是成立的，但我们在证明过程中却只使用了我们所需要的部分。这类的从定义域和对应的要证明的逻辑不是“完美对应”的，但是足够，不知道是好还是不好。
证明的结论之间引用过程，感觉画成网状或者树状关系图会更好？
看youtube了上的讲解视频，会发现有一种写代码的抽取函数感觉，和我上面完全拆开证明不一样，抽函数的感觉其实在数学里大概是叫做“令”+“引理”，感觉和完全展开比较，的确能减少很多心智负担啊！如果你也能打开youtube建议去看看
另外比如有些 强结论要用的时候，即使你证出了相对弱的结论，但没有证明出强结论，其实相当于“没有用”，比如上面 基础解，的平方，的n次方，和任意另一组解能产生新的解的证明。当然如果能证明出，那些就是过程了，但不是步骤（虽然我上面有写进文中，因为要简洁整理的话，直接强结论证明，即可其它的弱的可以直接省略
虽然视频看的时候的确感觉到老师和同学的口算不如国内，但自从自己思考过十进制的意义以后，感觉数值计算都不再重要，有的是计算机，不需要人类来算。
youtuber james cook 有证明一个 同系数二元二次方程 之间的关系，可以用它来 从 不是解的东西里生成解(感觉好像不是特别行，因为一个等式的 四个值仅仅由两个变量控制而不是3个？)！(Quadradic Forms) Q(u+v)+Q(u-v)=2(Q(u)+Q(v)),然后以此建立树，考虑其中的“正负交替路线”river
多核没智力还是搞不动数学啊,
这篇文章整理了很多篇其它资料，所以在符号使用上还不够统一，之后看有空整理一下
在我快写完这一篇文章的时候发现了 一个超理论坛-连分数入门 注册需要一点点水平XD，这篇是带着例子讲解写的！(大自看了一下 感觉很棒 推荐), 又 有些性质证明方式不止一种，例如我本篇文章所抄来的证明 二次无理数和有循环节的充要 会感觉更漂亮一些
有些paper写到后面还是很多笔误，不过看通了也是能理解具体过程
有一个想法是 哪些结论是关键或者说证明的难点，其实可以这样想，现在，把文章中一些部分换成填空，你还能不能补全整个文章，不需要完全一样，只要能证明就行。这样想的话，就会知道所谓的难点是在哪。