Moseri-de Bruijni järjestuse generaator | Neljandate astmete kalkulaator

Mis on Moseri-de Bruijni jada?

Moseri-de Bruijni jada on täisarvude loend, mille iga liiget saab esitada arvu 4 erinevate astmete summana. Jada algab arvudega 0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85 ning jätkub lõpmatult. Jada on saanud nime matemaatikute Leo Moseri ja Nicolaas Govert de Bruijni järgi. Täisarvujadade veebientsüklopeedias on see registreeritud tähisega A000695.

Arv kuulub jadasse parajasti siis, kui selle 4-süsteemis esitus kasutab ainult numbreid 0 ja 1, mitte kunagi numbreid 2 ega 3. Näiteks 21 on 4-süsteemis kujul 111, seega kuulub see jadasse. Arv 22 on 4-süsteemis kujul 112, seega see jadasse ei kuulu.

Moseri-de Bruijni jada valem

Jada saab määratleda kolmel samaväärsel viisil.

Arvu 4 erinevate astmete summa

Arv n kuulub jadasse, kui seda saab esitada kujul

$n = \sum_{i \in S} 4^i$

mingi mittenegatiivsete täisarvude hulga S korral, kus iga arvu 4 astet kasutatakse kõige rohkem üks kord.

4-süsteemi numbrite test

Kirjutage arv 4-süsteemis. Kui iga number on 0 või 1, kuulub arv jadasse. Kui mõni number on 2 või 3, siis see jadasse ei kuulu.

Kahendsüsteemi numbrite asendamine 4-süsteemi numbritega

Kui liikmeid loendada alates n = 0, on indeksil n asuv liige

$M(n) = \sum_{i=0}^{k} b_i \cdot 4^i$

kus $b_i$ on n-i kahendsüsteemi numbrid. Teisisõnu kirjutage n kahendsüsteemis ja lugege seejärel iga kahendsüsteemi number samal kohal paiknevaks 4-süsteemi numbriks. Generaator kasutab seda meetodit, sest selleks tuleb kontrollida ainult bitte ja liita arve.

Mitmenda liikme arvutamine

M(n) leidmiseks teeb generaator iga indeksi n korral järgmist, alustades väärtusest n = 0:

1. Vaadake n-i kahendkuju.
2. Iga biti korral, mille väärtus on 1 ja asukoht j, liitke jooksvale summale 4^j.
3. Jätke bitid väärtusega 0 vahele.
4. Jooksev summa on M(n).

Läbitöötatud näide: M(5)

• 5 kahendsüsteemis on 101.
• Bitt 0 (parempoolne) on 1, seega liidame 4⁰ = 1.
• Bitt 1 on 0, seega ei liideta midagi.
• Bitt 2 on 1, seega liidame 4² = 16.
• Summa: 1 + 16 = 17.

Seega M(5) = 17. See on generaatori toodetav kuues väärtus, sest loendamine algab väärtusest M(0).

Näide: esimesed 32 liiget

Kuidas kontrollida, kas arv kuulub jadasse

Teisendage arv 4-ndsüsteemi ja lugege selle numbreid.

• 85: 4-ndsüsteemis on 85 kujul 1111 (64 + 16 + 4 + 1). Esinevad ainult numbrid 0 ja 1, seega 85 kuulub jadasse.
• 90: 4-ndsüsteemis on 90 kujul 1122. See sisaldab numbrit 2, seega 90 jadasse ei kuulu.

Kasvukiirus

Jada kasvab kiiresti, sest indeksi iga lisabitt võib ligikaudu neljakordistada selle väärtuse, mille see summale lisab. M(19) on 261. M(99) on 5 125. M(999), suurim liik, mida see generaator suudab toota, on 349 205. Indeksi kasvades paiknevad liikmed üksteisest üha kaugemal, mistõttu on jada hõre: enamik täisarve ei esine selles kunagi, kuigi liikmeid on lõpmata palju.

Kuidas kasutada Moseri-de Bruijni jada generaatorit

1. Sisestage genereeritavate liikmete arv. Kui väli jäetakse tühjaks, on vaikeväärtus 20.
2. Liikmete loend uueneb automaatselt, alustades väärtusest M(0).
3. Kogu loendi kopeerimiseks kasutage nuppu „Kopeeri tulemus“.

Tööriist aktsepteerib täisarve vahemikus 1 kuni 1000. Komakohaga arvud, negatiivsed arvud ja mittenumbrilised sisestused lükatakse tagasi. 20 liikme taotlemisel tagastatakse M(0) kuni M(19); viimane kuvatav väärtus on 261. Kõik arvutused tehakse brauseris, seega kuvatakse tulemused kohe ja andmeid serverisse ei saadeta.

Seotud jadad

• Arvu 2 astmed (OEIS A000079): 1, 2, 4, 8, 16, 32 jne. Need on tavaliste kahendarvude koostisosad.
• Arvu 3 erinevate astmete summad (OEIS A005836): 0, 1, 3, 4, 9, 10, 12, 13 jne. See põhineb samal ideel nagu Moseri-de Bruijni jada, kuid kasutab 3-süsteemi 4-süsteemi asemel.
• Fibbinaarsed arvud (OEIS A003714): 0, 1, 2, 4, 5, 8, 9, 10 jne. Arvud, mille kahendkujus ei esine kaht järjestikust 1-bitti.

Ajalugu

Leo Moser (1921-1970) oli Austria-Kanada matemaatik, kes tegeles arvuteooria, kombinatoorika ja geomeetriaga. Nicolaas Govert de Bruijn (1918-2012) oli Hollandi matemaatik, kes oli tuntud oma töö poolest kombinatoorikas, graafiteoorias ja arvutiteaduses; tema samanimetuid, kuid sellega mitteseotud de Bruijni jadasid kasutatakse laialdaselt kodeerimisteoorias. Mõlemad uurisid aditiivseid baase: täisarvude hulki, näiteks arvu 4 astmeid, millest iga esitatav arv saadakse täpselt ühe summana. Nende nime kandev jada on üks sellise baasi näide.

Korduma kippuvad küsimused

Milleks kasutatakse Moseri-de Bruijni jada?

Seda kasutatakse aditiivses arvuteoorias ja kombinatoorikas, eriti summavabade hulkade ja aditiivsete baaside uurimisel. Samuti õpetatakse selle abil arvutiteaduses arvusüsteemide teisendamist ja bitikaupa tehtavaid operatsioone.

Kuidas genereerida Moseri-de Bruijni jada?

Kirjutage indeks n kahendsüsteemis ja käsitlege seejärel iga kahendsüsteemi numbrit samal kohal oleva 4-ndsüsteemi numbrina. Kui n = 5 (kahendsüsteemis 101), annab see 4² + 4⁰ = 17.

Kuidas kontrollida, kas arv kuulub jadasse?

Teisendage arv 4-süsteemi. Kui iga number on 0 või 1, kuulub arv jadasse. Kui mõni number on 2 või 3, siis see jadasse ei kuulu.

Mis on n-nda liikme valem?

M(n) = summa kõigi i-de korral avaldistest $b_i \cdot 4^i$, kus $b_i$ on n-i kahendsüsteemi numbrid.

Kas jada on lõpmatu?

Jah. Sellel on lõpmata palju liikmeid, kuigi n-i kasvades paiknevad need üksteisest üha kaugemal.

Mille poolest erineb see kahendsüsteemist?

Kahendsüsteem ehk arvu 2 erinevate astmete summad võimaldab esitada iga mittenegatiivse täisarvu. Moseri-de Bruijni jada kasutab selle asemel arvu 4 astmeid, mistõttu jääb enamik täisarve välja.