Функция fusc

Функция fusc — это целочисленная функция на множестве натуральных чисел, определённая Э. Дейкстрой следующим образом:

$\mathrm{fusc}(k)=\{\begin{array}{cc}1,& k=1;\\ \mathrm{fusc}(n),& k=2n,n\in \mathbb{N};\\ \mathrm{fusc}(n)+\mathrm{fusc}(n+1),& k=2n+1,n\in \mathbb{N}.\end{array}$

Последовательность, генерируемая этой функцией, имеет вид

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

Это диатомическая последовательность Штерна (Шаблон:OEIS). Функция fusc связана с последовательностью Калкина — Уилфа, а именно $n$-й член последовательности Калкина — Уилфа равен $\mathrm{fusc}(n)/\mathrm{fusc}(n+1)$, а соответствие

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

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

Свойства

Пусть $f_1=\mathrm{fusc}(n_1)$ и $f_2=\mathrm{fusc}(n_2)$, тогда:

• если существует $N$ такое, что $n_1+n_2=2^N$, то $f_1$ и $f_2$ взаимно просты;
• если $f_1$ и $f_2$ взаимно просты, то существуют $n_1$, $n_2$ и $N$ такие, что $n_1+n_2=2^N$.

Значение функции не изменится, если в двоичном представлении аргумента инвертировать все внутренние цифры. Например, $\mathrm{fusc}(19)=\mathrm{fusc}(29)$, т. к. 19₁₀ = 10011₂ и 29₁₀ = 11101₂.

Значение функции также не изменится, если в двоичном представлении аргумента записать все цифры в обратном порядке. Например, $\mathrm{fusc}(19)=\mathrm{fusc}(25)$, т. к. 19₁₀ = 10011₂ и 25₁₀ = 11001₂.

Значение $\mathrm{fusc}(n)$ чётно тогда и только тогда, когда $n$ делится на 3.

Функция обладает свойствами

$\mathrm{fusc}(2^n)=1,$

$\mathrm{fusc}(3\cdot 2^n)=2.$

Значение $\mathrm{fusc}(n)$ равно количеству всех нечётных чисел Стирлинга второго рода вида $S_2(n+1,2r+1)$, а $\mathrm{fusc}(n+1)$ равно количеству всех нечётных биномиальных коэффициентов вида $(\genfrac{}{}{0ex}{}{n-r}{r})$, где $0⩽2r<n$.

Вычисление

Кроме рекурсивного вычисления функции fusc по определению, существует простой итеративный алгоритм:

fusc(N):
    n, a, b = N, 1, 0
    пока n ≠ 0:
        если n чётное:
            a, n = a + b, n / 2
        если n нечётное:
            b, n = a + b, (n - 1) / 2
    fusc(N) = b

Ссылки

• Шаблон:OEIS

См. также

• Дерево Калкина — Уилфа