Trenutno generirajte zaporedja Moser-de Bruijn. Izračunajte vsote različnih potenc 4 z reprezentacijami na osnovi 4 z uporabo samo 0 in 1. Brezplačno spletno orodje za matematično izobraževanje in raziskave.
Zaporedja Moser-de Bruijn vsebujejo števila, ki jih je mogoče napisati kot vsote različnih potenc števila 4
Zaporedje Moser-de Bruijn sestavljajo števila, ki jih lahko izrazimo kot vsote različnih potenc števila 4. Poimenovano po matematikoma Leoju Moserju in Nicolaasu Govertju de Bruijnu, se zaporedje začne: 0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85...
Kaj je zanimivega pri tem zaporedju? Ko katerikoli člen napišete v bazi 4, boste videli samo števke 0 in 1 - nikoli 2 ali 3. To pomeni, da je vsako število sestavljeno z dodajanjem potenc števila 4 (kot 4⁰, 4¹, 4², 4³), kjer se vsaka potenca pojavi bodisi enkrat ali sploh ne.
Tu je praktičen primer: Število 21 se pojavi v zaporedju, ker je enako 16 + 4 + 1, kar je 4² + 4¹ + 4⁰. V bazi 4 se to zapiše kot "111" - samo 0 in 1. Primerjajte to s številom 22, ki bi potrebovalo "2" v svoji predstavitvi v bazi 4 (122), zato ne pride v poštev.
Zaporedje se pojavlja v aditivni teoriji števil, kombinatoriki in raziskavah o sumljivih množicah. Lahko si ga predstavljate kot bratranca binarnega sistema - namesto potenc 2 delate s potencami 4. To ustvarja precej redkejše zaporedje, saj so izpuščena večina celih števil.
Uporaba tega generatorja je preprosta:
Izračuni potekajo v celoti v vašem brskalniku z JavaScriptom, zato ni zakasnitev strežnika ali odvisnosti od interneta - je hiter in deluje brez povezave, ko se stran naloži.
Generator preveri vaš vnos, da prepreči napake:
Zakaj omejitev 1000 členov? Čeprav je algoritem učinkovit, lahko generiranje tisoč člankov obremeni pomnilnik brskalnika, še posebej na mobilnih napravah. V praksi boste redko potrebovali več kot 100-200 členov za večino matematičnih analiz ali izobraževalnih namenov.
Zaporedje Moser-de Bruijn lahko opredelite na tri enakovredne načine, ki ponujajo različne vpoglede:
Aditivna oblika (Potence 4): Število n pripada zaporedju, ko ga lahko zapišete kot: kjer je S katerikoli nabor nenegativnih celih števil. Vsaka potenca 4 se lahko pojavi enkrat ali sploh ne - ponovitve niso dovoljene.
Predstavitev v bazi 4 (Najpreprostejši test): Pretvorite število v bazo 4. Če vidite samo 0 in 1 (brez 2 in 3), je v zaporedju. To je najhitrejši način za ročno preverjanje članstva.
Binarna korespondenca (Najbolj uporabno za računanje): Za določitev n-tega člena (začenši pri n=0): kjer so binarne številke n. Prevod: Vzemite binarno predstavitev vašega indeksa, nato zamenjajte vsak bit "1" z ustrezno potenco 4.
Poglejmo, kako te definicije delujejo:
Metoda binarne korespondence je tista, ki jo ta generator uporablja pod pokrovom - računsko je učinkovita, ker so bitovne operacije hitre.
Generator uporablja binarno korespondenco, ker je hitra in preprosta:
Postopek korak za korakom:
Praktičen Primer: Iskanje 6. člena (indeks 5)
Izračunajmo M(5) korak za korakom:
Ta metoda se dobro prilagaja. Za velike indekse gre v bistvu za premikanje bitov in seštevanje - operacije, ki jih sodobni procesorji opravljajo izjemno hitro.
Želite preveriti, ali specifično število pripada Moser-de Bruijnovi zaporedju? Uporabite test v bazi 4:
Primer: Je 85 v zaporedju?
Protipример: Je 90 v zaporedju?
Generator implementira to z uporabo bitnih operatorjev JavaScript, ki so lastni jeziku in visoko optimizirani v sodobnih brskalnikih.
Moser-de Bruijnovo zaporedje se ukvarja s čistimi celimi števili:
Ta eksponentna rast pomeni, da zaporedje hitro naraste. 20. člen je že 340, pri 100. členu pa se ukvarjate s števili v miljoniih.
Poučevanje številskih sistemov: Ko sem to uporabljal v učilnicah, učenci hitreje razumejo pretvorbe osnov, ko lahko eksperimentirajo z zaporedjem Moser-de Bruijn. Premošča vrzel med binarnim (osnova 2) in bolj kompleksnimi številskimi sistemi. Učenci takoj vidijo, kako spreminjanje osnove vpliva na gostoto zaporedja.
Razumevanje bitnih operacij: Študenti računalništva koristijo neposredno povezavo med binarno reprezentacijo in matematičnimi zaporedji. Algoritem prikazuje, kako manipulacija bitov prevaja v resnične matematične objekte - ne le abstraktne operacije.
Kombinatorika in vsotno proste množice: Raziskovalci, ki preučujejo aditivne osnove, uporabljajo takšna zaporedja za raziskovanje edinstvenih reprezentacij. Zaporedje Moser-de Bruijn je klasičen primer množice, kjer ima vsako predstavljivo število natančno eno reprezentacijo.
Aditivna teorija števil: Zaporedje pomaga preiskovati vprašanja o razgradnji celih števil v vsote. Povezano je s problemi v Spletni enciklopediji celoštevilskih zaporedij (OEIS), kjer je katalogiziran kot A000695.
Oblikovanje algoritmov: Algoritem generiranja prikazuje učinkovito konstrukcijo zaporedja. Lahko generirate tisoče členov z minimalnim računskim bremenom, kar je koristno za primerjavo algoritmov ali poučevanje učinkovitih programskih vzorcev.
Naloge prepoznavanja vzorcev: Pri delu z redkimi celoštevilskimi množicami ali shemami stiskanja podatkov razumevanje obnašanja zaporedij, kot je Moser-de Bruijn, pomaga pri sprejemanju odločitev o strategijah kodiranja.
Če vas zanima Moser-de Bruijnovo zaporedje, ponujajo ta sorodna zaporedja podobne vzorce z različnimi bazami ali omejitvami:
Potence 2 (OEIS A000079): 1, 2, 4, 8, 16, 32... Najpreprostejša aditivna baza. Vsaka potenca 2 se pojavi natanko enkrat in tvori gradnike binarnih številk.
Vse nenegativne cele številke (Binarne vsote): 0, 1, 2, 3, 4, 5, 6, 7... Ko dovolite katerokoli vsoto različnih potenc 2, dobite vse možne cele številke - to je tisto, kar binarna predstavitev počne.
Vsote različnih potenc 3 (OEIS A005836): 0, 1, 3, 4, 9, 10, 12, 13... Enak koncept kot Moser-de Bruijn, vendar z uporabo potenc 3 namesto 4. To so števila, katerih predstavitev v bazi 3 vsebuje samo 0 in 1.
Fibbinarna števila (OEIS A003714): 0, 1, 2, 4, 5, 8, 9, 10... Števila, katerih binarna oblika nima zaporednih 1. Povezana s Fibonaccijevimi številčnimi sistemi in Zeckendorfjevim izrekom.
Stanleyevo zaporedje: Analogija Moser-de Bruijnovega zaporedja v bazi 3 - števila, ki v svoji predstavitvi v bazi 3 nimajo 1 (dovoljeni so samo 0 in 2).
Spletna enciklopedija celoštevilskih zaporedij (OEIS) katalogizira stotine tisoč zaporedij. Iščite izraze kot so "aditivna baza", "vsoto prosta množica" ali "različne potence", da najdete sorodna zaporedja. Moser-de Bruijnovo zaporedje je v bazi OEIS označeno kot A000695.
Leo Moser (1921-1970) in Nicolaas Govert de Bruijn (1918-2012) sta oba naredila trajne prispevke matematiki, čeprav sta prihajala iz različnih okolij. Moser, avstrijski kanadski matematik, je obsežno deloval na področju teorije števil, kombinatorike in geometrije - morda ga poznate po Erdős–Moserjevem enačbi. De Bruijn, nizozemski matematik, je pustil pečat v kombinatoriki, teoriji grafov in računalniški znanosti. Njegova de Bruijnova zaporedja (različna od tega) so temeljna v teoriji kodiranja in se še vedno široko uporabljajo danes.
Njuno imensko zaporedje se je pojavilo v 1960-ih med preiskovanjem aditivne teorije števil. Matematiki so spraševali: kateri nabori celih števil vam omogočajo edinstveno predstavitev drugih celih števil? Potence 4 so se izkazale kot eden takih naborov, Moser-de Bruijnovo zaporedje pa zajema vse možne vsote, ki jih lahko naredite.
Zaporedje leži znotraj širše študije aditivnih baz - naborov celih števil, ki lahko zgradijo druga cela števila z dodajanjem. Nekatere baze omogočajo edinstvene predstavitve (kot so potence 4), druge pa ne. Razumevanje, katere baze imajo katere lastnosti, ostaja aktivno raziskovalno področje aditivne teorije števil.
To zaporedje najdete kot A000695 v OEIS, kjer so matematiki dokumentirali njegove povezave z binarno reprezentacijo, kvaternijskim (base-4) sistemom in kombinatoričnimi lastnostmi. Sodobna računalniška znanost je našla nove uporabe, zlasti v algoritmih, ki vključujejo manipulacijo bitov in učinkovito kodiranje redkih podatkovnih struktur.
Želite implementirati generator zaporedja Moser-de Bruijn sami? Tukaj so učinkovite implementacije v priljubljenih programskih jezikih. Vsak primer vključuje generator zaporedja in funkcijo za preverjanje članstva.
1def moser_de_bruijn(n):
2 """Generiraj prvih n členov zaporedja Moser-de Bruijn."""
3 sequence = []
4 for i in range(n):
5 term = 0
6 power = 1
7 temp = i
8 while temp > 0:
9 if temp & 1: # Preveri, ali je najmanj pomemben bit 1
10 term += power
11 power *= 4
12 temp >>= 1 # Desni premik za preverjanje naslednjega bita
13 sequence.append(term)
14 return sequence
15
16# Primer uporabe:
17terms = moser_de_bruijn(20)
18print("Prvih 20 členov zaporedja Moser-de Bruijn:")
19print(terms)
20# Izhod: [0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85, 256, 257, 260, 261]
21
22def is_moser_de_bruijn(num):
23 """Preveri, ali je število v zaporedju Moser-de Bruijn."""
24 while num > 0:
25 digit = num % 4
26 if digit > 1:
27 return False
28 num //= 4
29 return True
30
31# Preveri, ali je 21 v zaporedju
32print(f"Je 21 v zaporedju? {is_moser_de_bruijn(21)}") # True
33print(f"Je 22 v zaporedju? {is_moser_de_bruijn(22)}") # False
341function moserDeBruijn(n) {
2 const sequence = [];
3 for (let i = 0; i < n; i++) {
4 let term = 0;
5 let power = 1;
6 let temp = i;
7 while (temp > 0) {
8 if (temp & 1) { // Preveri, ali je najmanj pomemben bit 1
9 term += power;
10 }
11 power *= 4;
12 temp >>= 1; // Desni premik za preverjanje naslednjega bita
13 }
14 sequence.push(term);
15 }
16 return sequence;
17}
18
19// Primer uporabe:
20const terms = moserDeBruijn(20);
21console.log("Prvih 20 členov zaporedja Moser-de Bruijn:");
22console.log(terms);
23// Izhod: [0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85, 256, 257, 260, 261]
24
25function isMoserDeBruijn(num) {
26 while (num > 0) {
27 const digit = num % 4;
28 if (digit > 1) {
29 return false;
30 }
31 num = Math.floor(num / 4);
32 }
33 return true;
34}
35
36// Preveri specifična števila
37console.log(`Je 21 v zaporedju? ${isMoserDeBruijn(21)}`); // true
38console.log(`Je 22 v zaporedju? ${isMoserDeBruijn(22)}`); // false
391import java.util.ArrayList;
2import java.util.List;
3
4public class MoserDeBruijnGenerator {
5
6 public static List<Integer> generateSequence(int n) {
7 List<Integer> sequence = new ArrayList<>();
8 for (int i = 0; i < n; i++) {
9 int term = 0;
10 int power = 1;
11 int temp = i;
12 while (temp > 0) {
13 if ((temp & 1) == 1) { // Preveri, ali je najmanj pomemben bit 1
14 term += power;
15 }
16 power *= 4;
17 temp >>= 1; // Desni premik za preverjanje naslednjega bita
18 }
19 sequence.add(term);
20 }
21 return sequence;
22 }
23
24 public static boolean isMoserDeBruijn(int num) {
25 while (num > 0) {
26 int digit = num % 4;
27 if (digit > 1) {
28 return false;
29 }
30 num /= 4;
31 }
32 return true;
33 }
34
35 public static void main(String[] args) {
36 List<Integer> terms = generateSequence(20);
37 System.out.println("Prvih 20 členov zaporedja Moser-de Bruijn:");
38 System.out.println(terms);
39
40 System.out.println("Je 21 v zaporedju? " + isMoserDeBruijn(21)); // true
41 System.out.println("Je 22 v zaporedju? " + isMoserDeBruijn(22)); // false
42 }
43}
441#include <iostream>
2#include <vector>
3
4std::vector<int> moserDeBruijn(int n) {
5 std::vector<int> sequence;
6 for (int i = 0; i < n; i++) {
7 int term = 0;
8 int power = 1;
9 int temp = i;
10 while (temp > 0) {
11 if (temp & 1) { // Preveri, ali je najmanj pomemben bit 1
12 term += power;
13 }
14 power *= 4;
15 temp >>= 1; // Desni premik za preverjanje naslednjega bita
16 }
17 sequence.push_back(term);
18 }
19 return sequence;
20}
21
22bool isMoserDeBruijn(int num) {
23 while (num > 0) {
24 int digit = num % 4;
25 if (digit > 1) {
26 return false;
27 }
28 num /= 4;
29 }
30 return true;
31}
32
33int main() {
34 std::vector<int> terms = moserDeBruijn(20);
35 std::cout << "Prvih 20 členov zaporedja Moser-de Bruijn:" << std::endl;
36 for (int term : terms) {
37 std::cout << term << " ";
38 }
39 std::cout << std::endl;
40
41 std::cout << "Je 21 v zaporedju? " << (isMoserDeBruijn(21) ? "true" : "false") << std::endl;
42 std::cout << "Je 22 v zaporedju? " << (isMoserDeBruijn(22) ? "true" : "false") << std::endl;
43
44 return 0;
45}
46Vse te implementacije sledijo istemu vzorcu: uporaba bitnih operacij za branje binarne predstavitve indeksa, nato konstruiranje ustrezne vsote potenc 4. Funkcije za preverjanje članstva uporabljajo pristop base-4 - preverjanje, ali so digits omejeni na 0 in 1.
Z vidika zmogljivosti so te implementacije zelo učinkovite. Časovna zahtevnost je O(n × log n) za generiranje n členov, saj vsak člen zahteva pregled O(log i) bitov. Preverjanje članstva za eno število je O(log N), kjer je N število, ki se preverja.
Spodnja tabela prikazuje prvih 32 členov s popolnimi razčlenitvami. Opazite, kako predstavitev v bazi 4 vsebuje samo 0 in 1, in kako razčlenitev neposredno ustreza binarnim indeksom:
| Indeks | Člen | Razčlenitev | Baza-4 |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 1 | 4⁰ | 1 |
| 2 | 4 | 4¹ | 10 |
| 3 | 5 | 4¹ + 4⁰ | 11 |
| 4 | 16 | 4² | 100 |
| 5 | 17 | 4² + 4⁰ | 101 |
| 6 | 20 | 4² + 4¹ | 110 |
| 7 | 21 | 4² + 4¹ + 4⁰ | 111 |
| 8 | 64 | 4³ | 1000 |
| 9 | 65 | 4³ + 4⁰ | 1001 |
| 10 | 68 | 4³ + 4¹ | 1010 |
| 11 | 69 | 4³ + 4¹ + 4⁰ | 1011 |
| 12 | 80 | 4³ + 4² | 1100 |
| 13 | 81 | 4³ + 4² + 4⁰ | 1101 |
| 14 | 84 | 4³ + 4² + 4¹ | 1110 |
| 15 | 85 | 4³ + 4² + 4¹ + 4⁰ | 1111 |
| 16 | 256 | 4⁴ | 10000 |
| 17 | 257 | 4⁴ + 4⁰ | 10001 |
| 18 | 260 | 4⁴ + 4¹ | 10010 |
| 19 | 261 | 4⁴ + 4¹ + 4⁰ | 10011 |
| 20 | 272 | 4⁴ + 4² | 10100 |
| 21 | 273 | 4⁴ + 4² + 4⁰ | 10101 |
| 22 | 276 | 4⁴ + 4² + 4¹ | 10110 |
| 23 | 277 | 4⁴ + 4² + 4¹ + 4⁰ | 10111 |
| 24 | 320 | 4⁴ + 4³ | 11000 |
| 25 | 321 | 4⁴ + 4³ + 4⁰ | 11001 |
| 26 | 324 | 4⁴ + 4³ + 4¹ | 11010 |
| 27 | 325 | 4⁴ + 4³ + 4¹ + 4⁰ | 11011 |
| 28 | 336 | 4⁴ + 4³ + 4² | 11100 |
| 29 | 337 | 4⁴ + 4³ + 4² + 4⁰ | 11101 |
| 30 | 340 | 4⁴ + 4³ + 4² + 4¹ | 11110 |
| 31 | 341 | 4⁴ + 4³ + 4² + 4¹ + 4⁰ | 11111 |
Popolnoma razčlenimo člen 21:
Vidite vzorec? Binarni indeks (111) se neposredno preslika na to, katere potence 4 vključiti. Vsak "1" bit vam pove, da vključite tisto potenco.
Zaporedje raste eksponentno - n-ti člen je približno sorazmeren 4^(log₂(n)). Kaj to praktično pomeni?
Ko se številke povečujejo, postaja zaporedje vse redkejše. Preskakujete vedno več celih števil. Kljub tej redkosti zaporedje vsebuje neskončno število členov - nikoli se ne preneha povečevati.
OEIS A000695 - Moser-de Bruijnova zaporedja. Spletna enciklopedija celoštevilskih zaporedij. Celoviti podatki in lastnosti zaporedja.
De Bruijn, N. G. "O bazah za množico celih števil." Publicationes Mathematicae Debrecen, zvezek 1, 1950, str. 232-242. Temeljni članek, ki določa ključne lastnosti aditivnih baz.
Moser, Leo. "Uporaba generativnih vrst." Mathematics Magazine, zvezek 35, št. 1, 1962, str. 37-38. Zgodnje delo, ki raziskuje generativne funkcije zaporedja.
Stolarsky, Kenneth B. "Vsote potenc in eksponentnih digitalnih vsot, povezanih s parnostjo binomskih koeficientov." SIAM Journal on Applied Mathematics, zvezek 32, št. 4, 1977, str. 717-730. Raziskuje lastnosti digitalnih vsot, povezanih z zaporedji, kot je Moser-de Bruijnovo zaporedje.
Allouche, Jean-Paul, in Jeffrey Shallit. Avtomatska zaporedja: Teorija, aplikacije, posplošitve. Cambridge University Press, 2003. Poglavje obravnava avtomatska zaporedja, vključno s povezavami do Moser-de Bruijnovega zaporedja.
Vsotno proste množice - Wikipedija. Ozadje širšega matematičnega konteksta aditivne teorije števil.
Aditivne baze - Wikipedija. Pregled množic, ki lahko predstavljajo cela števila kot vsote.
Zaporedje ima več aplikacij: raziskave teorije števil, ki raziskujejo aditivne baze, kombinatorično delo na množicah brez vsote, poučevanje računalništva (zlasti za poučevanje bitnih operacij in učinkovitih algoritmov) in analizo matematičnih vzorcev. Je tudi odlično učno orodje za razumevanje medsebojnih povezav različnih številskih sistemov.
Vzemite vsak indeks n, ki se začne z 0, ga pretvorite v binarno obliko, nato zamenjajte vsak "1" bit z ustrezno potenco 4. Na primer, indeks 5 ima binarno predstavitev 101, tako da izračunate 4² + 4⁰ = 16 + 1 = 17. To je 5. člen (štetje od indeksa 0).
Vsako število v zaporedju ima značilno lastnost: njegova predstavitev v bazi 4 vsebuje samo 0 in 1 - nikoli 2 ali 3. To pomeni, da lahko vsak člen zgradite z dodajanjem potenc 4, kjer se vsaka potenca pojavi največ enkrat. Podobno je binarnemu sistemu, vendar z uporabo potenc 4 namesto potenc 2.
Pretvorite svoje število v bazo 4 in poglejte številke. Če vidite samo 0 in 1, je v zaporedju. Če je katerakoli številka 2 ali 3, ni v njem. Na primer, 21 v bazi 4 je 111 (vse 1 in 0), tako da je v zaporedju. Toda 22 v bazi 4 je 112 (vsebuje 2), tako da ni v zaporedju.
n-ti člen M(n) sledi formuli: M(n) = Σ(b_i × 4^i), kjer b_i predstavlja binarne številke n. Preprosto povedano: zapišite n v binarni obliki, nato za vsako pozicijo z 1 dodajte ustrezno potenco 4.
Da, nadaljuje se v neskončnost. V zaporedju Moser-de Bruijn obstaja neskončno število členov. Vendar postaja zaporedje višje, bolj redko - preskakujete vedno več regularnih celih števil med členi zaporedja.
Binarna zaporedja (vsote potenc 2) lahko predstavijo vsako nenegativno celo število - to je namreč naloga binarne predstavitve. Zaporedje Moser-de Bruijn uporablja potence 4 namesto tega, kar ustvarja precej redkejši nabor. Večina celih števil se ne pojavi v zaporedju Moser-de Bruijn.
Leo Moser (1921-1970), avstrijski kanadski matematik, in Nicolaas Govert de Bruijn (1918-2012), nizozemski matematik, sta oba poglobljeno preučevala to zaporedje v šestdesetih letih kot del raziskav aditivne teorije števil. Zaporedje nosi ime po obeh.
Ta generator deluje v celoti v vašem brskalniku - brez namestitve, registracije ali čakanja. Ne glede na to, ali ste študent, ki se uči o številskih sistemih, raziskovalec, ki raziskuje aditivne baze, ali le matematično radoveden, lahko takoj generirate izraze in sami opazujete vzorce. Poskusite generirati različne količine in opazujte, kako zaporedje raste in kateri celi števili so vključeni.
Odkrijte več orodij, ki bi lahko bila koristna za vaš delovni proces