Функція fusc - це цілочислова функція на множині натуральних чисел, яку Е. Дейкстра визначив такEWD 570: An exercise for Dr. R. M. Burstall.:
Послідовність, яку генерує ця функція, має вигляд
1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, …
Це діатомічна послідовність Штерна (). Функція пов'язана з послідовністю Калкіна — Вілфа, а саме -й член послідовності Калкіна — Вілфа дорівнює , а відповідність
є взаємно однозначною відповідністю між множиною натуральних чисел і множиною додатних раціональних чисел.
Властивості Нехай і , тоді:
якщо існує таке, що , то і взаємно прості; якщо і взаємно прості, то існують , і такі, що .
Значення функції не зміниться, якщо в двійковому поданні аргументу інвертувати всі внутрішні цифриEWD 578: More about the function «fusc» (A sequel to EWD570).. Наприклад, , оскільки 1910 = 100112 і 2910 = 111012.
Значення функції також не зміниться, якщо в двійковому поданні аргументу записати всі цифри в зворотному порядку. Наприклад, , оскільки 1910 = 100112 і 2510 = 110012.
Значення парне тоді і тільки тоді, коли ділиться на 3.
Функція має властивості
Значення дорівнює кількості всіх непарних чисел Стірлінга другого роду вигляду , а дорівнює кількості всіх непарних біноміальних коефіцієнтів вигляду , де .
Обчислення Крім рекурсивного обчислення функції за визначенням, існує простий ітеративний алгоритм:
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
Примітки
Див. також Дерево Калкіна — Вілфа
Посилання