Функция fusc

Функция fusc — это целочисленная функция на множестве натуральных чисел, определённая Э. Дейкстрой следующим образом^[1]:

$\mathrm{fusc}\,(n) = \begin{cases} \mathrm{fusc}\,(1)=1; \\ \mathrm{fusc}\,(2n) = \mathrm{fusc}\,(n); \\ \mathrm{fusc}\,(2n+1) = \mathrm{fusc}\,(n) + \mathrm{fusc}\,(n+1). \end{cases}$

Последовательность, генерируемая этой функцией, имеет вид:

1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, … .

Это диатомическая последовательность Штерна (последовательность A002487 в OEIS). Функция fusc связана с последовательностью Калкина — Уилфа, а именно $n$-ый член последовательности Калкина — Уилфа равен $\mathrm{fusc}\,(n)/\mathrm{fusc}\,(n+1)$, а соответствие

$n\mapsto\frac{\mathrm{fusc}\,(n)}{\mathrm{fusc}\,(n+1)},\quad n=1,2,3,\dots$

является взаимно однозначным соответствием между множеством натуральных чисел и множеством положительных рациональных чисел.

Свойства

Пусть $f_1=\mathrm{fusc}\,(n_1)$ и $f_2=\mathrm{fusc}\,(n_2)$, тогда^[1]:

• если существует $N$ такое, что $n_1 + n_2 = 2^N$, то $f_1$ и $f_2$ взаимно просты;
• если $f_1$ и $f_2$ взаимно просты, то существуют $n_1$, $n_2$ и $N$ такие, что $n_1 + n_2 = 2^N$.

Значение функции не изменится, если в двоичном представлении аргумента инвертировать все внутренние цифры^[2]. Например, $\mathrm{fusc}\,(19)=\mathrm{fusc}\,(29)$, т.к. 19₁₀ = 10011₂ и 29₁₀ = 11101₂.

Значение функции также не изменится, если в двоичном представлении аргумента записать все цифры в обратном порядке^[2]. Например, $\mathrm{fusc}\,(19)=\mathrm{fusc}\,(25)$, т.к. 19₁₀ = 10011₂ и 25₁₀ = 11001₂.

Значение $\mathrm{fusc}\,(n)$ чётно тогда и только тогда, когда $n$ делится на 3^[2].

$\mathrm{fusc}\,(2^n) = 1$

$\mathrm{fusc}\,(3\cdot2^n) = 2$

Значение $\mathrm{fusc}\,(n)$ равно количеству всех нечётных чисел Стирлинга второго рода вида $S_2(n+1, 2r+1)$, а $\mathrm{fusc}\,(n+1)$ равно количеству всех нечётных биномиальных коэффициентов вида $\scriptstyle{n-r\choose r}$, где $\scriptstyle{0\leqslant 2r<n}$^[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. ↑ ^{1 2 3} EWD 570: An exercise for Dr. R. M. Burstall.
2. ↑ ^{1 2 3} 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.

Ссылки

• последовательность A002487 в OEIS

См. также

• Дерево Калкина — Уилфа