Рациональное число с наименьшим знаменателем в интервале

[ellipse]

Как найти рациональное число с наименьшим знаменателем в интервале $(a;b)$.
$a < \frac{m}{n} < b \Longrightarrow an < m < bn$ т.е. нужно найти такое минимальное $n$, что между $an, bn$ содержится целое число. Как решить эту задачу? Неужели только перебором? Может можно сократить область поиска?

[Droog_Andrey]

А если попробовать рациональные приближения $a$ и $b$ (цепными дробями)? Отталкиваться от тех из них, которые имеют погрешности, сравнимые с $|a-b|$.

[Профессор Снэйп]

Ну а в каком виде заданы $a$ и $b$?

[ellipse]

Профессор Снэйп писал(а):

Ну а в каком виде заданы $a$ и $b$?

Пусть $a, b$ - рациональные

[maxal]

ellipse писал(а):

Как найти рациональное число с наименьшим знаменателем в интервале $(a;b)$.
$a < \frac{m}{n} < b \Longrightarrow an < m < bn$ т.е. нужно найти такое минимальное $n$, что между $an, bn$ содержится целое число.

Ограничение сверху на $n$ - это сумма знаменателей чисел $a$ и $b$. Дело в том, что если $a=\frac{p_a}{q_a} < b=\frac{p_b}{q_b}$, где $p_a$, $p_b$, $q_a$ и $q_b$ - натуральные числа, то

$$a < \frac{p_a + p_b}{q_a + q_b} < b.$$

При этом эта верхняя грань достижима на соседних членах рядов Фарея, причем в этом случае $\frac{p_a + p_b}{q_a + q_b}$ представляет собой несократимую дробь.

[mihiv]

Предположим $a < \frac mn <b$ и $\frac mn$ (несократимая) дробь с наименьшим знаменателем в этом интервале. Рассмотрим дроби $\frac m{n-1}$ и $\frac {m-1}{n-1}$ знаменатель этих дробей меньше $n$, значит,согласно сделанному предположению они лежат вне интервала $(a,b)$,поэтому $\frac m{n-1}>b$,а $\frac {m-1}{n-1}<a$. Следовательно, $\frac m{n-1}-\frac {m-1}{n-1}=\frac 1{n-1}>b-a$,отсюда получаем оценку $n<\frac1{b-a}+1$. Числа $a$ и $b$ не обязательно предполагать рациональными.

[Профессор Снэйп]

Тут все предлагают верхние оценки для $n$, которые в некоторых случаях могут быть точны. Ну а если оценка получена и она оказалась достаточно велика? Насколько я понял, автора интересует именно этот случай и он спрашивает, можно ли избежать перебора.

[ИСН]

А тупо берём среднее арифметическое и идём по его подходящим дробям. И только.

[maxal]

ИСН писал(а):

А тупо берём среднее арифметическое и идём по его подходящим дробям. И только.

Докажите.

[ИСН]

Ну как. (Я не все нужные слова знаю.) Искать такое число на интервале - это значит искать некоторое наилучшее приближение к середине интервала (наилучшее - в смысле, которое лучше всех с меньшим знаменателем), а все такие приближения суть её подходящие дроби, вроде так.

[maxal]

ИСН в сообщении #200445 писал(а):

Искать такое число на интервале - это значит искать некоторое наилучшее приближение к середине интервала (наилучшее - в смысле, которое лучше всех с меньшим знаменателем)

Эта предпосылка неверна.

[maxal]

maxal писал(а):

Ограничение сверху на $n$ - это сумма знаменателей чисел $a$ и $b$. Дело в том, что если $a=\frac{p_a}{q_a} < b=\frac{p_b}{q_b}$, где $p_a$, $p_b$, $q_a$ и $q_b$ - натуральные числа, то

$$a < \frac{p_a + p_b}{q_a + q_b} < b.$$

При этом эта верхняя грань достижима на соседних членах рядов Фарея, причем в этом случае $\frac{p_a + p_b}{q_a + q_b}$ представляет собой несократимую дробь.

Отсюда следует и алгоритм для нахождения искомого числа с наименьшим знаменателем:
1) если $a$ и $b$ являются соседними элементами ряда Фарея $F_{\max\{q_a,q_b\}}$, то решение уже указано выше;
2) в противном случае нужно "достроить" все дроби ряда Фарея $F_{\max\{q_a,q_b\}}$, находящиеся между $a$ и $b$, и выбрать из них дробь с наименьшим знаменателем. Для этого можно начать с чуть большего отрезка (покрывающего $[a,b]$) ряда $F_{\min\{q_a,q_b\}}$ и достроить его стандартным образом (см. ссылку выше) до отрезка ряда $F_{\max\{q_a,q_b\}}.$

Сложность здесь пропорциональна разности знаменателей $|q_a - q_b|$ и количеству дробей в $F_{\max\{q_a,q_b\}}$, находящихся между $a$ и $b$.

[ИСН]

Крутил так и сяк – нет, не понимаю. Вот число; оно попало на интервал, а все с меньшими знаменателями – не попали. А оно попало. Значит, оно ближе к середине интервала, чем те. То есть, значит, наилучшее приближение для этой середины.
Или как?

[Dandan]

та при чем тут середина. "Лучшее" число на интервале (1/2 - 1/1000000, 1) совсем не рядом с серединой этого интервала.

[RIP]

Бывают разные наилучшие приближения. В данном случае это почти наилучшее приближение первого рода ("почти" потому, что в определении наил. прибл. рассматриваются и дроби со знаменателем, равным рассматриваемому); среди них помимо подходящих ещё промежуточные дроби встречаются.