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

Обчислення

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