Функция 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

Примечания

  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. — Vol. 70, № 2. — P. 275—278.

Ссылки

См. также

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.