WikiSort.ru - Не сортированное

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

${\displaystyle \operatorname {fusc} (k)={\begin{cases}1,&k=1;\\\operatorname {fusc} (n),&k=2n,n\in \mathbb {N} ;\\\operatorname {fusc} (n)+\operatorname {fusc} (n+1),&k=2n+1,n\in \mathbb {N} .\end{cases}}}$

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

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

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

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

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

Свойства

Пусть ${\displaystyle f_{1}=\operatorname {fusc} (n_{1})}$ и ${\displaystyle f_{2}=\operatorname {fusc} (n_{2})}$ , тогда^[1]:

• если существует ${\displaystyle N}$ такое, что ${\displaystyle n_{1}+n_{2}=2^{N}}$ , то ${\displaystyle f_{1}}$ и ${\displaystyle f_{2}}$ взаимно просты;
• если ${\displaystyle f_{1}}$ и ${\displaystyle f_{2}}$ взаимно просты, то существуют ${\displaystyle n_{1}}$ , ${\displaystyle n_{2}}$ и ${\displaystyle N}$ такие, что ${\displaystyle n_{1}+n_{2}=2^{N}}$ .

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

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

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

Функция обладает свойствами

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

${\displaystyle \operatorname {fusc} (3\cdot 2^{n})=2.}$

Значение ${\displaystyle \operatorname {fusc} (n)}$ равно количеству всех нечётных чисел Стирлинга второго рода вида ${\displaystyle S_{2}(n+1,2r+1)}$ , а ${\displaystyle \operatorname {fusc} (n+1)}$ равно количеству всех нечётных биномиальных коэффициентов вида ${\displaystyle {\binom {n-r}{r}}}$ , где ${\displaystyle 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

См. также

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