11/21<n/(x+n)<10/19有唯一整数解，求最小n

kuing

有微信网友问：

若 `n\inN` 且关于 `x` 的不等式 `11/21<n/(x+n)<10/19` 有唯一整数解，问 `n` 的最小值。

我最先想到的是连分数
\[\frac{11}{21}<\frac n{x+n}<\frac{10}{19}\iff\frac9{10}<\frac xn<\frac{10}{11}\iff\frac1{1+\dfrac19}<\frac xn<\frac1{1+\dfrac1{10}},\]
那么最小的分母就是
\[\frac1{1+\dfrac1{9+\dfrac12}}=\frac{19}{21},\]
于是最小 `n=21`，相应的唯一的整数 `x=19`。

网友追问：为什么+1/2会是分母最小的？

我一时还真不知道怎么解释好，又不想扯太多……

算了，换个解法吧，于是搜了下论坛，就搜到了 这帖 和 这帖，参照后帖，另解如下：
\[\frac{11}{21}<\frac n{x+n}<\frac{10}{19}\iff\frac{9n}{10}<x<\frac{10n}{11}\iff\frac n{11}<n-x<\frac n{10},\]
那么相当于 `n/11<y<n/10` 有唯一整数解，于是有
\[\left[\frac n{11}\right]+1<\frac n{10}\leqslant\left[\frac n{11}\right]+2,\]
令 `n=11k+r`, `k\inN`, `r=0`, `1`, `\ldots`, `10`，上式化为
\[k+1<\frac{11k+r}{10}\leqslant k+2\iff10-r<k\leqslant20-r,\]
由此及 `r\leqslant10` 得 `k\geqslant11-r\geqslant1`，当 `k=1` 时 `r=10`, `n=21`，所以最小 `n` 就是 `21`。

我数论是渣渣，你们有啥更好嘀想法不妨写写

hbghlyj

Orthogonal Polynomials and Continued Fractions: From Euler's Point of View 1.3 Rational approximations
Continued Fractions and Hyperbolic Geometry by C Series · 2015

根据Stern–Brocot 树页面：
Stern–Brocot 树中数字之间的父子节点关系可以用连分数来理解。每个正有理数 $q$ 都可以表示为以下形式的连分数
$ {\displaystyle q=a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+{\cfrac {1}{\ddots +{\cfrac {1}{a_{k}}}}}}}}}}}=[a_{0};a_{1},a_{2},\ldots ,a_{k}]} $
其中 $k$ 和 $a_0$ 是非负整数，每个后续系数 $a_i$ 是正整数。这个表示法不是唯一的，因为
$ {\displaystyle [a_{0};a_{1},a_{2},\ldots ,a_{k-1},1]=[a_{0};a_{1},a_{2},\ldots ,a_{k-1}+1],} $
但使用这种等价关系将每个以 $1$ 结尾的连分数替换为更短的连分数表明，每个有理数都有一个唯一的表示形式，其中最后一个系数大于 $1$。然后，除非 $q = 1$，否则 $q$ 的父节点在 Stern–Brocot 树中由连分数表达式给出
$ {\displaystyle [a_{0};a_{1},a_{2},\ldots ,a_{k}-1].} $
同样，这个父节点是通过将连分数最内层项的分母减少 1 并与前一项收缩而形成的，如果分数变为 $ {\displaystyle 1/1} $。例如，有理数 $ {\displaystyle 23/16}$ 的连分数表示为
$ {\displaystyle {\frac {23}{16}}=1+{\cfrac {1}{2+{\cfrac {1}{3+{\frac {1}{2}}}}}}=[1;2,3,2],} $
所以它在 Stern–Brocot 树中的父节点是
$ {\displaystyle [1;2,3,1]=[1;2,4]=1+{\cfrac {1}{2+{\frac {1}{4}}}}={\frac {13}{9}}.} $

反过来，Stern–Brocot 树中的每个数字 $q$ 恰好有两个子节点：如果
$ {\displaystyle q=[a_{0};a_{1},a_{2},\ldots ,a_{k}]=[a_{0};a_{1},a_{2},\ldots ,a_{k}-1,1]} $
那么一个子节点是由连分数表示的数字
$ {\displaystyle \displaystyle [a_{0};a_{1},a_{2},\ldots ,a_{k}+1]} $
而另一个子节点由连分数表示
$ {\displaystyle [a_{0};a_{1},a_{2},\ldots ,a_{k}-1,2].} $
其中一个子节点小于 $q$，这是左子节点；另一个大于 $q$，这是右子节点（实际上，如果 $k$ 是奇数，前一个表达式给出左子节点，如果 $k$ 是偶数，则给出右子节点）。例如，$ {\displaystyle 13/9}$ 的连分数表示为 $[1;2,4]$，它的两个子节点是 $[1;2,5] = \frac{16}{11}$（右子节点）和 $[1;2,3,2] = \frac{23}{16}$（左子节点）。

显然，对于每个有限的连分数表达式，可以反复移动到其父节点，并在有限步内到达树的根 $[1;] = \frac{1}{1}$（准确地说，在 $a_0 + \ldots + a_{k-1}$ 步内）。因此，每个正有理数在这棵树中恰好出现一次。此外，任何数字 $q$ 的左子节点的所有后代都小于 $q$，而 $q$ 的右子节点的所有后代都大于 $q$。树中深度为 $d$ 的数字是连分数系数之和为 $d + 1$ 的数字。

kuing

hbghlyj 发表于 2025-1-18 21:19
Rational with minimal denominator between two rationals

我的连分数解法的内心想法也是这样，但是如何解释清楚最后的分母最小则化简后的分母也最小？

hbghlyj

kuing 发表于 2025-1-18 13:29
解释清楚最后的分母最小则化简后的分母也最小？ ...

定理：$a,b,c,d\inN^+,$
若 $\frac cd<\frac ab$，且 $ad-bc=1$，则 $\frac cd$ 和 $\frac ab$ 之间的任何分数的分母均不小于 $b+d$.

第一种证明：
设 $\frac xy\in(\frac cd,\frac ab)$ 且 $x,y\inN^+$，那么
$$0< \frac xy-\frac cd=\frac{dx-cy}{yd}$$
$$0< \frac ab-\frac xy=\frac{ay-bx}{yb}$$
即，分子是正整数，
$$dx-cy\ge1$$
$$ay-bx\ge 1$$
并且可以将其合并为
$$y=(ad-bc)y=b(dx-cy)+d(ay-bx)\ge b+d$$
第二种证明：
设 $\frac xy$ 为区间 $(\frac cd,\frac ab)$ 内分母最小的有理数，且 $x,y\inN^+$，那么
三角形 $(0,0),(a,b),(x,y)$ 内部没有任何格点，由Pick定理该三角形的面积为$\frac12$，即$ay-bx=1$.
三角形 $(0,0),(c,d),(x,y)$ 内部没有任何格点，由Pick定理该三角形的面积为$\frac12$，即$dx-cy=1$.
由$\cases{ay-bx=1\\dx-cy=1}$解得$\cases{x=a+c\\y=b+d}$

hbghlyj

楼上的证明的出处：
matrix67.com/blog/archives/2199
en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree
en.wikipedia.org/wiki/Mediant_(mathematics)

6 阶 Farey sunburst，有 1 个内部 (0,0) 点和 96 个边界点（对应 Farey 序列的每个项），由Pick定理面积为$$1 + ⁠\frac{96}2⁠ - 1 = 48$$

hbghlyj

binary search

kuing 发表于 2025-1-18 13:11 \[\frac9{10}<\frac xn<\frac{10}{11}\]

hbghlyj

例子：$(\pi-\frac1{700},\pi+\frac1{700})$得到 $\dfrac{22}7$

例子：$(\pi-\frac1{10^6},\pi+\frac1{10^6})$得到 $\displaystyle \frac{355}{113}$

例子：$(\pi-\frac1{10^{10}},\pi+\frac1{10^{10}})$得到 $\displaystyle \frac{312689}{99532}$

睡神

\[\frac{11}{21}=\frac1{1+\dfrac1{1+\dfrac1{9+1}}}<\frac1{1+\dfrac1{1+\dfrac1{9+\dfrac{10x-9n}{n-x}}}}<\frac1{1+\dfrac1{1+\dfrac1{9}}}=\frac{10}{19}\]

因为  不等式只有唯一的整数解

所以  $\begin{cases} n-x=2 \\ 10x-9n=1 \end{cases} \riff \begin{cases} n=21 \\ x=19 \end{cases}$

睡神

睡神 发表于 2025-1-18 22:31
\[\frac{11}{21}=\frac1{1+\dfrac1{1+\dfrac1{9+1}}}<\frac1{1+\dfrac1{1+\dfrac1{9+\dfrac{10x-9n}{n-x}}} ...

若改为有m个整数解

则  $\begin{cases} n-x=m+1 \\ 10x-9n=l \\l=1,\cdots ,m \end{cases} \riff \begin{cases} n=10m+11l \\ x=9m+10l \end{cases}$

kuing

睡神 发表于 2025-1-18 22:31
\[\frac{11}{21}=\frac1{1+\dfrac1{1+\dfrac1{9+1}}}<\frac1{1+\dfrac1{1+\dfrac1{9+\dfrac{10x-9n}{n-x}}} ...

这写法也挺好😀

kuing

那就是也可以这样写
\begin{align*}
\frac{11}{21}<\frac n{x+n}<\frac{10}{19}&\iff\frac{11}{21-2\cdot11}<\frac n{x+n-2n}<\frac{10}{19-2\cdot10}\\
&\iff-11<\frac n{x-n}<-10\\
&\iff11(n-x)>n>10(n-x),
\end{align*}
显然 `n-x=1` 时 `n` 不存在，所以 `n-x\geqslant2`，得 `n>20`，即 `n\geqslant21`😄

以上无需唯一解的条件，如果加上唯一解，那就只能 `n-x=2`（否则若 `n-x>2` 则至少有两个 `n`，相应地至少有两个 `x`），得 `n=21`。

hbghlyj

问题：$(\pi-\varepsilon,\pi+\varepsilon)$内，分母最小的有理数的分母的增长速率是？
$\varepsilon=\frac1{700}$得到 $\dfrac{22}7$，分母为$7$
$\varepsilon=\frac1{10^6}$得到 $\displaystyle \frac{355}{113}$，分母为$113$
$\varepsilon=\frac1{10^{10}}$得到 $\displaystyle \frac{312689}{99532}$，分母为$99532$

hbghlyj

它是否等于$\pi$表示为连分数的渐进分数的分母的增长速率
发到 chat.stackexchange.com/transcript/message/67035985#67035985 问一下。