Funcția fusc

Funcția fusc este o funcție întreagă pe mulțimea numerelor naturale, definită de E. Dijkstra după cum urmează [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\în \mathbb {N} .\end{cases}}

Secvența generată de această funcție este

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

Aceasta este secvența de diatomee Stern (secvența A002487 în OEIS ). Funcția fusc este legată de secvența Culkin-Wilf , și anume, al treilea termen al secvenței Culkin-Wilf este , iar corespondența $n$ $\operatorname {fusc} (n)/\operatorname {fusc} (n+1)$

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

este o corespondență unu-la-unu între mulțimea numerelor naturale și mulțimea numerelor raționale pozitive.

Proprietăți

Fie și , apoi [1] : $f_{1}=\operatorname {fusc} (n_{1})$ $f_{2}=\operatorname {fusc} (n_{2})$

dacă există astfel încât , atunci și sunt coprime; $N$ $n_{1}+n_{2}=2^{N)$ $f_1$ $f_{2}$
dacă și sunt coprime, atunci există , și astfel încât . $f_1$ $f_{2}$ $n_{1}$ $n_{2}$ $N$ $n_{1}+n_{2}=2^{N)$

Valoarea funcției nu se va schimba dacă toate cifrele interne [2] sunt inversate în reprezentarea binară a argumentului . De exemplu, deoarece 19 10 = 10011 2 și 29 10 = 11101 2 . $\operatorname {fusc} (19)=\operatorname {fusc} (29)$

De asemenea, valoarea funcției nu se va modifica dacă toate cifrele sunt scrise în reprezentarea binară a argumentului în ordine inversă [2] . De exemplu, deoarece 19 10 = 10011 2 și 25 10 = 11001 2 . $\operatorname {fusc} (19)=\operatorname {fusc} (25)$

Valoarea este chiar dacă și numai dacă este divizibil cu 3 [2] . $\operatorname {fusc} (n)$ $n$

Funcția are proprietăți

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

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

Valoarea este egală cu numărul tuturor numerelor impare Stirling din al doilea fel al formei și este egală cu numărul tuturor coeficienților binomi impari din forma , unde [3] . $\operatorname {fusc} (n)$ $S_{2}(n+1,2r+1)$ $\operatorname {fusc} (n+1)$ ${\binom {nr}{r)}$ $0\leqslant 2r<n$

Calcul

Pe lângă evaluarea recursivă a funcției fusc prin definiție, există un algoritm iterativ simplu [1] :

fusc(N): n, a, b = N, 1, 0 în timp ce n ≠ 0: dacă n este par: a, n = a + b, n / 2 daca n este impar: b, n = a + b, (n - 1) / 2 fusc(N) = b

Note

↑ 1 2 3 EWD 570: Un exercițiu pentru Dr. RM Burstall Arhivat 15 august 2021 la Wayback Machine .
↑ 1 2 3 EWD 578: Mai multe despre funcția „fusc” (O continuare a EWD570) Arhivat la 15 august 2021 la Wayback Machine .
↑ Carlitz, L. A problem in partitions related to the Stirling numbers // Bulletin of the American Mathematical Society. - 1964. - Vol. 70, nr. 2 . - P. 275-278. Arhivat din original pe 21 ianuarie 2022.

Link -uri

secvența A002487 în OEIS

Vezi și

Arborele Culkin - Wilf