Нумерация рациональных чисел

[arseniiv]

Составим последовательность дробей вида $\frac{0}{1},\frac{0}{2},\frac{1}{2},\frac{0}{3},\frac{1}{3},\frac{2}{3},\frac{0}{4},\frac{1}{4},\frac{2}{4},\frac{3}{4}, \ldots $, а потом "вычеркнем" из неё все ранее встречавшиеся числа ( = оставим только несократимые дроби, избавившись от нулей, кроме первого). Получится $0,\frac{1}{2},\frac{1}{3},\frac{2}{3},\frac{1}{4},\frac{3}{4}, \ldots $. Теперь если обозначить элементы последовательности $q(i)$, получим тотальную биекцию $q:{\Bbb N} \to [0;\;1) \cap {\Bbb Q}$.

Знает ли кто-нибудь формулу для $q(i)$? Немного подумав, получил, что количество дробей со знаменателем $a$ равно $\phi (a)$. Дальше: выражение $s\phi (a) = \sum\limits_{j = 1}^a {\phi (j-1)}+1$ показывает, с какого номера элементы последовательности имеют [в виде несократимой дроби] знаменатель $a$. Значит, для вычисления, какой знаменатель у данного элемента, можно использовать продолжение $s\phi ^{ - 1} (i)$ на $\Bbb N$, каким образом - долго писать, оно строится легко. А что делать для числителя? Там как раз перебираются взаимно-простые (первый ноль не в счёт) со знаменателем числа, меньшие его.

И для упрощения можно начинать последовательность не с $0$, а с $1/2$ - тогда ведь просто из области значений исключается $0$, зато все числа в последовательности будут положительными.

Видимо, такую последовательность нельзя построить неалгоритмически?..

[ИСН]

Из меня плохой учитель, но послушайте: Вы не хотите эту формулу. Не хотите. Это дзен.
Если угодно конкретики: перечисление по диагонали красиво не свернётся. Есть какое-то другое (совсем в другом порядке, но тоже биекция), которое, кажется, сворачивалось. Но лучше от этого никому не стало.

[arseniiv]

Я понимаю, что если уже задан алгоритм построения, формула ни к чему. Да и на практике она не сгодится. Просто интересно. А может, и ввести какую-нибудь специальную функцию, которая вычисляется алгоритмически, тогда всё можно "спрятать" в неё. Но так же неинтересно

[venco]

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

Есть какое-то другое (совсем в другом порядке, но тоже биекция), которое, кажется, сворачивалось.

Наверное, Stern-Brocot Tree, и далее по ссылкам.

[ewert]

была тут на форуме какая-то формула на этот счёт, которую кто-то приводил -- не то Профессор Снэйп, не то ещё кто-то, не помню. За ненадобностью.

[Бодигрим]

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

Если угодно конкретики: перечисление по диагонали красиво не свернётся. Есть какое-то другое (совсем в другом порядке, но тоже биекция), которое, кажется, сворачивалось. Но лучше от этого никому не стало.

Возможно, Д. Н. Андреев Об одной замечательной нумерации положительных рациональных чисел

[maxal]

Еще есть Система счисления Штерна — Броко, которая базируется на одноименном дереве.

[Sonic86]

Можете еще посмотреть дроби Фарея, может поможет.

[arseniiv]

Спасибо за дерево и СС Штерна-Броко, я хотя и раньше читал, сейчас решил её поисследовать. Интересная вещь.