Функция 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, …
Это диатомическая последовательность Штерна (). Функция fusc связана с последовательностью Калкина — Уилфа, а именно -й член последовательности Калкина — Уилфа равен , а соответствие
является взаимно однозначным соответствием между множеством натуральных чисел и множеством положительных рациональных чисел.
Свойства Пусть и , тогда: если существует такое, что , то и взаимно просты; если и взаимно просты, то существуют , и такие, что .
Значение функции не изменится, если в двоичном представлении аргумента инвертировать все внутренние цифрыEWD 578: More about the function "fusc" (A sequel to EWD570) .. Например, , т. к. 1910 = 100112 и 2910 = 111012.
Значение функции также не изменится, если в двоичном представлении аргумента записать все цифры в обратном порядке. Например, , т. к. 1910 = 100112 и 2510 = 110012.
Значение чётно тогда и только тогда, когда делится на 3.
Функция обладает свойствами
Значение равно количеству всех нечётных чисел Стирлинга второго рода вида , а равно количеству всех нечётных биномиальных коэффициентов вида , где .
Вычисление Кроме рекурсивного вычисления функции 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
Примечания
Ссылки
См. также Дерево Калкина — Уилфа
Категория:Функции Категория:Целочисленные последовательности