Fusc funkció

A fusc függvény egy egész szám függvény a természetes számok halmazán, amelyet E. Dijkstra a következőképpen határoz meg [1] :

\operatorname {fusc} (k)={\begin{cases}1,&k=1;\\\operátornév {fusc} (n),&k=2n,n\in \mathbb {N} ;\\ \operátornév {fusc} (n)+\operátornév {fusc} (n+1),&k=2n+1,n\in \mathbb {N} .\end{cases}}

A függvény által generált sorozat a

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

Ez a Stern kovaatom szekvencia ( A002487 szekvencia az OEIS -ben ). A fusc függvény a Culkin-Wilf sorozathoz kapcsolódik , nevezetesen a Culkin-Wilf szekvencia harmadik tagja , és a megfelelés $n$ $\operátornév {fusc} (n)/\operátornév {fusc} (n+1)$

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

a természetes számok halmaza és a pozitív racionális számok halmaza közötti egy-egy megfeleltetés.

Tulajdonságok

Legyen és , majd [1] : $f_{1}=\operátornév {fusc} (n_{1})$ $f_{2}=\operátornév {fusc} (n_{2})$

ha létezik olyan, hogy , Akkor és a coprime; $N$ ${\displaystyle n_{1}+n_{2}=2^{N))$ $f_1$ $f_{2}$
ha és a koprime, akkor léteznek , és olyan, hogy . $f_1$ $f_{2}$ $n_{1}$ $n_{2}$ $N$ ${\displaystyle n_{1}+n_{2}=2^{N))$

A függvény értéke nem változik, ha az argumentum bináris reprezentációjában az összes belső számjegyet [2] megfordítják . Például azért, mert 19 10 = 10011 2 és 29 10 = 11101 2 . $\operátornév {fusc} (19)=\operátornév {fusc} (29)$

A függvény értéke akkor sem változik, ha az összes számjegyet az argumentum bináris reprezentációjában fordított sorrendben írjuk be [2] . Például azért, mert 19 10 = 10011 2 és 25 10 = 11001 2 . $\operátornév {fusc} (19)=\operátornév {fusc} (25)$

Az érték akkor és csak akkor páros, ha osztható 3 -mal [2] . $\operatorname {fusc} (n)$ $n$

A függvénynek vannak tulajdonságai

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

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

Az érték megegyezik az űrlap második fajtájához tartozó összes páratlan Stirling-szám számával , és egyenlő a forma összes páratlan binomiális együtthatójának számával , ahol [3] . $\operatorname {fusc} (n)$ $S_{2}(n+1,2r+1)$ $\operatorname {fusc} (n+1)$ ${\binom {nr}{r))$ $0\leqslant 2r<n$

Számítás

A fusc függvény definíciós rekurzív kiértékelése mellett létezik egy egyszerű iteratív algoritmus [1] :

fusc(N): n, a, b = N, 1, 0 míg n ≠ 0: ha n páros: a, n = a + b, n / 2 ha n páratlan: b, n = a + b, (n - 1) / 2 fusc(N) = b

Jegyzetek

↑ 1 2 3 EWD 570: Gyakorlat Dr. RM Burstall archiválva : 2021. augusztus 15. a Wayback Machine -nél .
↑ 1 2 3 EWD 578: További információ a "fusc" funkcióról (az EWD570 folytatása) Archiválva : 2021. augusztus 15. a Wayback Machine -nél .
↑ Carlitz, L. A Stirling-számokkal kapcsolatos partíciók problémája // Bulletin of the American Mathematical Society. - 1964. - 1. évf. 70, 2. sz . - 275-278. Az eredetiből archiválva : 2022. január 21.

Linkek

A002487 szekvencia az OEIS -ben

Lásd még

Culkin Tree – Wilf