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