Функция fusc

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

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

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

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

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

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

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

Свойства

Пусть $f_{1}=\operatorname {fusc} (n_{1})$ и $f_{2}=\operatorname {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}$.

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

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

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

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

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

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

Значение $\operatorname {fusc} (n)$ равно количеству всех нечётных чисел Стирлинга второго рода вида $S_{2}(n+1,2r+1)$, а $\operatorname {fusc} (n+1)$ равно количеству всех нечётных биномиальных коэффициентов вида ${\binom {n-r}{r}}$, где $0\leqslant 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

Ссылки

• последовательность A002487 в OEIS

См. также

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