Функція fusc

Функція fusc - це цілочислова функція на множині натуральних чисел, яку Е. Дейкстра визначив так:

${\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). Функція ${\displaystyle \operatorname {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})}$, тоді:

• якщо існує ${\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}}$.

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

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

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

Функція має властивості

${\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}$.

Обчислення

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

Примітки

1. EWD 570: An exercise for Dr. R. M. Burstall.
2. EWD 578: More about the function «fusc» (A sequel to EWD570).
3. Carlitz, L. A problem in partitions related to the Stirling numbers // Bulletin of the American Mathematical Society. — 1964. — Т. 70, № 2 (6 липня). — С. 275—278.

Див. також

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

Посилання

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