Funkce fusc

Funkce fusc je celočíselná funkce na množině přirozených čísel, kterou definoval E. Dijkstra takto [1] :

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

Sekvence generovaná touto funkcí je

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

Toto je Sternova sekvence rozsivek (sekvence A002487 v OEIS ). Funkce fusc souvisí s Culkin-Wilfovou sekvencí , jmenovitě, tý člen Culkin-Wilfovy sekvence je , a korespondence $n$ $\operatorname {fusc} (n)/\operatorname {fusc} (n+1)$

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

je korespondence jedna ku jedné mezi množinou přirozených čísel a množinou kladných racionálních čísel.

Vlastnosti

Nechat a , pak [1] : $f_{1}=\operatorname {fusc} (n_{1})$ $f_{2}=\operatorname {fusc} (n_{2})$

pokud existuje takové, že , pak a jsou coprime; $N$ ${\displaystyle n_{1}+n_{2}=2^{N))$ $f_1$ $f_{2}$
jestliže a jsou coprime, pak existují , a takové, že . $f_1$ $f_{2}$ $n_{1}$ $n_{2}$ $N$ ${\displaystyle n_{1}+n_{2}=2^{N))$

Hodnota funkce se nezmění, pokud jsou všechny vnitřní číslice [2] v binární reprezentaci argumentu invertovány . Například proto, že 19 10 = 10011 2 a 29 10 = 11101 2 . $\operatorname {fusc} (19)=\operatorname {fusc} (29)$

Hodnota funkce se také nezmění, pokud jsou všechny číslice zapsány v binární reprezentaci argumentu v opačném pořadí [2] . Například proto, že 19 10 = 10011 2 a 25 10 = 11001 2 . $\operatorname {fusc} (19)=\operatorname {fusc} (25)$

Hodnota je sudá právě tehdy, když je dělitelná 3 [2] . $\operatorname {fusc} (n)$ $n$

Funkce má vlastnosti

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

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

Hodnota je rovna počtu všech lichých Stirlingových čísel druhého druhu formuláře , a je rovna počtu všech lichých binomických koeficientů formuláře , kde [3] . $\operatorname {fusc} (n)$ $S_{2}(n+1,2r+1)$ $\operatorname {fusc} (n+1)$ ${\binom {nr}{r))$ $0\leqslant 2r<n$

Výpočet

Kromě rekurzivního vyhodnocení funkce fusc podle definice existuje jednoduchý iterační algoritmus [1] :

fusc(N): n, a, b = N, 1,0 zatímco n ≠ 0: pokud n je sudé: a, n = a + b, n/2 pokud je n liché: b, n = a + b, (n - 1) / 2 fusc(N) = b

Poznámky

↑ 1 2 3 EWD 570: Cvičení pro Dr. RM Burstall Archivováno 15. srpna 2021 na Wayback Machine .
↑ 1 2 3 EWD 578: Více o funkci „fusc“ (pokračování EWD570) Archivováno 15. srpna 2021 na Wayback Machine .
↑ Carlitz, L. Problém v oddílech související se Stirlingovými čísly // Bulletin of the American Mathematical Society. - 1964. - Sv. 70, č. 2 . - S. 275-278. Archivováno z originálu 21. ledna 2022.

Odkazy

sekvence A002487 v OEIS

Viz také

Culkin Tree - Wilf