Функция fusc

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

fusc ⁡ ( k ) = { 1 , k = 1 ; fusc ⁡ ( n ) , k = 2 n , n ∈ N ; fusc ⁡ ( n ) + fusc ⁡ ( n + 1 ) , k = 2 n + 1 , n ∈ N . {displaystyle operatorname {fusc} (k)={egin{cases}1,&k=1;operatorname {fusc} (n),&k=2n,nin mathbb {N} ;operatorname {fusc} (n)+operatorname {fusc} (n+1),&k=2n+1,nin mathbb {N} .end{cases}}}

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

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

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

n ↦ fusc ⁡ ( n ) fusc ⁡ ( n + 1 ) , n = 1 , 2 , 3 , … {displaystyle nmapsto {frac {operatorname {fusc} (n)}{operatorname {fusc} (n+1)}},quad n=1,2,3,dots }

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

Свойства

Пусть f 1 = fusc ⁡ ( n 1 ) {displaystyle f_{1}=operatorname {fusc} (n_{1})} и f 2 = fusc ⁡ ( n 2 ) {displaystyle f_{2}=operatorname {fusc} (n_{2})} , тогда:

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

Значение функции не изменится, если в двоичном представлении аргумента инвертировать все внутренние цифры. Например, fusc ⁡ ( 19 ) = fusc ⁡ ( 29 ) {displaystyle operatorname {fusc} (19)=operatorname {fusc} (29)} , т. к. 1910 = 100112 и 2910 = 111012.

Значение функции также не изменится, если в двоичном представлении аргумента записать все цифры в обратном порядке. Например, fusc ⁡ ( 19 ) = fusc ⁡ ( 25 ) {displaystyle operatorname {fusc} (19)=operatorname {fusc} (25)} , т. к. 1910 = 100112 и 2510 = 110012.

Значение fusc ⁡ ( n ) {displaystyle operatorname {fusc} (n)} чётно тогда и только тогда, когда n {displaystyle n} делится на 3.

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

fusc ⁡ ( 2 n ) = 1 , {displaystyle operatorname {fusc} (2^{n})=1,} fusc ⁡ ( 3 ⋅ 2 n ) = 2. {displaystyle operatorname {fusc} (3cdot 2^{n})=2.}

Значение fusc ⁡ ( n ) {displaystyle operatorname {fusc} (n)} равно количеству всех нечётных чисел Стирлинга второго рода вида S 2 ( n + 1 , 2 r + 1 ) {displaystyle S_{2}(n+1,2r+1)} , а fusc ⁡ ( n + 1 ) {displaystyle operatorname {fusc} (n+1)} равно количеству всех нечётных биномиальных коэффициентов вида ( n − r r ) {displaystyle {inom {n-r}{r}}} , где 0 ⩽ 2 r < n {displaystyle 0leqslant 2r<n} .

Вычисление

Кроме рекурсивного вычисления функции 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