Generera Moser-de Bruijn-sekvenser direkt. Beräkna summor av distinkta 4-potenser med bas-4-representationer som endast använder 0:or och 1:or. Gratis online-verktyg för matematikinlärning och forskning.
Moser-de Bruijn-sekvenser innehåller tal som kan skrivas som summor av distinkta potenser av 4
Moser-de Bruijn-sekvensen består av tal som kan uttryckas som summor av distinkta potenser av 4. Uppkallad efter matematikerna Leo Moser och Nicolaas Govert de Bruijn, börjar sekvensen: 0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85...
Vad gör denna sekvens intressant? När du skriver vilket term som helst i bas 4, kommer du bara att se siffrorna 0 och 1 - aldrig 2 eller 3. Detta innebär att varje tal byggs genom att lägga ihop potenser av 4 (som 4⁰, 4¹, 4², 4³), där varje potens förekommer en gång eller inte alls.
Här är ett praktiskt exempel: Numret 21 förekommer i sekvensen eftersom det är lika med 16 + 4 + 1, vilket är 4² + 4¹ + 4⁰. I bas 4 skrivs detta som "111" - bara 0:or och 1:or. Jämför detta med 22, som skulle behöva en "2:a" i sin bas-4-representation (122), så den klarar inte testet.
Sekvensen dyker upp inom additiv talteori, kombinatorik och forskning om sumfria mängder. Tänk på den som en bas-4-kusin till det binära systemet - istället för potenser av 2 arbetar du med potenser av 4. Detta skapar en mycket glesare sekvens eftersom de flesta heltal hoppas över.
Att använda denna generator är enkelt:
Beräkningarna körs helt i din webbläsare med JavaScript, så det finns ingen fördröjning från servern eller internetberoende—det är snabbt och fungerar offline när sidan har laddats.
Generatorn validerar din inmatning för att förhindra fel:
Varför gränsen på 1000 termer? Även om algoritmen är effektiv kan generering av tusentals termer belasta webbläsarminnet, särskilt på mobila enheter. I praktiken behöver du sällan mer än 100-200 termer för de flesta matematiska analyser eller utbildningsändamål.
Du kan definiera Moser-de Bruijn-sekvensen på tre likvärdiga sätt, var och en som erbjuder olika insikter:
Additiv form (Potenser av 4): Ett tal n tillhör sekvensen när du kan skriva det som: där S är vilken mängd som helst av icke-negativa heltal. Varje potens av 4 kan förekomma en gång eller inte alls—inga upprepningar tillåts.
Bas-4-representation (Enklaste testet): Konvertera ett tal till bas 4. Om du bara ser 0or och 1or (inga 2or eller 3or), så är det i sekvensen. Detta är det snabbaste sättet att kontrollera medlemskap för hand.
Binär korrespondens (Mest användbar för beräkning): För att hitta den n:te termen (med start från n=0): där är de binära siffrorna för n. Översättning: Ta den binära representationen av ditt index, ersätt sedan varje "1"-bit med motsvarande potens av 4.
Låt oss se hur dessa definitioner fungerar:
Metoden med binär korrespondens är det som denna generator använder under huven—den är beräkningsmässigt effektiv eftersom bitoperationer är snabba.
Generatorn använder binär korrespondens eftersom den är snabb och enkel:
Steg-för-steg-process:
Genomarbetat exempel: Hitta den 6:e termen (index 5)
Låt oss beräkna M(5) steg för steg:
Denna metod skalerar väl. För stora index handlar det i princip om bitförskjutning och addition—operationer som moderna processorer hanterar extremt snabbt.
Vill du kontrollera om ett specifikt tal finns i Moser-de Bruijn-sekvensen? Använd bas-4-testet:
Exempel: Finns 85 i sekvensen?
Motexempel: Finns 90 i sekvensen?
Generatorn implementerar detta med hjälp av JavaScript's bitoperatorer, som är inbyggda i språket och mycket optimerade i moderna webbläsare.
Moser-de Bruijn-sekvensen hanterar rena heltal:
Denna exponentiella tillväxt innebär att sekvensen snabbt blir stor. Den 20:e termen är redan 340, och vid den 100:e termen hanterar du tal i miljonklassen.
Undervisning om talsystem: När jag har använt detta i klassrum förstår eleverna baskonverteringar mycket snabbare när de kan leka med Moser-de Bruijn-sekvensen. Den överbryggar klyftan mellan binärt (bas 2) och mer komplexa talsystem. Eleverna ser omedelbart hur förändring av basen påverkar sekvensens täthet.
Förståelse för bitoperationer: Datavetenskap-studenter har nytta av att se den direkta kopplingen mellan binär representation och matematiska sekvenser. Algoritmen visar hur bitmanipulation översätts till verkliga matematiska objekt—inte bara abstrakta operationer.
Kombinatorik och sumfria mängder: Forskare som studerar additiva baser använder sekvenser som denna för att utforska vilka mängder som tillåter unika representationer. Moser-de Bruijn-sekvensen är ett läroboksexempel på en mängd där varje representabel nummer har exakt en representation.
Additiv talteori: Sekvensen hjälper till att undersöka frågor om hur heltal kan sönderdelas i summor. Den är relaterad till problem i Online Encyclopedia of Integer Sequences (OEIS), där den är katalogiserad som A000695.
Algoritmdesign: Generationsalgoritmen visar effektiv sekvenskonstruktion. Du kan generera tusentals termer med minimal beräkningsmässig overhead, vilket gör den användbar för algoritmbenchmarking eller undervisning i effektiva kodmönster.
Mönsterigenkännande uppgifter: När man arbetar med glesa heltalsuppsättningar eller datakompressionsscheman hjälper förståelsen för hur sekvenser som Moser-de Bruijn beter sig till att informera designbeslut om kodningsstrategier.
Om Moser-de Bruijn-sekvensen intresserar dig, erbjuder dessa relaterade sekvenser liknande mönster med olika baser eller begränsningar:
Potenser av 2 (OEIS A000079): 1, 2, 4, 8, 16, 32... Den enklaste additiva basen. Varje potens av 2 visas exakt en gång och bildar byggstenarna för binära tal.
Alla Icke-Negativa Heltal (Binära Summor): 0, 1, 2, 3, 4, 5, 6, 7... När du tillåter vilken summa som helst av distinkta potenser av 2, får du varje möjligt heltal—det är det binära representationssättet.
Summor av Distinkta Potenser av 3 (OEIS A005836): 0, 1, 3, 4, 9, 10, 12, 13... Samma koncept som Moser-de Bruijn, men med potenser av 3 istället för 4. Detta är tal vars bas-3-representation innehåller endast 0:or och 1:or.
Fibbinära Tal (OEIS A003714): 0, 1, 2, 4, 5, 8, 9, 10... Tal vars binära form inte har några på varandra följande 1:or. Kopplat till Fibonacci-talsystem och Zeckendorfs sats.
Stanley-sekvensen: Bas-3-analogen till Moser-de Bruijn—tal med inga 1:or i sin bas-3-representation (endast 0:or och 2:or tillåtna).
Online Encyclopedia of Integer Sequences (OEIS) katalogiserar hundratusentals sekvenser. Sök efter termer som "additiv bas", "sumfri mängd" eller "distinkta potenser" för att hitta relaterade sekvenser. Moser-de Bruijn-sekvensen själv är A000695 i OEIS-databasen.
Leo Moser (1921-1970) och Nicolaas Govert de Bruijn (1918-2012) bidrog båda på ett bestående sätt till matematiken, trots att de kom från olika bakgrunder. Moser, en österrikisk-kanadensisk matematiker, arbetade omfattande inom talteori, kombinatorik och geometri—du kanske känner igen hans namn från Erdős–Moser-ekvationen. De Bruijn, en nederländsk matematiker, lämnade sina spår inom kombinatorik, grafteori och datavetenskap. Hans de Bruijn-sekvenser (skilda från denna) är grundläggande inom kodningsteori och fortfarande vida använda idag.
Deras namngivna sekvens uppstod på 1960-talet under undersökningar av additiv talteori. Matematiker ställde frågan: vilka mängder av heltal låter dig unikt representera andra heltal som summor? Potenser av 4 visade sig vara en sådan mängd, och Moser-de Bruijn-sekvensen fångar alla möjliga summor du kan skapa.
Sekvensen finns inom den bredare studien av additiva baser—mängder av heltal som kan bygga andra heltal genom addition. Vissa baser tillåter unika representationer (som potenser av 4), medan andra inte gör det. Att förstå vilka baser som har vilka egenskaper förblir ett aktivt forskningsområde inom additiv talteori.
Du hittar denna sekvens som A000695 i OEIS, där matematiker har dokumenterat dess kopplingar till binär representation, kvarternära (bas-4) system och kombinatoriska egenskaper. Modern datavetenskap har hittat nya användningsområden för den, särskilt i algoritmer som involverar bitmanipulation och effektiv kodning av glesa datastrukturer.
Vill du implementera Moser-de Bruijn-sekvensens generator själv? Här är effektiva implementationer i populära programmeringsspråk. Varje exempel inkluderar både en sekvens-generator och en medlemskapstestfunktion.
1def moser_de_bruijn(n):
2 """Generera de första n termerna i Moser-de Bruijn-sekvensen."""
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: # Kontrollera om minst signifikanta biten är 1
10 term += power
11 power *= 4
12 temp >>= 1 # Högerförskjutning för att kontrollera nästa bit
13 sequence.append(term)
14 return sequence
15
16# Exempelanvändning:
17terms = moser_de_bruijn(20)
18print("Första 20 termerna i Moser-de Bruijn-sekvensen:")
19print(terms)
20# Utdata: [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 """Kontrollera om ett nummer finns i Moser-de Bruijn-sekvensen."""
24 while num > 0:
25 digit = num % 4
26 if digit > 1:
27 return False
28 num //= 4
29 return True
30
31# Kontrollera om 21 finns i sekvensen
32print(f"Finns 21 i sekvensen? {is_moser_de_bruijn(21)}") # Sant
33print(f"Finns 22 i sekvensen? {is_moser_de_bruijn(22)}") # Falskt
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) { // Kontrollera om minst signifikanta biten är 1
9 term += power;
10 }
11 power *= 4;
12 temp >>= 1; // Högerförskjutning för att kontrollera nästa bit
13 }
14 sequence.push(term);
15 }
16 return sequence;
17}
18
19// Exempelanvändning:
20const terms = moserDeBruijn(20);
21console.log("Första 20 termerna i Moser-de Bruijn-sekvensen:");
22console.log(terms);
23// Utdata: [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// Kontrollera specifika nummer
37console.log(`Finns 21 i sekvensen? ${isMoserDeBruijn(21)}`); // sant
38console.log(`Finns 22 i sekvensen? ${isMoserDeBruijn(22)}`); // falskt
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) { // Kontrollera om minst signifikanta biten är 1
14 term += power;
15 }
16 power *= 4;
17 temp >>= 1; // Högerförskjutning för att kontrollera nästa bit
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("Första 20 termerna i Moser-de Bruijn-sekvensen:");
38 System.out.println(terms);
39
40 System.out.println("Finns 21 i sekvensen? " + isMoserDeBruijn(21)); // sant
41 System.out.println("Finns 22 i sekvensen? " + isMoserDeBruijn(22)); // falskt
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) { // Kontrollera om minst signifikanta biten är 1
12 term += power;
13 }
14 power *= 4;
15 temp >>= 1; // Högerförskjutning för att kontrollera nästa bit
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 << "Första 20 termerna i Moser-de Bruijn-sekvensen:" << std::endl;
36 for (int term : terms) {
37 std::cout << term << " ";
38 }
39 std::cout << std::endl;
40
41 std::cout << "Finns 21 i sekvensen? " << (isMoserDeBruijn(21) ? "sant" : "falskt") << std::endl;
42 std::cout << "Finns 22 i sekvensen? " << (isMoserDeBruijn(22) ? "sant" : "falskt") << std::endl;
43
44 return 0;
45}
46Alla dessa implementationer följer samma mönster: använda bitoperationer för att läsa det binära representationen av ett index, sedan konstruera motsvarande summa av 4-potenser. Medlemskapstestfunktionerna använder bas-4-metoden—kontrollera om siffror är begränsade till 0 och 1.
Prestandamässigt är dessa implementationer mycket effektiva. Tidskomplexiteten är O(n × log n) för att generera n termer, eftersom varje term kräver undersökning av O(log i) bitar. Att kontrollera medlemskap för ett enskilt nummer är O(log N) där N är det nummer som testas.
Tabellen nedan visar de första 32 termerna med fullständiga nedbrytningar. Observera hur bas-4-representationen endast innehåller 0:or och 1:or, och hur nedbrytningen mappar direkt till binära index:
| Index | Term | Nedbrytning | Bas-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 |
Låt oss bryta ner term 21 fullständigt:
Ser du mönstret? Det binära indexet (111) mappar direkt till vilka potenser av 4 som ska inkluderas. Varje "1"-bit talar om för dig att inkludera den potensen.
Sekvensen växer exponentiellt—den n:te termen är ungefär proportionell mot 4^(log₂(n)). Vad innebär detta praktiskt?
Ju större nummer, desto glesare blir sekvensen. Du hoppar över allt fler heltal. Trots denna glesthet innehåller sekvensen oändligt många termer—den slutar aldrig växa.
OEIS A000695 - Moser-de Bruijn-sekvensen. The Online Encyclopedia of Integer Sequences. Omfattande data och egenskaper hos sekvensen.
De Bruijn, N. G. "Om baser för mängden heltal." Publicationes Mathematicae Debrecen, vol. 1, 1950, s. 232-242. Det grundläggande papperet som fastställer nyckelegenskaper hos additiva baser.
Moser, Leo. "En tillämpning av genererande serier." Mathematics Magazine, vol. 35, nr. 1, 1962, s. 37-38. Tidigt arbete som utforskar sekvensens genererande funktioner.
Stolarsky, Kenneth B. "Potens- och exponentiella summor av digitala summor relaterade till binomialkoefficientparitet." SIAM Journal on Applied Mathematics, vol. 32, nr. 4, 1977, s. 717-730. Utforskar digitala sumegenskaper relaterade till sekvenser som Moser-de Bruijn.
Allouche, Jean-Paul, och Jeffrey Shallit. Automatiska sekvenser: Teori, tillämpningar, generaliseringar. Cambridge University Press, 2003. Kapiteltäckning av automatiska sekvenser inklusive kopplingar till Moser-de Bruijn-sekvensen.
Sumfria mängder - Wikipedia. Bakgrund till den bredare matematiska kontexten för additiv talteori.
Additiva baser - Wikipedia. Översikt över mängder som kan representera heltal som summor.
Sekvensen har flera användningsområden: forskning inom talteori som utforskar additiva baser, kombinatoriskt arbete med summafria mängder, datavetenskaplig utbildning (särskilt för att undervisa om bitoperationer och effektiva algoritmer) och matematisk mönsteranalys. Det är också ett utmärkt pedagogiskt verktyg för att förstå hur olika talbaser förhåller sig till varandra.
Ta varje index n från 0, konvertera det till binärt, och ersätt sedan varje "1"-bit med motsvarande potens av 4. Till exempel har index 5 binär representation 101, så du beräknar 4² + 4⁰ = 16 + 1 = 17. Det är den 5:e termen (räknat från index 0).
Varje nummer i sekvensen har en distinktiv egenskap: dess bas-4-representation innehåller endast 0or och 1or—aldrig 2or eller 3or. Detta innebär att du kan bygga varje term genom att addera potenser av 4 där varje potens förekommer högst en gång. Det är som binärt, men med potenser av 4 istället för potenser av 2.
Konvertera ditt nummer till bas 4 och titta på siffrorna. Om du bara ser 0or och 1or finns det i sekvensen. Om någon siffra är 2 eller 3 finns det inte. Exempelvis är 21 i bas 4 111 (alla 1or och 0or), så det finns i sekvensen. Men 22 i bas 4 är 112 (innehåller en 2), så det finns inte.
Den n:te termen M(n) följer denna formel: M(n) = Σ(b_i × 4^i), där b_i representerar de binära siffrorna i n. På vanligt språk: skriv n i binärt, och för varje position med en 1, lägg till motsvarande potens av 4.
Ja, den fortsätter för evigt. Det finns oändligt många termer i Moser-de Bruijn-sekvensen. Men ju högre upp du kommer, desto glesare blir sekvensen—du hoppar över allt fler vanliga heltal mellan sekvensmedlemmar.
Binära sekvenser (summor av potenser av 2) kan representera alla icke-negativa heltal—det är vad binär representation gör. Moser-de Bruijn-sekvensen använder potenser av 4 istället, vilket skapar en mycket glesare mängd. De flesta heltal förekommer inte i Moser-de Bruijn-sekvensen.
Leo Moser (1921-1970), en österrikisk-kanadensisk matematiker, och Nicolaas Govert de Bruijn (1918-2012), en nederländsk matematiker, studerade båda denna sekvens ingående under 1960-talet som en del av forskning inom additiv talteori. Sekvensen bär båda deras namn.
Denna generator körs helt i din webbläsare—ingen installation, ingen registrering, ingen väntan. Oavsett om du är en student som lär dig om talsystem, en forskare som utforskar additiva baser eller bara matematiskt nyfiken, kan du generera termer direkt och se mönstren själv. Prova att generera olika kvantiteter för att observera hur sekvensen växer och vilka heltal som inkluderas.
Upptäck fler verktyg som kan vara användbara för din arbetsflöde