WikiSort.ru - Не сортированное

Основные свойства

• Все дроби, расположенные в вершинах дерева, несократимы;
• Любая несократимая рациональная дробь встречается в дереве в точности один раз.

Последовательность Калкина — Уилфа

Из приведенных выше свойств следует, что последовательность положительных рациональных чисел, получаемая в результате обхода «сначала-в-ширину»^[3] (англ. breadth-first traversal) дерева Калкина — Уилфа (называемая также последовательностью Калкина — Уилфа; см. иллюстрацию):

${\displaystyle {\frac {1}{1}},{\frac {1}{2}},{\frac {2}{1}},{\frac {1}{3}},{\frac {3}{2}},{\frac {2}{3}},{\frac {3}{1}},{\frac {1}{4}},{\frac {4}{3}},{\frac {3}{5}},{\frac {5}{2}},{\frac {2}{5}},{\frac {5}{3}},{\frac {3}{4}},\dots ,}$

определяет взаимно однозначное соответствие между множеством натуральных чисел и множеством положительных рациональных чисел.

Данная последовательность может быть задана рекуррентным соотношением^[4]:

${\displaystyle q_{1}=1;}$

${\displaystyle q_{i+1}={\frac {1}{\lfloor q_{i}\rfloor +1-\{q_{i}\}}}={\frac {1}{2\lfloor q_{i}\rfloor -q_{i}+1}},\quad i=1,2,\dots \!,}$

где ${\displaystyle \lfloor x\rfloor }$ и ${\displaystyle \{x\}}$ обозначают соответственно целую и дробную части числа ${\displaystyle x}$ .

В последовательности Калкина — Уилфа знаменатель каждой дроби равен числителю следующей.

Функция fusc

В 1976 году Э. Дейкстра определил на множестве натуральных чисел целочисленную функцию fusc(n) следующими рекуррентными соотношениями^[5]:

• ${\displaystyle \mathop {\mathrm {fusc} } (1)=1}$ ;
• ${\displaystyle \mathop {\mathrm {fusc} } (2n)=\mathop {\mathrm {fusc} } (n)}$ ;
• ${\displaystyle \mathop {\mathrm {fusc} } (2n+1)=\mathop {\mathrm {fusc} } (n)+\mathop {\mathrm {fusc} } (n+1)}$ .

Последовательность значений ${\displaystyle \scriptstyle {\mathop {\mathrm {fusc} } (n),\ n=1,2,3,\dots }}$ , совпадает с последовательностью числителей дробей в последовательности Калкина — Уилфа, то есть последовательностью

1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, … .

Таким образом (поскольку знаменатель каждой дроби в последовательности Калкина — Уилфа равен числителю следующей), ${\displaystyle n}$ -й член последовательности Калкина — Уилфа равен ${\displaystyle \scriptstyle {\mathop {\mathrm {fusc} } (n)/\mathop {\mathrm {fusc} } (n+1)}}$ , а соответствие

${\displaystyle n\mapsto {\frac {\mathop {\mathrm {fusc} } (n)}{\mathop {\mathrm {fusc} } (n+1)}},\quad n=1,2,3,\dots }$

является взаимно однозначным соответствием между множеством натуральных чисел и множеством положительных рациональных чисел.

Функция ${\displaystyle \scriptstyle {\mathop {\mathrm {fusc} } }}$ может быть, помимо указанных выше рекуррентных соотношений, определена следующим образом.

• Значение ${\displaystyle \scriptstyle {\mathop {\mathrm {fusc} } }(n+1),\ n\geqslant 0,}$ равно количеству гипердвоичных (англ. hyperbinary) представлений числа ${\displaystyle n}$ , то есть представлений в виде суммы неотрицательных степеней двойки, где каждая степень ${\displaystyle 2^{k}}$ встречается не более двух раз^[6]. Например, число 6 представляется тремя такими способами:

6 = 4 + 2 = 4 + 1 + 1 = 2 + 2 + 1 + 1, поэтому ${\displaystyle \scriptstyle {\mathop {\mathrm {fusc} } }(6+1)=3}$ .

• Значение ${\displaystyle \scriptstyle {\mathop {\mathrm {fusc} } (n+1)},\ n\geqslant 0,}$ равно числу всех нечётных биномиальных коэффициентов вида ${\displaystyle \scriptstyle {n-r \choose r}}$ , где ${\displaystyle \scriptstyle {0\leqslant 2r<n}}$ ^[7].

В оригинальной статье Калкина и Уилфа функция ${\displaystyle \scriptstyle {\mathop {\mathrm {fusc} } }}$ не упоминается, но рассматривается целочисленная функция ${\displaystyle b(n)}$ , определённая для ${\displaystyle \scriptstyle n=0,1,2,\dots }$ , равная количеству гипердвоичных представлений числа ${\displaystyle n}$ , и доказывается, что соответствие

${\displaystyle n\mapsto {\frac {b(n)}{b(n+1)}},\quad n=0,1,2,\dots ,}$

является взаимно однозначным соответствием между множеством неотрицательных целых чисел и множеством рациональных чисел. Таким образом, для ${\displaystyle \scriptstyle n=0,1,2,\dots }$ имеют место соотношения:

• ${\displaystyle \scriptstyle b(n)=\mathop {\mathrm {fusc} } (n+1);}$
• ${\displaystyle \scriptstyle b(2n+1)=b(n);\quad b(2n+2)=b(n)+b(n+1).}$