Mosera-de Bruiņa secības ģenerators | Četru pakāpju kalkulators

Kas ir Mosera–de Bruijna virkne?

Mosera–de Bruijna virkne ir veselu skaitļu saraksts, kuru katru var izteikt kā dažādu skaitļa 4 pakāpju summu. Tā sākas ar 0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85 un turpinās bezgalīgi. Tā nosaukta matemātiķu Leo Mosera un Nicolaas Govert de Bruijna vārdā. Tiešsaistes veselu skaitļu virkņu enciklopēdijā tā kataloģizēta kā A000695.

Skaitlis pieder virknei tieši tad, ja tā pierakstā ar bāzi 4 tiek izmantoti tikai cipari 0 un 1, bet nekad 2 vai 3. Piemēram, 21 bāzē 4 tiek pierakstīts kā 111, tāpēc tas pieder virknei. Skaitlis 22 bāzē 4 tiek pierakstīts kā 112, tāpēc tas virknei nepieder.

Mosera–de Bruijna virknes formula

Virkni var definēt trīs līdzvērtīgos veidos.

Dažādu skaitļa 4 pakāpju summa

Skaitlis n pieder virknei, ja to var pierakstīt kā

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

kādas nenegatīvu veselu skaitļu kopas S elementu summu, kur katra 4 pakāpe tiek izmantota ne vairāk kā vienu reizi.

Ciparu pārbaude bāzē 4

Pierakstiet skaitli bāzē 4. Ja katrs cipars ir 0 vai 1, skaitlis pieder virknei. Ja kāds cipars ir 2 vai 3, tas virknei nepieder.

Binārā pieraksta aizstāšana ar pierakstu bāzē 4

Skaitot virknes locekļus no n = 0, loceklis ar indeksu n ir

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

kur $b_i$ ir skaitļa n binārie cipari. Citiem vārdiem: pierakstiet n binārajā sistēmā, pēc tam nolasiet katru bināro ciparu kā bāzes 4 ciparu tajā pašā pozīcijā. Šo metodi izmanto ģenerators, jo tam jāapstrādā tikai biti un jāsaskaita skaitļi.

Kā aprēķināt n-to locekli

Lai atrastu M(n), ģenerators katram indeksam n, sākot ar n = 0, veic šādas darbības:

1. Aplūko n bināro pierakstu.
2. Katram bitam, kas vienāds ar 1 un atrodas pozīcijā j, pieskaita 4^j uzkrātajai summai.
3. Izlaiž bitus, kas vienādi ar 0.
4. Uzkrātā summa ir M(n).

Aprēķina piemērs: M(5)

• 5 binārajā sistēmā ir 101.
• Bits 0 (labajā malā) ir 1, tāpēc pieskaita 4⁰ = 1.
• Bits 1 ir 0, tāpēc neko nepieskaita.
• Bits 2 ir 1, tāpēc pieskaita 4² = 16.
• Kopā: 1 + 16 = 17.

Tātad M(5) = 17. Tā ir sestā ģeneratora izveidotā vērtība, jo skaitīšana sākas ar M(0).

Piemērs: pirmie 32 locekļi

Kā pārbaudīt, vai skaitlis pieder virknei

Pārveidojiet skaitli uz bāzi 4 un nolasiet tā ciparus.

• 85: bāzē 4 skaitlis 85 ir 1111 (64 + 16 + 4 + 1). Tajā parādās tikai 0 un 1, tāpēc 85 pieder virknei.
• 90: bāzē 4 skaitlis 90 ir 1122. Tajā ir 2, tāpēc 90 virknei nepieder.

Augšanas ātrums

Virkne aug strauji, jo katrs papildu bits indeksā var aptuveni četrkāršot tā pievienoto vērtību. M(19) ir 261. M(99) ir 5 125. M(999), lielākais loceklis, ko šis ģenerators var izveidot, ir 349 205. Pieaugot indeksam, locekļi atrodas arvien tālāk cits no cita, tāpēc virkne ir reta: lielākā daļa veselo skaitļu tajā nekad neparādās, lai gan tai ir bezgalīgi daudz locekļu.

Kā izmantot Mosera–de Bruijna virknes ģeneratoru

1. Ievadiet ģenerējamo locekļu skaitu. Ja lauks ir tukšs, pēc noklusējuma tiek izmantots 20.
2. Locekļu saraksts tiek automātiski atjaunināts, sākot ar M(0).
3. Nokopējiet visu sarakstu, izmantojot pogu “Kopēt rezultātu”.

Rīks pieņem veselus skaitļus no 1 līdz 1000. Decimāldaļas, negatīvi skaitļi un ieraksti, kas nav skaitļi, tiek noraidīti. Pieprasot 20 locekļus, tiek atgriezti M(0) līdz M(19); pēdējā parādītā vērtība ir 261. Visi aprēķini notiek pārlūkprogrammā, tāpēc rezultāti parādās uzreiz un dati netiek nosūtīti serverim.

Saistītās virknes

• Skaitļa 2 pakāpes (OEIS A000079): 1, 2, 4, 8, 16, 32 un tā tālāk. Tās ir parasto bināro skaitļu pamatelementi.
• Dažādu skaitļa 3 pakāpju summas (OEIS A005836): 0, 1, 3, 4, 9, 10, 12, 13 un tā tālāk. Tā ir tāda pati ideja kā Mosera–de Bruijna virknē, tikai veidota no bāzes 3, nevis bāzes 4.
• Fibinārie skaitļi (OEIS A003714): 0, 1, 2, 4, 5, 8, 9, 10 un tā tālāk. Tie ir skaitļi, kuru binārajā pierakstā nav divu pēc kārtas esošu 1.

Vēsture

Leo Mosers (1921-1970) bija austriešu un kanādiešu matemātiķis, kas strādāja skaitļu teorijā, kombinatorikā un ģeometrijā. Nicolaas Govert de Bruijn (1918-2012) bija nīderlandiešu matemātiķis, kas pazīstams ar darbu kombinatorikā, grafu teorijā un datorzinātnē; viņa vārdā nosauktās, ar šo nesaistītās de Bruijna virknes plaši izmanto kodēšanas teorijā. Abi pētīja aditīvās bāzes: veselu skaitļu kopas, piemēram, skaitļa 4 pakāpes, no kurām katram attēlojamam skaitlim ir tieši viens summas pieraksts. Virkne, kurai piešķirti viņu vārdi, ir viens šādas bāzes piemērs.

Biežāk uzdotie jautājumi

Kam izmanto Mosera–de Bruijna virkni?

Tā tiek izmantota aditīvajā skaitļu teorijā un kombinatorikā, īpaši summu brīvu kopu un aditīvo bāzu pētījumos. To izmanto arī, lai datorzinātnē mācītu bāzu pārveidošanu un bitu operācijas.

Kā ģenerē Mosera–de Bruijna virkni?

Pierakstiet indeksu n binārajā sistēmā, pēc tam nolasiet katru bināro ciparu kā bāzes 4 ciparu tajā pašā pozīcijā. Ja n = 5 (binārais pieraksts 101), iegūst 4² + 4⁰ = 17.

Kā pārbaudīt, vai skaitlis pieder virknei?

Pārveidojiet to uz bāzi 4. Ja katrs cipars ir 0 vai 1, skaitlis pieder virknei. Ja kāds cipars ir 2 vai 3, tas virknei nepieder.

Kāda ir n-tā locekļa formula?

M(n) = visu i vērtību summa, kas ietver $b_i \cdot 4^i$, kur $b_i$ ir skaitļa n binārie cipari.

Vai virkne ir bezgalīga?

Jā. Tai ir bezgalīgi daudz locekļu, lai gan, pieaugot n, tie atrodas arvien tālāk cits no cita.

Ar ko tā atšķiras no binārās sistēmas?

Binārā sistēma, tas ir, atšķirīgu 2 pakāpju summas, ļauj attēlot katru nenegatīvu veselu skaitli. Mosera–de Bruijna virknē tā vietā izmanto 4 pakāpes, tāpēc lielākā daļa veselo skaitļu tajā neparādās.