数列 \(F_1=(0/1, 1/1)\) と置く。\(F_{n-1}\) の隣接する既約分数 \(a/b,c/d\) であって、\(b+d = n\) が成り立つものの間に \((a+c)/(b+d)\) を挿入したものを \(F_n\) と置く。分母が n の既約分数は全て \(F_n\) に含まれる。また、隣接する既約分数 a/b, c/d の間には \(|ad-bc|=1\) が成り立つ。

証明（Hardy&WrightのAn Introduction to the Number Theory）：既約分数 \(a/b\) をベクトル (a b) と見なす。a/b, c/d が隣接しているとする。|ad-bc|=1 ならば \begin{pmatrix}a & c \\ b & d\end{pmatrix} はユニモジュラー行列なので、ベクトル (a b), (c d) は格子全体を張り、全単射。さもなくば、（0, 0), (a, b), (c d), (a + c, b + d) のなす平行四辺形に、これ以外の格子 p = s(a b) + t(c d) が存在する。p か (a b) + (c d) – p のどちらかが (0, 0), (a, b), (c, d) のなす三角形の、これ以外の格子点である。よって、\(|ad – bc| = 1\) が必要（Pickの定理でも良い）■

\((0, 1)\) の有理数を頂点、\(1/2\) を根として、Farey数列で a/b, (a+c)/(b+d), c/d と並ぶとき、(a+c)/(b+d) の親を a/b, c/d のうち分母が大きい方とした木を Stern Brocot Treeと呼ぶ。Stern Brocot 木の根から、左子を \(a_1\) 回、右子を \(a_2\) 回、左子を \(a_3\) 回, .. だけ潜ったときの値は \(\frac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3+1/\cdots}}}\) となる。

証明：互除法を考えると、LCAは無視して足してもよい。\(\frac{0}{1}, \frac{1}{n+1}, \frac{1}{(n-1)+1}\) の場合（深さの偶奇で左右逆転）に帰着され、\(\frac{0}{1}, \frac{1}{n+1}\) の間の数は \(\frac{1}{(n+1)+1}\) で, \(\frac{1}{n+1}, \frac{1}{(n-1)+1}\) の間の数は \(\frac{1}{n+\frac{1}{1+1}}\) となる■

ABC333G
実数 \(r \in (0, 1)\) が与えられる。\(0 \leq p \leq q \leq N\) の下で \(|r-p/q|\) を最小にする \(p/q\) のうち最小のものを求めよ。

ABC273H
Stern Brocot木の頂点が N 個順番に指定される。L番目からR番目にかけて指定された頂点のシュタイナー木のサイズを、全てのL, Rについて和を取った値を求めよ。

ABC408G
a/b < x/y < c/d を満たす x/y のうち、y最小のものを求めよ。

Library Checker(min of mod of linear)
\(\min_{0 \leq x \leq N} \{ax + b \bmod m\}\) を求めよ。

Pell方程式

\(d\)を非平方数としたとき\(x^2-dy^2=1\)をPell方程式と呼ぶ。x, y は正整数とする。\(\gamma=a + b\sqrt{d} \in \mathbb{Z}[\sqrt{d}]\) の共役を \(\overline \gamma\ = a-b\sqrt{d}\) と置く。ノルムを \(N(\gamma)=\gamma \overline \gamma=a^2-b^2\) と置く。行列の det の準同型性から、\(N(\gamma \beta)=N(\gamma)N(\beta)\)。\(x^2-dy^2=1\) は \(\mathbb{Z}[\sqrt{d}]\) の非自明なノルム 1 の元。\(z_1,z_2 \in \mathbb{Z}[\sqrt{d}]\) について \(N(z_1)=N(z_2)=1\) とする。\(z_1^k \leq z_2 < z_1^{k+1}\) としても一般性を失わず、\(1 \leq z_1^{-k} z_2 < z_1\) なので、Pell方程式の解を冪乗で全て生成する最小の元がある。

\(|x/y – \sqrt{d}| < 1/y^2\) を満たす \(x/y\) は連分数展開により無限に見つかる。\(|(x/y)^2-d| < (\sqrt{d} + 1/y^2)^2-d = (2\sqrt{d}+ 1/y^2)/y^2\) なので、ある \(-2\sqrt{d}-1 \leq n \leq 2 \sqrt{d} + 1\) について \((x/y)^2-d = n/y^2 \iff N(x + \sqrt{d}y)=n\) を満たす \(x,y\) が無限に存在する。\(N(a)=N(b)=n\) とすると \(ab^{-1}=a \overline b / n \in \mathbb{Z}[\sqrt{d}]\) のノルム１で解が存在。

二次形式\(A=\begin{pmatrix}1 & 0 \\ 0 & -d\end{pmatrix}\) を、\(\begin{pmatrix}1 & 1 \\ 0 & 1\end{pmatrix}\), \(\begin{pmatrix}1 & 0 \\ 1 & 1\end{pmatrix}\\\) で (1,1) が正になるように合同変換を繰り返すと \(A\) に戻ることを利用すると Pell方程式の解が求まる(Wildberger。