Функція 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). Функція $\operatorname {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$.

Обчислення

Крім рекурсивного обчислення функції $\operatorname {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