Trenutno generirajte Moser-de Bruijnove sekvence. Izračunajte zbroje različitih potencija broja 4 s prikazom u bazi 4 koristeći samo 0 i 1. Besplatni mrežni alat za matematičko obrazovanje i istraživanje.
Slijedovi Moser-de Bruijn sadržavaju brojeve koji se mogu napisati kao zbroji različitih potencija broja 4
Moser-de Bruijnov niz sastoji se od brojeva koji se mogu izraziti kao zbrovi različitih potencija od 4. Nazvan po matematičarima Leou Moseru i Nicolaasu Goverteu de Bruijnu, niz počinje: 0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85...
Što čini ovaj niz zanimljivim? Kada napišete bilo koji član u bazi 4, vidjet ćete samo znamenke 0 i 1 - nikada 2 ili 3. To znači da je svaki broj izgrađen zbrajanjem potencija od 4 (poput 4⁰, 4¹, 4², 4³), gdje svaka potencija ili postoji jednom ili uopće ne postoji.
Evo praktičnog primjera: Broj 21 pojavljuje se u nizu jer je jednak 16 + 4 + 1, što je 4² + 4¹ + 4⁰. U bazi 4, ovo se piše kao "111" - samo 0 i 1. Usporedite ovo s brojem 22, koji bi zahtijevao "2" u svojoj bazi-4 reprezentaciji (122), pa stoga ne ulazi u niz.
Niz se pojavljuje u aditivnoj teoriji brojeva, kombinatorici i istraživanjima suma slobodnih skupova. Zamislite ga kao bazu-4 sestru binarnom sustavu - umjesto potencija od 2, radite s potencijama od 4. Ovo stvara puno rjeđi niz budući da se preskače većina cijelih brojeva.
Korištenje ovog generatora je jednostavno:
Izračuni se izvode u potpunosti u vašem pregledniku pomoću JavaScripta, tako da nema kašnjenja poslužitelja ili ovisnosti o internetu - brzo je i radi izvanmrežno nakon učitavanja stranice.
Generator provjerava vaš unos kako bi spriječio pogreške:
Zašto ograničenje od 1000 članova? Iako je algoritam učinkovit, generiranje tisuća članova može opteretiti memoriju preglednika, posebno na mobilnim uređajima. U praksi, rijetko ćete trebati više od 100-200 članova za većinu matematičkih analiza ili obrazovnih svrha.
Moser-de Bruijn slijed možete definirati na tri ekvivalentna načina, od kojih svaki nudi različite uvide:
Aditivni oblik (Potencije od 4): Broj n pripada slijedu kada ga možete napisati kao: gdje je S bilo koji skup nezaricnih cijelih brojeva. Svaka potencija od 4 može se pojaviti jednom ili uopće ne - ponavljanja nisu dopuštena.
Reprezentacija u bazi 4 (Najjednostavniji test): Pretvorite broj u bazu 4. Ako vidite samo 0 i 1 (bez 2 i 3), broj je u slijedu. Ovo je najbrži način za ručnu provjeru članstva.
Binarna korespondencija (Najpogodnija za računanje): Da biste pronašli n-ti član (počevši od n=0): gdje su binarne znamenke od n. Prijevod: Uzmite binarnu reprezentaciju svog indeksa, zatim zamijenite svaki "1" bit odgovarajućom potencijom od 4.
Pogledajmo kako ove definicije funkcioniraju:
Metoda binarne korespondencije je ono što ovaj generator koristi ispod poklopca - computacijski je učinkovita jer su bitovske operacije brze.
Generator koristi binarnu korespondenciju jer je brz i jednostavan:
Korak po korak:
Primjer izračuna: Pronalaženje 6. člana (indeks 5)
Izračunajmo M(5) korak po korak:
Ova metoda dobro skalira. Za velike indekse, suštinski radite pomicanje bitova i zbrajanje — operacije koje moderne procesorske jedinice izvode izuzetno brzo.
Želite provjeriti pripada li specifičan broj Moser-de Bruijnovoj sekvenci? Koristite test baze 4:
Primjer: Je li 85 u sekvenci?
Protuprimjer: Je li 90 u sekvenci?
Generator implementira ovo koristeći JavaScript-ove bitovne operatore, koji su izvorni jeziku i visoko optimizirani u modernim preglednicima.
Moser-de Bruijnova sekvenca bavi se čistim cijelim brojevima:
Ovaj eksponencijalni rast znači da sekvenca brzo postaje velika. 20. član je već 340, a 100. član uključuje brojeve u milionima.
Poučavanje brojnih sustava: Kada sam ovo koristio u učionicama, učenici brže shvaćaju pretvorbe baza kada mogu eksperimentirati s Moser-de Bruijnovim nizom. On premošćuje jaz između binarnog (baza 2) i složenijih numeričkih sustava. Učenici odmah vide kako promjena baze mijenja gustoću niza.
Razumijevanje bitnih operacija: Studenti računalnih znanosti koristi od izravne veze između binarne reprezentacije i matematičkih nizova. Algoritam pokazuje kako se manipulacija bitovima prevodi u stvarne matematičke objekte - a ne samo apstraktne operacije.
Kombinatorika i suma-besplatni skupovi: Istraživači koji proučavaju aditivne baze koriste nizove poput ovog za istraživanje skupova koji omogućavaju jedinstvene reprezentacije. Moser-de Bruijnov niz je udžbenički primjer skupa gdje svaki predstavljivi broj ima točno jednu reprezentaciju.
Aditivna teorija brojeva: Niz pomaže u istraživanju pitanja o tome kako se cijeli brojevi mogu razložiti u zbroje. Povezan je s problemima u Online enciklopediji nizova cijelih brojeva (OEIS), gdje je katalogiziran kao A000695.
Dizajn algoritama: Algoritam generiranja prikazuje učinkovitu izgradnju niza. Možete generirati tisuće članova uz minimalne računalne troškove, čineći ga korisnim za usporedbu algoritama ili poučavanje učinkovitih programskih uzoraka.
Zadaci prepoznavanja uzoraka: Kada radite s rijetkim skupovima cijelih brojeva ili shemama kompresije podataka, razumijevanje ponašanja nizova poput Moser-de Bruijnovog pomaže u donošenju odluka o strategijama kodiranja.
Ako vas zanima Moser-de Bruijnova sekvenca, ove srodne sekvence nude slične uzorke s različitim bazama ili ograničenjima:
Potencije broja 2 (OEIS A000079): 1, 2, 4, 8, 16, 32... Najjednostavnija aditivna baza. Svaka potencija broja 2 pojavljuje se točno jednom, formirajući osnovne elemente binarnih brojeva.
Svi nenegativni cijeli brojevi (Binarne sume): 0, 1, 2, 3, 4, 5, 6, 7... Kada dozvolite bilo koju sumu različitih potencija broja 2, dobivate svaki mogući cijeli broj—to čini binarna reprezentacija.
Sume različitih potencija broja 3 (OEIS A005836): 0, 1, 3, 4, 9, 10, 12, 13... Isti koncept kao Moser-de Bruijnova sekvenca, ali koristeći potencije broja 3 umjesto 4. Ovo su brojevi čija base-3 reprezentacija sadržava samo 0 i 1.
Fibbinarni brojevi (OEIS A003714): 0, 1, 2, 4, 5, 8, 9, 10... Brojevi čiji binarni oblik nema uzastopnih 1. Povezani s Fibonaccijevim sustavom brojeva i Zeckendorfovom teoremom.
Stanleyeva sekvenca: Base-3 analog Moser-de Bruijnove sekvence—brojevi koji nemaju 1 u svojoj base-3 reprezentaciji (dozvoljeni su samo 0 i 2).
Online enciklopedija cijelih brojeva (OEIS) katalogizira stotine tisuća sekvenci. Pretražite termine poput "aditivna baza", "suma bez skupa" ili "različite potencije" da biste pronašli srodne sekvence. Moser-de Bruijnova sekvenca sama je A000695 u OEIS bazi podataka.
Leo Moser (1921-1970) i Nicolaas Govert de Bruijn (1918-2012) obojica su dali trajan doprinos matematici, premda su dolazili iz različitih pozadina. Moser, austrijski-kanadski matematičar, opsežno je radio na teoriji brojeva, kombinatorici i geometriji - možda ćete prepoznati njegovo ime iz Erdős–Moserovog izraza. De Bruijn, nizozemski matematičar, ostavio je trag u kombinatorici, teoriji grafova i računalnoj znanosti. Njegovi de Bruijnovi nizovi (različiti od ovog) temeljni su u teoriji kodiranja i još uvijek se široko koriste danas.
Njihov imenski slijed pojavio se 1960-ih tijekom istraživanja aditivne teorije brojeva. Matematičari su postavljali pitanje: koji skupovi cijelih brojeva omogućavaju jedinstveno predstavljanje drugih cijelih brojeva kao zbroja? Potencije broja 4 pokazale su se kao jedan takav skup, a Moser-de Bruijnov slijed obuhvaća sve moguće zbroje koje možete napraviti.
Slijed se nalazi unutar šireg proučavanja aditivnih baza - skupova cijelih brojeva koji se mogu izgraditi kroz zbrajanje. Neke baze dopuštaju jedinstvene reprezentacije (poput potencija broja 4), dok druge ne. Razumijevanje svojstava različitih baza i dalje je aktivno istraživačko područje u aditivnoj teoriji brojeva.
Ovaj slijed možete pronaći kao A000695 u OEIS-u, gdje su matematičari dokumentirali njegove veze s binarnom reprezentacijom, kvarternim (base-4) sustavima i kombinatornim svojstvima. Moderna računalna znanost pronašla je nove primjene za njega, posebice u algoritmima koji uključuju manipulaciju bitova i učinkovito kodiranje rijetkih podatkovnih struktura.
Želite li sami implementirati generator slijeda Moser-de Bruijn? Evo učinkovitih implementacija u popularnim programskim jezicima. Svaki primjer uključuje generator slijeda i funkciju za testiranje članstva.
1def moser_de_bruijn(n):
2 """Generiraj prvih n članova slijeda 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: # Provjeri je li najmanje značajan bit 1
10 term += power
11 power *= 4
12 temp >>= 1 # Desni pomak za provjeru sljedećeg bita
13 sequence.append(term)
14 return sequence
15
16# Primjer upotrebe:
17terms = moser_de_bruijn(20)
18print("Prvih 20 članova slijeda Moser-de Bruijn:")
19print(terms)
20# Izlaz: [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 """Provjeri je li broj u slijedu 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# Provjeri je li 21 u slijedu
32print(f"Je li 21 u slijedu? {is_moser_de_bruijn(21)}") # True
33print(f"Je li 22 u slijedu? {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) { // Provjeri je li najmanje značajan bit 1
9 term += power;
10 }
11 power *= 4;
12 temp >>= 1; // Desni pomak za provjeru sljedećeg bita
13 }
14 sequence.push(term);
15 }
16 return sequence;
17}
18
19// Primjer upotrebe:
20const terms = moserDeBruijn(20);
21console.log("Prvih 20 članova slijeda Moser-de Bruijn:");
22console.log(terms);
23// Izlaz: [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// Provjeri specifične brojeve
37console.log(`Je li 21 u slijedu? ${isMoserDeBruijn(21)}`); // true
38console.log(`Je li 22 u slijedu? ${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) { // Provjeri je li najmanje značajan bit 1
14 term += power;
15 }
16 power *= 4;
17 temp >>= 1; // Desni pomak za provjeru sljedećeg 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 članova slijeda Moser-de Bruijn:");
38 System.out.println(terms);
39
40 System.out.println("Je li 21 u slijedu? " + isMoserDeBruijn(21)); // true
41 System.out.println("Je li 22 u slijedu? " + 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) { // Provjeri je li najmanje značajan bit 1
12 term += power;
13 }
14 power *= 4;
15 temp >>= 1; // Desni pomak za provjeru sljedećeg 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 članova slijeda 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 li 21 u slijedu? " << (isMoserDeBruijn(21) ? "true" : "false") << std::endl;
42 std::cout << "Je li 22 u slijedu? " << (isMoserDeBruijn(22) ? "true" : "false") << std::endl;
43
44 return 0;
45}
46Sve ove implementacije slijede isti uzorak: koriste bitovne operacije za čitanje binarne reprezentacije indeksa, a zatim konstruiraju odgovarajući zbroj potencija broja 4. Funkcije za testiranje članstva koriste pristup baze 4 - provjeravaju je li znamenke ograničene na 0 i 1.
S aspekta performansi, ove implementacije su izuzetno učinkovite. Vremenska složenost za generiranje n članova je O(n × log n), jer svaki član zahtijeva pregledavanje O(log i) bitova. Provjera članstva za jedan broj je O(log N), gdje je N broj koji se testira.
Tablica ispod prikazuje prvih 32 članova s potpunim razlaganjima. Primijetite kako base-4 reprezentacija sadržava samo 0 i 1, i kako dekompozicija izravno odgovara binarnim indeksima:
| Indeks | Član | Dekompozicija | Base-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 |
Razložimo potpuno član 21:
Vidite li uzorak? Binarni indeks (111) izravno mapira koje potencije 4 uključiti. Svaki "1" bit govori vam da uključite tu potenciju.
Niz eksponencijalno raste — n-ti član je otprilike proporcionalan 4^(log₂(n)). Što to praktično znači?
Kako brojevi postaju veći, niz postaje sve rjeđi. Preskačete sve više i više cijelih brojeva. Unatoč ovoj rjeđoj strukturi, niz sadržava beskonačno mnogo članova — nikada ne prestaje rasti.
OEIS A000695 - Moser-de Bruijn sekvenca. Online enciklopedija cijelih brojeva. Sveobuhvatni podaci i svojstva sekvence.
De Bruijn, N. G. "O bazama skupa cijelih brojeva." Publicationes Mathematicae Debrecen, sv. 1, 1950, str. 232-242. Temeljni rad koji uspostavlja ključna svojstva aditivnih baza.
Moser, Leo. "Primjena generativnih serija." Mathematics Magazine, sv. 35, br. 1, 1962, str. 37-38. Rani rad koji istražuje generativne funkcije sekvence.
Stolarsky, Kenneth B. "Sume potencija i eksponencijalnih digitalnih suma povezanih s paritetom binomnih koeficijenata." SIAM Journal on Applied Mathematics, sv. 32, br. 4, 1977, str. 717-730. Istražuje svojstva digitalnih suma povezanih sa sekvencama poput Moser-de Bruijn.
Allouche, Jean-Paul, i Jeffrey Shallit. Automatske sekvence: Teorija, primjene, generalizacije. Cambridge University Press, 2003. Poglavlje koje pokriva automatske sekvence uključujući veze s Moser-de Bruijn sekvencom.
Suma-besplatni skupovi - Wikipedia. Pozadina šireg matematičkog konteksta aditivne teorije brojeva.
Aditivne baze - Wikipedia. Pregled skupova koji mogu predstavljati cijele brojeve kao sume.
Slijed ima nekoliko primjena: istraživanje teorije brojeva koji istražuju aditivne baze, kombinatorički rad na skupovima bez zbroja, obrazovanje u računalnoj znanosti (posebno za poučavanje bitnih operacija i učinkovitih algoritama) i analizu matematičkih uzoraka. Također je odlično nastavno pomagalo za razumijevanje kako se različite brojne baze međusobno odnose.
Uzmite svaki indeks n počevši od 0, pretvorite ga u binarni zapis, zatim zamijenite svaki "1" bit odgovarajućom potencijom broja 4. Na primjer, indeks 5 ima binarni zapis 101, pa izračunate 4² + 4⁰ = 16 + 1 = 17. To je 5. član (računajući od indeksa 0).
Svaki broj u slijedu ima svojstveno obilježje: njegov zapis u bazi 4 sadržava samo 0 i 1 - nikada 2 ili 3. To znači da možete izgraditi svaki član dodavanjem potencija broja 4 gdje se svaka potencija pojavljuje najviše jednom. Poput binarnog zapisa, ali koristeći potencije broja 4 umjesto potencija broja 2.
Pretvorite broj u bazu 4 i pogledajte znamenke. Ako vidite samo 0 i 1, broj je u slijedu. Ako je bilo koja znamenka 2 ili 3, nije. Na primjer, 21 u bazi 4 je 111 (sve 1 i 0), pa je u slijedu. Ali 22 u bazi 4 je 112 (sadržava 2), pa nije u slijedu.
n-ti član M(n) slijedi ovu formulu: M(n) = Σ(b_i × 4^i), gdje b_i predstavlja binarne znamenke broja n. Jednostavnim jezikom: napišite n u binarnom zapisu, zatim za svaku poziciju s 1 dodajte odgovarajuću potenciju broja 4.
Da, nastavlja se zauvijek. Postoji beskonačno mnogo članova u slijedu Moser-de Bruijn. Međutim, što idete više, slijed postaje sve rjeđi - preskačete sve više regularnih cijelih brojeva između članova slijeda.
Binarni slijedovi (zbroj potencija broja 2) mogu predstavljati svaki necijeli broj - to radi binarna reprezentacija. Slijed Moser-de Bruijn koristi potencije broja 4 umjesto toga, što stvara puno rjeđi skup. Većina cijelih brojeva ne pojavljuje se u slijedu Moser-de Bruijn.
Leo Moser (1921-1970), austrijski kanadski matematičar, i Nicolaas Govert de Bruijn (1918-2012), nizozemski matematičar, obojica su dubinski proučavali ovaj slijed tijekom 1960-ih kao dio istraživanja aditivne teorije brojeva. Slijed nosi njihova imena.
Ovaj generator radi u potpunosti u vašem pregledniku - bez instalacije, bez registracije, bez čekanja. Bez obzira jeste li student koji uči o brojevnim sustavima, istraživač koji istražuje aditivne baze ili jednostavno matematički radoznali, možete trenutno generirati termine i sami vidjeti obrasce. Pokušajte generirati različite količine kako biste promatrali kako slijed raste i koji se cijeli brojevi uključuju.
Otkrijte više alata koji bi mogli biti korisni za vaš radni proces