Функция fusc

Функция fusc — это целочисленная функция на множественатуральных чисел, определённая Э. Дейкстрой следующим образом:
fusc(k)={1,k=1;fusc(n),k=2nnN;fusc(n)+fusc(n+1),k=2n+1nN;kN
 Последовательность, генерируемая этой функцией, имеет вид:

 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, \ldots .
 Это диатомическая последовательность Штерна . Функция fusc связана споследовательностью Калкина — Уилфа, а именно n-ый членпоследовательности Калкина — Уилфа равенfusc(n)/fusc(n+1), а соответствие
nfusc(n)fusc(n+1),n=1,2,3,
является взаимно однозначным соответствием между множеством натуральныхчисел и множеством положительных рациональных чисел.

Свойства


 Пусть f1=fusc(n1) и f2=fusc(n2), тогда:

  • если существует N такое, что n1+n2=2N, то f1 и f2 взаимно просты;
  • если f1 и f2 взаимно просты, то существуют n1, n2 и N такие, что n1+n2=2N.

 Значение функции не изменится, если в двоичном представлении аргументаинвертировать все внутренние цифры. Например,fusc(19)=fusc(29), т.к. 1910 =100112 и 2910 = 111012.
 Значение функции также не изменится, если в двоичном представленииаргумента записать все цифры в обратном порядке. Например,fusc(19)=fusc(25), т.к. 1910 =100112 и 2510 = 110012.
 Значение fusc(n) чётно тогда и только тогда, когда nделится на 3.
fusc(2n)=1
fusc(32n)=2
 Значение fusc(n) равно количеству всех нечётных чиселСтирлинга второго рода вида S2(n+1,2r+1), а fusc(n+1)равно количеству всех нечётных биномиальных коэффициентов вида(nrr), где $\scriptstyle{0\leqslant 2r

Вычисление


 Кроме рекурсивного вычисления функции fusc по определению, существуетпростой итеративный алгоритм: \texttt 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