Функція fusc

Нехай ${\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].

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

• Дерево Калкіна — Вілфа

• послідовність A002487 з Онлайн енциклопедії послідовностей цілих чисел, OEIS