Fusc funktion

Funktionen fusc är en heltalsfunktion på mängden naturliga tal, definierad av E. Dijkstra enligt följande [1] :

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

Sekvensen som genereras av denna funktion är

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

Detta är Stern-kiselalgersekvensen (sekvens A002487 i OEIS ). fusc-funktionen är relaterad till Culkin-Wilf-sekvensen , nämligen den :e termen i Culkin-Wilf-sekvensen är , och korrespondensen $n$ $\operatörsnamn {fusc} (n)/\operatörsnamn {fusc} (n+1)$

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

är en en-till-en-överensstämmelse mellan mängden naturliga tal och mängden positiva rationella tal.

Egenskaper

Låt och , sedan [1] : $f_{1}=\operatörsnamn {fusc} (n_{1})$ $f_{2}=\operatörsnamn {fusc} (n_{2})$

om det finns sådana att , då och är coprime; $N$ ${\displaystyle n_{1}+n_{2}=2^{N))$ $f_1$ $f_{2}$
om och är coprime, så finns det , och sådant som . $f_1$ $f_{2}$ $n_{1}$ $n_{2}$ $N$ ${\displaystyle n_{1}+n_{2}=2^{N))$

Funktionens värde ändras inte om alla interna siffror [2] inverteras i den binära representationen av argumentet . Till exempel eftersom 19 10 = 10011 2 och 29 10 = 11101 2 . $\operatörsnamn {fusc} (19)=\operatörsnamn {fusc} (29)$

Funktionens värde ändras inte heller om alla siffror skrivs i den binära representationen av argumentet i omvänd ordning [2] . Till exempel eftersom 19 10 = 10011 2 och 25 10 = 11001 2 . $\operatörsnamn {fusc} (19)=\operatörsnamn {fusc} (25)$

Värdet är jämnt om och endast om det är delbart med 3 [2] . $\operatörsnamn {fusc} (n)$ $n$

Funktionen har egenskaperna

\operatörsnamn {fusc} (2^{n})=1,

\operatörsnamn {fusc} (3\cdot 2^{n})=2.

Värdet är lika med numret av alla udda Stirlingtal av den andra typen av formen , och är lika med antalet alla udda binomialkoefficienter i formen , där [3] . $\operatörsnamn {fusc} (n)$ $S_{2}(n+1,2r+1)$ $\operatörsnamn {fusc} (n+1)$ ${\binom {nr}{r))$ $0\leqslant 2r<n$

Beräkning

Förutom den rekursiva utvärderingen av fusc-funktionen per definition, finns det en enkel iterativ algoritm [1] :

fusc(N): n, a, b = N, 1, 0 medan n ≠ 0: om n är jämnt: a, n = a + b, n / 2 om n är udda: b, n = a + b, (n - 1) / 2 fusc(N) = b

Anteckningar

↑ 1 2 3 EWD 570: En övning för Dr. RM Burstall Arkiverad 15 augusti 2021 på Wayback Machine .
↑ 1 2 3 EWD 578: Mer om funktionen "fusc" (En uppföljare till EWD570) Arkiverad 15 augusti 2021 på Wayback Machine .
↑ Carlitz, L. Ett problem i partitioner relaterade till Stirling-talen // Bulletin of the American Mathematical Society. - 1964. - Vol. 70, nr 2 . - S. 275-278. Arkiverad från originalet den 21 januari 2022.

Länkar

sekvens A002487 i OEIS

Se även

Culkin Tree - Wilf