分数问题

hejoseph

已知 \(\alpha\)、\(\beta\)，满足 \(0<\alpha<\beta<1\)，\(x\)、\(y\) 为正整数，且满足
\[\alpha<\frac{x}{y}<\beta\]
求 \(y\) 的最小值。
这个问题可以用连分数直接得到结论，例如
\[\alpha=\frac{19}{193},\beta=\frac{97}{985},\]
因为
\[\frac{19}{193}=\frac{1}{10+\frac{1}{6+\frac{1}{3}}}=\frac{1}{10+\frac{1}{6+\frac{1}{2+\frac{1}{1}}}},\frac{97}{985}=\frac{1}{10+\frac{1}{6+\frac{1}{2+\frac{1}{7}}}},\]
则
\[\frac{x}{y}=\frac{1}{10+\frac{1}{6+\frac{1}{2+\frac{1}{2}}}}=\frac{32}{325}\]

现在把问题改为：已知 \(\alpha\)、\(\beta\) 和正整数 \(n\)，满足 \(0<\alpha<\beta<1\)，\(x\)、\(y\) 为正整数，且满足
\[\alpha<\frac{x}{y}<\beta,y\leq n,\]
求 \(y\) 的最大值。

hujunhua

这个结果应该会无趣很多。
就像那个三圆问题一样，最大值是个边界值，就无趣很多。

hejoseph

我也估计结论不太有趣，目前我的方法也是用上面一个题目的方法去做，不断求分母最小的分数，然后分母的倍数也选上，直到第一次得到最小的分母超过 \(n\)，不过过程也是无趣的。

hujunhua

当`n\ge\frac1{\beta-\alpha}`时，`y`的最大值就是`n`. 所有题目要有意义，必须`n\le\frac1{\beta-\alpha}`
可以考虑区间`[\alpha, \beta]`内的有理数序列，按分母递增的顺序。在分母小于`\frac1{\beta-\alpha}`时显然没有两个分母相同的分数，所以分离出这个范围内的分母序列是有意义的。
分母 `y` 可按如下条件滤取：`\lceil y\alpha\rceil\le\lfloor y\beta\rfloor`
以`\alpha=19/193, \beta=97/985`为例试了一下:

1. a = 19/193; b = 97/985;
   
2. Select[Range[1/(b - a)], Ceiling[a #] == Floor[b #] &]

复制代码

此例`\frac1{\beta-\alpha}=36184`, 结果显示分母序列长度为`15940`. 也就是平均来说差不多隔一个数有一个分母。当然实际不是平均分布，而是在左疏右密（右端往左走有很长一个连续整数段），点图接近抛物线。
既然右端往左走有很长一段连续整数段，那么使题目有意义的 n 值还应该收缩，在本例中，右端连续段长为357，往左直至31328。

hujunhua

所以求最大值的问题应该这么提：求最大的分母`y`, 使得没有分数`x/y\in(\alpha,\beta)`. 本例答案是31327.

hujunhua

如果使用两个连续的菲波拉契分数：`\alpha=F_{i-1}/F_i, \beta=F_i/F_{i+1}`, 那么这个最大分母是`F_iF_{i+1}-F_{i+2}=(F_i-1)(F_{i+1}-1)-1`