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

[whitefox]

maximk в сообщении #1132141 писал(а):

Нужна какая-то явная зависимость, скажем, вида $f_k=g(f_{k-1}, f_{k+1})$.

maximk в сообщении #1132141 писал(а):

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

Вот и выразите дроби как вам уже предлагалось:

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

в виде пары числитель-знаменатель

Тогда первыми двумя членами ряда Фарея $N$-го порядка будут $f_0=(0,1);f_1=(1,N).$

Пусть двухместная функция $c(x,y)$ любым двум целым числам $x,y$ ставит в соответствие упорядоченную пару $(x,y).$ И пусть функция $l(X)$ ставит в соответствие упорядоченной паре $X$ её левый элемент, то есть $l((x,y))=x,$ а функция $r(X)$ ставит в соответствие упорядоченной паре $X$ её правый элемент, то есть $r((x,y))=y.$

Используя эти функции и, приведённые выше, формулы, вы сможете определить функцию $g(X,Y)$ ставящую в соответствие двум упорядоченным парам $X,Y$ третью упорядоченную пару $Z,$ так чтобы выполнялось рекуррентное соотношение:

$$f_{n+1}=g(f_n,f_{n-1})$$

[iifat]

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

Если нам даны медианта двух чисел и одно из этих чисел, то второе восстановить однозначно нельзя

Даже если речь идёт о соседних дробях Фарея?

[INGELRII]

iifat
Ну если так... в-в-возможно. Лень думать, я только что пообедал

[iifat]

Аналогично. Википедия утверждает, что да и даже алгоритм приводит. Давайте ей верить пока не проголодаемся.

[DeBill]

А давайте запретим надругательство над Фареем, и будем честно выписывать все члены, а не только те, у которых знаменатель не боле $n$. Тогда :
Стартуем со строчки $F_0$, состоящей из дробей $F_{0,0} = \frac{0}{1}, F_{0,1}=\frac{1}{1}$.
В $n$-й строчке $F_n$ будут стоять дроби $F_{n,k}$ с номерами $k= 0,1,..., 2^n$
При этом: $F_{n,2k} = F_{n-1,k}$, $F_{n,2k-1}$ получается "медетированием" из своих соседей. Теперь это можно расписать порознь для их числителей и знаменателей. Вот и будут реккурентные формулы - правда, выражающие $F_n$ через $F_{n-1}$. И почему то казится, что можно соорудить и формулы для прямого доступа (сразу по $n$ найти числитель и знаменатель ) - используя двоичную запись числа $k$....
Вики-Фарея тогда можно получить кастрированием ФАРЕЯ: надо просто удалить те члены, знаменатели которых слишком большие....

[arseniiv]

maximk в сообщении #1132272 писал(а):

чтобы применить производящие функции и найти формулу общего n-го члена последовательности $F_n$

А зачем?

[maximk]

arseniiv, интерес.

[arseniiv]

Ну, тогда добавить нечего. Если бы была практическая надобность в генерации всех дробей данной $F_n$, то или дерево, или рекуррентная формула одинаково хороши (вторая особенно хороша, если в каждый момент времени нужна только одна-две дроби, а не сразу все). А так — удачи с $\lfloor\hphantom{a}\rfloor$.

[maximk]

arseniiv, спасибо. А вообще эти последовательности представляют интерес еще и потому, что гипотеза Римана допускает переформулировку в терминах этих последовательностей (см. например статью Стечкина об этих последовательностях

(Оффтоп)

в поиске достаточно вбить "Стечкин Фарея"

). Быть может для исследования одного из тех неравенств будет полезно получить общую формулу $\omega_\nu$ (в терминах той статьи).

(Оффтоп)

Моя выпускная работа посвящена некоторым свойствам $F_n$, решил продолжить исследовать. Подумал, что проще всего будет получить общую формулу именно на этом пути. Неплохо бы рассмотреть другие варианты. В задачнике Гашкова, Чубарикова по теории чисел в начале есть раздел по этим последовательностям, если кому интересно.