Функция fusc

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

${\displaystyle \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 связана с последовательностью Калкина — Уилфа, а именно ${\displaystyle n}$-й член последовательности Калкина — Уилфа равен ${\displaystyle \operatorname {fusc} (n)/\operatorname {fusc} (n+1)}$, а соответствие

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

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

Пусть ${\displaystyle f_{1}=\operatorname {fusc} (n_{1})}$ и ${\displaystyle f_{2}=\operatorname {fusc} (n_{2})}$, тогда^[1]:

• если существует ${\displaystyle N}$ такое, что ${\displaystyle n_{1}+n_{2}=2^{N}}$, то ${\displaystyle f_{1}}$ и ${\displaystyle f_{2}}$ взаимно просты;
• если ${\displaystyle f_{1}}$ и ${\displaystyle f_{2}}$ взаимно просты, то существуют ${\displaystyle n_{1}}$, ${\displaystyle n_{2}}$ и ${\displaystyle N}$ такие, что ${\displaystyle n_{1}+n_{2}=2^{N}}$.

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

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

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

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

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

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

Значение ${\displaystyle \operatorname {fusc} (n)}$ равно количеству всех нечётных чисел Стирлинга второго рода вида ${\displaystyle S_{2}(n+1,2r+1)}$, а ${\displaystyle \operatorname {fusc} (n+1)}$ равно количеству всех нечётных биномиальных коэффициентов вида ${\displaystyle {\binom {n-r}{r}}}$, где ${\displaystyle 0\leqslant 2r<n}$^[3].

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

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

1. ↑ ^{1 2 3} EWD 570: An exercise for Dr. R. M. Burstall Архивная копия от 15 августа 2021 на Wayback Machine.
2. ↑ ^{1 2 3} EWD 578: More about the function "fusc" (A sequel to EWD570) Архивная копия от 15 августа 2021 на Wayback Machine.
3. ↑ Carlitz, L. A problem in partitions related to the Stirling numbers // Bulletin of the American Mathematical Society. — 1964. — Vol. 70, № 2. — P. 275—278. Архивировано 21 января 2022 года.

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

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