Farey 序列
Farey 序列是指集合
\[
\mathcal{F}_n=\{\frac{a}{b}\mid 0\leq a\leq b\leq n,\ (a,b)=1\}
\]
按从小到大顺序排列而得的一个分数序列. Farey 序列形如:
$\mathcal{F}_1$ 为
\[\frac{0}{1}\quad\frac{1}{1}\]
$\mathcal{F}_2$ 为
\[\frac{0}{1}\quad\frac{1}{2}\quad\frac{1}{1}\]
$\mathcal{F}_3$ 为
\[
\frac{0}{1}\quad\frac{1}{3}\quad\frac{1}{2}\quad\frac{2}{3}\quad\frac{1}{1}
\]
$\mathcal{F}_4$ 为
\[
\frac{0}{1}\quad\frac{1}{4}\quad\frac{1}{3}\quad\frac{1}{2}\quad\frac{2}{3}\quad\frac{3}{4}\quad\frac{1}{1}
\]
$\mathcal{F}_5$ 为
\[
\frac{0}{1}\quad\frac{1}{5}\quad\frac{1}{4}\quad\frac{1}{3}\quad\frac{2}{5}\quad\frac{1}{2}\quad\frac{3}{5}\quad\frac{2}{3}\quad\frac{3}{4}\quad\frac{4}{5}\quad\frac{1}{1}
\]
易见,
\[
\begin{array}{rcl}
\mathcal{F}_n&\rightarrow&\mathcal{F}_n\\
\frac{h}{k}&\mapsto&\frac{k-h}{k}
\end{array}
\]
是一一映射, 并将 $\mathcal{F}_n$ 中的元素进行了逆序排列.
如果不考虑 $\mathcal{F}_n$ 中的 0, 并把任何数 $\frac{a}{b}$ 的倒数也放在其中, 组成一个序列, 记为 $\mathcal{G}_n$, 则它们形如
$\mathcal{G}_1$ 为
\[\frac{1}{1}\]
$\mathcal{G}_2$ 为
\[\frac{1}{2}\quad\frac{1}{1}\quad\frac{2}{1}\]
$\mathcal{G}_3$ 为
\[
\frac{1}{3}\quad\frac{1}{2}\quad\frac{2}{3}\quad\frac{1}{1}\quad\frac{3}{2}\quad\frac{2}{1}\quad\frac{3}{1}
\]
$\mathcal{G}_4$ 为
\[
\frac{1}{4}\quad\frac{1}{3}\quad\frac{1}{2}\quad\frac{2}{3}\quad\frac{3}{4}\quad\frac{1}{1}\quad\frac{4}{3}\quad\frac{3}{2}\quad\frac{2}{1}\quad\frac{3}{1}\quad\frac{4}{1}
\]
$\mathcal{G}_5$ 为
\[
\frac{1}{5}\quad\frac{1}{4}\quad\frac{1}{3}\quad\frac{2}{5}\quad\frac{1}{2}\quad\frac{3}{5}\quad\frac{2}{3}\quad\frac{3}{4}\quad\frac{4}{5}\quad\frac{1}{1}\quad\frac{5}{4}\quad\frac{4}{3}\quad\frac{3}{2}\quad\frac{5}{3}\quad\frac{2}{1}\quad\frac{5}{2}\quad\frac{3}{1}\quad\frac{4}{1}\quad\frac{5}{1}
\]
证明:
(1) 如果 $\frac{a}{b}< \frac{c}{d}$ 是 Farey 序列中两个相邻的分数, 则有 $ad-bc=-1$. (逆命题不成立.)
(2) 如果 $\frac{a}{b}< \frac{x}{y}< \frac{c}{d}$ 是 Farey 序列中的三个相邻的分数, 则有
\[\frac{x}{y}=\frac{a+c}{b+d}\]
并且 (1) 和 (2) 是等价的.
(3) 若 $\frac{a}{b}< \frac{c}{d}$ 是 $\mathcal{F}_n$ 中相邻的两个分数, 则 $b+d>n$.
(4) 如果 $n>1$, 则 $\mathcal{F}_n$ 中不存在具有相同分母的两个相邻的项(既约分数).
(5) $\mathcal{F}_{n-1}\subset\mathcal{F}_n$, 并且多出的部分是下面的集合
\[\biggl\{\frac{k}{n}\biggl| 1\leq k\leq n-1,\quad (k,n)=1\biggr\}.\]
因此若记 $f(n)$ 为 $\mathcal{F}_n$ 所含元素的个数, 则 $f(n)=f(n-1)+\varphi(n)$, 其中 $\varphi(n)$ 指 1 到 $n$ 中与 $n$ 互素的正整数个数. 从而
\[f(n)=1+\sum_{k=1}^{n}\varphi(k).\]
若记 $g(n)$ 为 $\mathcal{G}_n$ 所含元素的个数, 则 $g(1)=1$, $g(2)=3$, $g(3)=7$, $g(4)=11$, $g(5)=19$. 求 $g(n)$ 的表达式.
References:
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. (《哈代数论》张明尧，张凡 译)