Функция fusc
Функция fusc — это целочисленная функция на множестве натуральных чисел, определённая Э. Дейкстрой следующим образом[1]:
Последовательность, генерируемая этой функцией, имеет вид
- 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, …
Это диатомическая последовательность Штерна (последовательность A002487 в OEIS). Функция fusc связана с последовательностью Калкина — Уилфа, а именно -й член последовательности Калкина — Уилфа равен , а соответствие
является взаимно однозначным соответствием между множеством натуральных чисел и множеством положительных рациональных чисел.
Свойства
Пусть и , тогда[1]:
- если существует такое, что , то и взаимно просты;
- если и взаимно просты, то существуют , и такие, что .
Значение функции не изменится, если в двоичном представлении аргумента инвертировать все внутренние цифры[2]. Например, , т. к. 1910 = 100112 и 2910 = 111012.
Значение функции также не изменится, если в двоичном представлении аргумента записать все цифры в обратном порядке[2]. Например, , т. к. 1910 = 100112 и 2510 = 110012.
Значение чётно тогда и только тогда, когда делится на 3[2].
Функция обладает свойствами
Значение равно количеству всех нечётных чисел Стирлинга второго рода вида , а равно количеству всех нечётных биномиальных коэффициентов вида , где [3].
Вычисление
Кроме рекурсивного вычисления функции 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
Примечания
- EWD 570: An exercise for Dr. R. M. Burstall.
- EWD 578: More about the function "fusc" (A sequel to EWD570).
- Carlitz, L. A problem in partitions related to the Stirling numbers // Bulletin of the American Mathematical Society. — 1964. — Vol. 70, № 2. — P. 275—278.