Рекуррентная формула для членов последовательности Фарея

[maximk]

Подскажите пожалуйста, как получить такую, исходя из некоторых известных соображений, например исходя из факта, что между двумя дробями из $F_n$ лежит их медианта (сумма числителей этих дробей, делёная на сумму их знаменателей), принадлежащая $F_n$. Пытался поработать с выражением медианты для получения её выражения через исходные дроби, получив таким образом рекуррентное соотношение, но здесь возникли некие проблемы: не удаётся удачно разделить числитель и знаменатель на что-нибудь, что приведёт к появлению явной записи исходных дробей. К примеру пусть $f_{k-1} = a/b < f_{k} = \frac{a+c}{b+d} < f_{k+1} = c/d$ при $f_i\in F_n$. Попытаемся разделить числитель и знаменатель $f_k$, скажем, на $b$, но тогда нужны выражения для $c/b$ и $d/b$ через $f_i$, но ничего кроме тривиальных тождеств на этом пути получить не сумел.

[Brukvalub]

В вики есть алгоритм, даже с кодом на Питоне.

[maximk]

Brukvalub, да, я видел, но так и не придумал, как отсюда получить рекуррентную зависимость между дробями и их медиантой. Если у вас есть какие-то мысли, было б неплохо, если б поделились, попробовал бы реализовать. Нужна какая-то явная зависимость, скажем, вида $f_k=g(f_{k-1}, f_{k+1})$.

-- 16.06.2016, 22:09 --

Если найти способ, как выразить $b/d$ (при обозначениях выше), то этого окажется достаточно.

[arseniiv]

maximk
Так вам нужна зависимость от предыдущего и следующего члена или от двух предыдущих? В обоих случаях всё тривиально.
1. Если вы ищите медианту, вам нужно выделить числитель и знаменатель окружающих её дробей.
2. Если вы ищите дробь по медианте её с другой известной, вам нужно выделить числитель и знаменатель окружающих её дробей, а формула с их использованием выводится в упомянутом Brukvalub разделе.
Вам осталось только по рациональному числу узнать числитель и знаменатель соответствующей несократимой дроби. Эти две функции можно и не выражать через что-нибудь ещё (а если вам надо их через что-то выразить, будьте конкретнее, через что именно). Если вы пишете какой-то код, онидолжны быть и так даны, потому что представлять точные рациональные числа в формате с плавающей запятой в этом случае нет смысла.

[INGELRII]

Как именно заданы рациональные числа, над которыми вы хотите это делать? Если в виде пары числитель-знаменатель, то вообще не вижу предмета обсуждения. А если иначе, то как?

[maximk]

По определению последовательности Фарея $F_n$ элементы из этой последовательности имеют вид $a/b$, где $b$ не превосходит $n$, $a$ не превосходит $b$, $a$ и $b$ взаимно просты.
Наверное всё очень просто, но почему-то не вижу решения.

[arseniiv]

Решения чего? Прокомментируйте как-нибудь подробнее, телепаты в отпуске.

[INGELRII]

То есть, по сути, нам даны не числа вида $\frac{a}{b}$, а пары чисел вида $(a,b)$, с НОД равным единице. И вот есть у нас две пары $(a,b),(c,d)$ по которым мы хочем построить пару $(a+c,b+d)$, которую потом надо сократить на НОД. Какбе укажите пальцем в действие, вызывающее у вас затруднение?

-- 17.06.2016, 00:17 --

Обратная же задача по числу и медианте его с другим числом найти это другое число - вообще однозначного решения не имеет. Вот нам известно число $\frac{1}{4}$ и медианта $\frac{1}{2}$. Второе число может оказаться равным $\frac{3}{4}$, а может очень даже $\frac{5}{8}$, а может и чему еще похуже. Сами продолжите ряд, это нетрудно.

[maximk]

Хотелось бы составить рекуррентную формулу типа формулы для чисел Фибоначчи, чтобы применить производящие функции и найти формулу общего n-го члена последовательности $F_n$, если это возможно по аналогии с методом, применяемым для чисел Фибоначчи. Начал делить числитель и знаменатель медианты для определенности, скажем, на $d$, в итоге если я получаю вид $b/d$ (чтоб явно выразить медианту через $f_{k-1}$ и $f_{k+1}$), то через $a/c$, и встает проблема того же рода.

[iifat]

INGELRII в сообщении #1132230 писал(а):

потом надо сократить на НОД

Даже этого не надо. Дробь заведомо будет несократимой.

[INGELRII]

iifat в сообщении #1132275 писал(а):

Дробь заведомо будет несократимой.

$2/7$ и $1/2$.

-- 17.06.2016, 09:35 --

maximk
Om nom nom nom. Давайте сначала: есть две пары чисел. Надо:

1) Сложить эти две пары, как вектора;
2) Получившуюся пару сократить на ее НОД.

Повторяю просьбу

INGELRII в сообщении #1132230 писал(а):

укажите пальцем в действие, вызывающее у вас затруднение?

[maximk]

Непонятно, как отсюда получить рекуррентное соотношение на дроби.

[whitefox]

Вам уже давали ссылку на алгоритм в Википедии, обладающий требуемыми вами свойствами:

Википедия писал(а):

Каждая итерация алгоритма строит следующую дробь на основе двух предыдущих.

И чем вас не устроили, приведённые там, формулы:

$$p = \left\lfloor\frac{n+b}{d}\right\rfloor c - a$$

$$q = \left\lfloor\frac{n+b}{d}\right\rfloor d - b $$

[Brukvalub]

whitefox в сообщении #1132282 писал(а):

чем вас не устроили, приведённые там, формулы

Как я понял, maximk хочет произвести какие-то теоретические изыскания с числами Фарея, поэтому ему не подходит алгоритм последовательной генерации рядов Фарея, а нужна именно рекуррентная формула или формула, выписывающая $n$ -е число по его номеру.

[INGELRII]

То есть стоит задача построить, например, $F_8$, имея лишь первые его два члена $0/1$ и $1/8$, что ли? Но это невозможно. Если нам даны медианта двух чисел и одно из этих чисел, то второе восстановить однозначно нельзя, множество решений аж счетно.

-- 17.06.2016, 11:54 --

iifat в сообщении #1132275 писал(а):

Дробь заведомо будет несократимой.

Кстати, я соврамши. Именно фарейские дроби всегда несократимы, а я почему-то думал сразу про общий случай вообще любых начальных значений.