Fusc funktion

Funktionen fusc er en heltalsfunktion på sættet af naturlige tal, defineret af E. Dijkstra som følger [1] :

\operatørnavn {fusc} (k)={\begin{cases}1,&k=1;\\\operatørnavn {fusc} (n),&k=2n,n\i \mathbb {N} ;\\ \operatørnavn {fusc} (n)+\operatørnavn {fusc} (n+1),&k=2n+1,n\i \mathbb {N} .\end{cases}}

Sekvensen genereret af denne funktion er

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

Dette er Stern-kiselalgersekvensen (sekvens A002487 i OEIS ). fusc-funktionen er relateret til Culkin-Wilf-sekvensen , nemlig det th led i Culkin-Wilf-sekvensen er , og korrespondancen $n$ $\operatørnavn {fusc} (n)/\operatørnavn {fusc} (n+1)$

n\mapsto {\frac {\operatørnavn {fusc} (n)}{\operatørnavn {fusc} (n+1))),\quad n=1,2,3,\dots

er en en-til-en overensstemmelse mellem mængden af naturlige tal og mængden af positive rationelle tal.

Egenskaber

Lad og , så [1] : $f_{1}=\operatørnavn {fusc} (n_{1})$ $f_{2}=\operatørnavn {fusc} (n_{2})$

hvis der eksisterer sådan, at , så og er coprime; $N$ ${\displaystyle n_{1}+n_{2}=2^{N))$ $f_1$ $f_{2}$
hvis og er coprime, så findes der , og sådan at . $f_1$ $f_{2}$ $n_{1}$ $n_{2}$ $N$ ${\displaystyle n_{1}+n_{2}=2^{N))$

Værdien af funktionen ændres ikke, hvis alle interne cifre [2] inverteres i den binære repræsentation af argumentet . For eksempel fordi 19 10 = 10011 2 og 29 10 = 11101 2 . $\operatørnavn {fusc} (19)=\operatørnavn {fusc} (29)$

Værdien af funktionen vil heller ikke ændre sig, hvis alle cifrene er skrevet i den binære repræsentation af argumentet i omvendt rækkefølge [2] . For eksempel fordi 19 10 = 10011 2 og 25 10 = 11001 2 . $\operatørnavn {fusc} (19)=\operatørnavn {fusc} (25)$

Værdien er lige, hvis og kun hvis den er delelig med 3 [2] . $\operatørnavn {fusc} (n)$ $n$

Funktionen har egenskaberne

\operatørnavn {fusc} (2^{n})=1,

\operatornavn {fusc} (3\cdot 2^{n})=2.

Værdien er lig med antallet af alle ulige stirlingtal af den anden slags form , og er lig med antallet af alle ulige binomiale koefficienter på formen , hvor [3] . $\operatørnavn {fusc} (n)$ $S_{2}(n+1,2r+1)$ $\operatørnavn {fusc} (n+1)$ ${\binom {nr}{r))$ $0\leqslant 2r<n$