Русская Википедия:Функция fusc

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

<math>\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} </math>

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

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

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

<math>n \mapsto \frac{\operatorname{fusc}(n)}{\operatorname{fusc}(n+1)}, \quad n = 1, 2, 3, \dots</math>

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

Свойства

Пусть <math>f_1 = \operatorname{fusc}(n_1)</math> и <math>f_2 = \operatorname{fusc}(n_2)</math>, тогда:

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

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

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

Значение <math>\operatorname{fusc}(n)</math> чётно тогда и только тогда, когда <math>n</math> делится на 3.

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

<math>\operatorname{fusc}(2^n) = 1,</math>

<math>\operatorname{fusc}(3 \cdot 2^n) = 2.</math>

Значение <math>\operatorname{fusc}(n)</math> равно количеству всех нечётных чисел Стирлинга второго рода вида <math>S_2(n + 1, 2r + 1)</math>, а <math>\operatorname{fusc}(n+1)</math> равно количеству всех нечётных биномиальных коэффициентов вида <math>\binom{n - r}{r}</math>, где <math>0 \leqslant 2r < n</math>.

Вычисление

Кроме рекурсивного вычисления функции fusc по определению, существует простой итеративный алгоритм:

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

Ссылки

• Шаблон:OEIS

См. также

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