Fusc-toiminto

Funktio fusc on luonnollisten lukujen joukossa oleva kokonaislukufunktio, jonka E. Dijkstra on määritellyt seuraavasti [1] :

\operaattorinnimi {fusc} (k)={\begin{cases}1,&k=1;\\\operaattorin nimi {fusc} (n),&k=2n,n\in \mathbb {N} ;\\ \operaattorinnimi {fusc} (n)+\operaattorin nimi {fusc} (n+1),&k=2n+1,n\in \mathbb {N} .\end{cases}}

Tämän funktion luoma sekvenssi on

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

Tämä on Stern piileväsekvenssi (sekvenssi A002487 OEIS : ssä ). Fusc-funktio liittyy Culkin-Wilf-sekvenssiin , nimittäin Culkin-Wilf-sekvenssin termi on , ja vastaavuus $n$ $\operaattorin nimi {fusc} (n)/\operaattorin nimi {fusc} (n+1)$

n\mapsto {\frac {\operaattorin nimi {fusc} (n)}{\operaattorin nimi {fusc} (n+1))),\quad n=1,2,3,\pisteet

on yksi yhteen vastaavuus luonnollisten lukujen joukon ja positiivisten rationaalilukujen joukon välillä.

Ominaisuudet

Olkoon ja , sitten [1] : $f_{1}=\operaattorinimi {fusc} (n_{1})$ $f_{2}=\operaattorinimi {fusc} (n_{2})$

jos on olemassa sellainen, että , Sitten ja ovat coprime; $N$ ${\displaystyle n_{1}+n_{2}=2^{N))$ $f_1$ $f_{2}$
jos ja ovat koprime, niin on olemassa , Ja sellainen, että . $f_1$ $f_{2}$ $n_{1}$ $n_{2}$ $N$ ${\displaystyle n_{1}+n_{2}=2^{N))$

Funktion arvo ei muutu, jos kaikki sisäiset numerot [2] käännetään argumentin binääriesityksessä . Esimerkiksi koska 19 10 = 10011 2 ja 29 10 = 11101 2 . $\operaattorin nimi {fusc} (19)=\operaattorin nimi {fusc} (29)$

Funktion arvo ei myöskään muutu, jos kaikki numerot kirjoitetaan argumentin binääriesitykseen käänteisessä järjestyksessä [2] . Esimerkiksi koska 19 10 = 10011 2 ja 25 10 = 11001 2 . $\operaattorin nimi {fusc} (19)=\operaattorin nimi {fusc} (25)$

Arvo on parillinen silloin ja vain, jos se on jaollinen 3: lla [2] . $\operaattorin nimi {fusc} (n)$ $n$

Funktiolla on ominaisuuksia

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

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

Arvo on yhtä suuri kuin muodon toisen lajin parittomat Stirling-luvut ja on yhtä suuri kuin muodon kaikkien parittomien binomikertoimien lukumäärä , jossa [3] . $\operaattorin nimi {fusc} (n)$ $S_{2}(n+1,2r+1)$ $\operaattorin nimi {fusc} (n+1)$ ${\binom {nr}{r))$ $0\leqslant 2r<n$

Laskenta

Fusc-funktion määritelmän mukaisen rekursiivisen arvioinnin lisäksi on olemassa yksinkertainen iteratiivinen algoritmi [1] :

fusc(N): n, a, b = N, 1, 0 kun taas n ≠ 0: jos n on parillinen: a, n = a + b, n/2 jos n on pariton: b, n = a + b, (n - 1) / 2 fusc(N) = b

Muistiinpanot

↑ 1 2 3 EWD 570: Harjoitus Dr. RM Burstall Arkistoitu 15. elokuuta 2021 Wayback Machinessa .
↑ 1 2 3 EWD 578: Lisätietoja funktiosta "fusc" (jatkoa EWD570:lle) Arkistoitu 15. elokuuta 2021 Wayback Machinessa .
↑ Carlitz, L. Stirling-lukuihin liittyvä ongelma osioissa // Bulletin of the American Mathematical Society. - 1964. - Voi. 70, nro 2 . - s. 275-278. Arkistoitu alkuperäisestä 21. tammikuuta 2022.

Linkit

sekvenssi A002487 OEIS : ssä

Katso myös

Culkin Tree - Wilf