Moser-de Bruijn sekos generatorius | Ketvirtųjų laipsnių skaičiuotuvas

Kas yra Moser-de Bruijn seka?

Moser-de Bruijn seka susideda iš skaičių, kurie gali būti išreikšti kaip skirtingų 4-ųjų laipsnių sumos. Pavadinta matematikų Leo Moser ir Nicolaas Govert de Bruijn garbei, seka prasideda: 0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85...

Kas daro šią seką įdomią? Kai užrašote bet kurį narį 4-ine sistema, matysite tik skaitmenis 0 ir 1 - niekada 2 ar 3. Tai reiškia, kad kiekvienas skaičius sudaromas sudedant 4-ųjų laipsnių (pvz., 4⁰, 4¹, 4², 4³) vertes, kur kiekvienas laipsnis pasirodo vieną kartą arba visai nepasirodo.

Štai praktinis pavyzdys: Skaičius 21 atsiranda sekoje, nes lygus 16 + 4 + 1, kas yra 4² + 4¹ + 4⁰. 4-ine sistemoje tai užrašoma kaip „111" - tik 0 ir 1. Palyginkite su 22, kuriam reikėtų „2" jo 4-inėje reprezentacijoje (122), todėl jis neįtraukiamas.

Seka pasirodo sudėtinėje skaičių teorijoje, kombinatorikoje ir tyrimuose apie sumų laisvas aibes. Galvokite apie ją kaip 4-inę dvejetainės sistemos giminaitę - vietoj 2-ųjų laipsnių, dirbate su 4-ųjų laipsniais. Tai sukuria daug retesnę seką, kadangi dauguma sveikųjų skaičių yra praleisti.

Kaip naudoti Moser-de Bruijn sekos generatorių

Naudojimasis šiuo generatoriumi yra paprastas:

1. Įveskite, kiek narių norite gauti (jei paliksite tuščią, numatytasis skaičius bus 20)
2. Spustelėkite "Generuoti", kad apskaičiuotumėte seką
3. Jūsų rezultatai iš karto pasirodys sąraše žemiau
4. Norite kitokių skaičių? Tiesiog pakeiskite įvestį ir generuokite dar kartą

Skaičiavimai vykdomi visiškai jūsų naršyklėje naudojant JavaScript, todėl nėra serverio delsos ar interneto priklausomybės - tai greita ir veikia neprisijungus, kai puslapis užsikrauna.

Įvesties tikrinimas ir apribojimai

Generatorius tikrina jūsų įvestį, kad išvengtų klaidų:

• Turi būti teigiamas sveikas skaičius (be dešimtainių ar neigiamų verčių)
• Daugiausiai 1000 narių, kad būtų išvengta naršyklės lėtėjimo
• Netinkamos skaitinės įvestys sukelia klaidos pranešimą
• Jei paliksite tuščią, pagal numatytuosius nustatymus gausite 20 narių

Kodėl 1000 narių riba? Nors algoritmas yra efektyvus, tūkstančių narių generavimas gali apkrauti naršyklės atmintį, ypač mobiliuosiuose įrenginiuose. Praktikoje jums retai prireiks daugiau nei 100-200 narių daugumai matematinių analizių ar mokomųjų tikslų.

Moser-de Bruijn sekos formulės supratimas

Moser-de Bruijn seką galima apibrėžti trimis lygiavertėmis formomis, kiekviena siūlanti skirtingus įžvalgas:

Trys sekos apibrėžimo būdai

Sudėtinė forma (4-ių laipsniai): Skaičius n priklauso sekai, kai jį galima užrašyti taip: $n = \sum_{i \in S} 4^i$ kur S yra bet koks neneigiamų sveikųjų skaičių rinkinys. Kiekvienas 4-ojo laipsnio skaičius gali pasirodyti vieną kartą arba visai nepasirodyti - kartotės neleidžiamos.

Bazės-4 reprezentacija (Paprasčiausias testas): Konvertuokite skaičių į 4-inę sistemą. Jei matote tik 0 ir 1 (be 2 ir 3), jis priklauso sekai. Tai greičiausias būdas patikrinti priklausymą ranka.

Dvejetainė korespondencija (Naudingiausias skaičiavimams): Norėdami rasti n-ąjį narį (pradedant nuo n=0): $M(n) = \sum_{i=0}^{k} b_i \cdot 4^i$ kur $b_i$ yra dvejetainiai indekso skaitmenys. Kitaip tariant: paimkite dvejetainę savo indekso reprezentaciją, tada kiekvieną "1" bitą pakeiskite atitinkamu 4-ojo laipsnio skaičiumi.

Veikiančios pavyzdžiai

Pažiūrėkime, kaip šie apibrėžimai veikia:

• n = 0 (dvejetainis: 0) → M(0) = 0
• n = 1 (dvejetainis: 1) → M(1) = 4⁰ = 1
• n = 2 (dvejetainis: 10) → M(2) = 4¹ = 4
• n = 3 (dvejetainis: 11) → M(3) = 4¹ + 4⁰ = 5
• n = 5 (dvejetainis: 101) → M(5) = 4² + 4⁰ = 17

Dvejetainės korespondencijos metodas yra tai, ką šis generatorius naudoja viduje - jis yra skaičiavimo požiūriu efektyvus, nes bitinės operacijos yra greitos.

Moser-de Bruijn sekos skaičiavimas

Generatoriaus algoritmas

Generatorius naudoja dvejetainę korespondenciją, nes tai greita ir paprasta:

Žingsnis po žingsnio:

1. Ciklas per kiekvieną indeksą i nuo 0 iki n-1 (n yra jūsų pageidaujamų narių skaičius)
2. Indeksui i, pažvelkite į jo dvejetainę reprezentaciją
3. Kiekvienam "1" bitui pozicijoje j, pridėkite 4^j prie einamosios sumos
4. Ta suma tampa i-uoju nariu

Praktinis pavyzdys: 6-ojo nario (indeksas 5) radimas

Apskaičiuokime M(5) žingsnis po žingsnio:

• Indeksas 5 dvejetainiu pavidalu: 101
• Bitas 0 (dešiniausiasis) = 1 → pridėti 4⁰ = 1
• Bitas 1 (vidurinysis) = 0 → nieko nepridėti
• Bitas 2 (kairiausiasis) = 1 → pridėti 4² = 16
• Galutinis rezultatas: 1 + 16 = 17

Šis metodas gerai plečiasi. Dideliems indeksams, iš esmės atliekate bitų postūmį ir sudėtį — operacijas, kurias šiuolaikiniai procesoriai apdoroja nepaprastai greitai.

Patikrinimas, ar skaičius priklauso sekai

Norite patikrinti, ar konkretus skaičius yra Moser-de Bruijn sekoje? Naudokite base-4 testą:

1. Konvertuokite savo skaičių į base-4
2. Peržiūrėkite skaitmenis — ar matote tik 0 ir 1?
3. Jei taip, jis yra sekoje. Jei pamatysite 2 ar 3, jis nėra sekoje.

Pavyzdys: Ar 85 yra sekoje?

• 85 base-4: 1111 (tai 64 + 16 + 4 + 1)
• Turi tik 1 ir 0 → Taip, 85 yra sekoje

Priešingas pavyzdys: Ar 90 yra sekoje?

• 90 base-4: 1122
• Turi skaitmenį 2 → Ne, 90 nėra sekoje

Generatorius tai įgyvendina naudojant JavaScript bitinių operatorių, kurie yra gimtieji kalbai ir labai optimizuoti šiuolaikinėse naršyklėse.

O kaip dėl vienetų ir tikslumo?

Moser-de Bruijn seka užsiima grynaisiais sveikaisiais skaičiais:

• Visi nariai yra neneigiami sveikieji skaičiai (0, 1, 4, 5, 16 ir t.t.)
• Jokių vienetų, dešimtainių ar apvalinimo
• Rezultatai matematiškai tikslūs — kiekvieną kartą gaunate tiksliai sveikuosius skaičius
• Augimas eksponentinis: n-asis narys gali pasiekti iki maždaug 4^(⌊log₂(n)⌋+1) - 1

Šis eksponentinis augimas reiškia, kad seka greitai tampa didele. 20-asis narys jau yra 340, o 100-asis narys apima skaičius milijonais.

Realaus pasaulio taikymai ir naudojimo atvejai

Švietimas ir mokymasis

Skaičių sistemų mokymas: Kai naudojau tai klasėse, studentai greičiau supranta bazių konvertavimą, kai gali žaisti su Moser-de Bruijn seka. Ji suteikia tiltą tarp dvejetainės (2 bazės) ir sudėtingesnių skaitinių sistemų. Studentai iš karto mato, kaip bazės keitimas keičia sekos tankį.

Bitinių operacijų supratimas: Informatikos studentams naudinga matyti tiesioginį ryšį tarp dvejetainės reprezentacijos ir matematinių sekų. Algoritmas parodo, kaip bitų manipuliavimas verčiasi į realius matematinius objektus — ne tik abstrakčias operacijas.

Tyrimai ir analizė

Kombinatorika ir sumų laisvos aibės: Tyrėjai, studijuojantys sudėtinius pagrindus, naudoja tokias sekas, kad ištirtų, kurios aibės leidžia unikalias reprezentacijas. Moser-de Bruijn seka yra vadovėlinis pavyzdys aibės, kurioje kiekvienas reprezentuojamas skaičius turi būtent vieną reprezentaciją.

Sudėtinė skaičių teorija: Seka padeda tirti klausimus apie tai, kaip sveikieji skaičiai gali būti išskaidyti į sumas. Ji susijusi su problemomis Interneto sveikųjų skaičių sekų enciklopedijoje (OEIS), kur ji katalogizuota kaip A000695.

Praktinis programavimas

Algoritmo projektavimas: Generavimo algoritmas parodo efektyvų sekos konstravimą. Galite generuoti tūkstančius narių su minimaliais skaičiavimų kaštais, kas daro jį naudingu algoritmo lyginimui ar efektyvių kodo šablonų mokymui.

Šablonų atpažinimo užduotys: Dirbant su retomis sveikųjų skaičių aibėmis ar duomenų suspaudimo schemomis, supratimas, kaip elgiasi tokios sekos kaip Moser-de Bruijn, padeda priimti sprendimus apie kodavimo strategijas.

Susijusios Matematinės Sekos

Jei jus domina Moser-de Bruijn seka, šios susijusios sekos siūlo panašius dėsningumus su skirtingomis bazėmis ar apribojimais:

Tiesioginiai Giminaičiai

2 laipsnio skaičiai (OEIS A000079): 1, 2, 4, 8, 16, 32... Paprasčiausia sudėtinė bazė. Kiekvienas 2 laipsnio skaičius pasirodo lygiai vieną kartą, sudarydamas dvejetainių skaičių statybos blokus.

Visi Neneigiami Sveikieji Skaičiai (Dvejetainės Sumos): 0, 1, 2, 3, 4, 5, 6, 7... Kai leidžiate bet kokią skirtingų 2 laipsnio skaičių sumą, gaunate visus įmanomus sveikuosius skaičius—tai tai, ką daro dvejetainė reprezentacija.

Skirtingų 3 laipsnio Skaičių Sumos (OEIS A005836): 0, 1, 3, 4, 9, 10, 12, 13... Tas pats principas kaip Moser-de Bruijn, tik naudojant 3 laipsnio skaičius vietoj 4. Tai skaičiai, kurių trejetas bazėje reprezentacijoje yra tik 0 ir 1.

Įdomios Variacijos

Fibbiniai Skaičiai (OEIS A003714): 0, 1, 2, 4, 5, 8, 9, 10... Skaičiai, kurių dvejetainėje formoje nėra gretimų 1. Susiję su Fibonacci skaičių sistemomis ir Zeckendorf teorema.

Stenlio Seka: Moser-de Bruijn analogas trejeto bazėje—skaičiai, kurių trejeto bazėje nėra 1 (leidžiami tik 0 ir 2).

Kur Sužinoti Daugiau

Interneto Sveikųjų Skaičių Sekų Enciklopedija (OEIS) katalogizuoja šimtus tūkstančių sekų. Ieškokite terminų kaip „sudėtinė bazė", „sumų laisvas rinkinys" ar „skirtingi laipsniai", kad rastumėte susijusias sekas. Pati Moser-de Bruijn seka yra A000695 OEIS duomenų bazėje.

Istorinė Apžvalga

Matematikai, Stovintys už Sekos

Leo Moser (1921-1970) ir Nicolaas Govert de Bruijn (1918-2012) abu padarė ilgalaikį indėlį į matematiką, nors ir kilę iš skirtingų aplinkų. Moser, austrų-kanadietis matematikas, daug dirbo skaičių teorijos, kombinatorikos ir geometrijos srityse - jūs galbūt atpažinsite jo vardą iš Erdős–Moser lygties. De Bruijn, olandų matematikas, paliko savo pėdsaką kombinatorikoje, grafų teorijoje ir informatikoje. Jo de Bruijn sekos (skirtingos nuo šios) yra fundamentalios kodavimo teorijoje ir iki šiol plačiai naudojamos.

Jų vardu pavadinta seka atsirado 1960-aisiais, tiriant sudėtinę skaičių teoriją. Matematikai klausė: kokios skaičių aibės leidžia unikaliai atstovauti kitus skaičius kaip sumas? Ketvirtojo laipsnio laipsniai pasirodė esantys viena tokių aibių, o Moser-de Bruijn seka apima visas galimas sumas, kurias galima sudaryti.

Kodėl Tai Svarbu

Seka yra sudėtinių bazių studijų dalis - skaičių aibių, kurios gali kurti kitus skaičius per sudėtį. Kai kurios bazės leidžia unikalius atstovavimus (kaip ketvirtojo laipsnio laipsniai), o kitos - ne. Supratimas, kokios bazės turi kokias savybes, išlieka aktyvia tyrimų sritimi sudėtinėje skaičių teorijoje.

Šią seką rasite A000695 OEIS, kur matematikai dokumentavo jos ryšius su dvejetaine reprezentacija, ketvertainėmis (bazė-4) sistemomis ir kombinatorinėmis savybėmis. Šiuolaikinė informatika rado naujų jos panaudojimų, ypač algoritmuose, susijusiuose su bitų manipuliavimu ir efektyviu retų duomenų struktūrų kodavimu.

Kodo įgyvendinimo pavyzdžiai

Norite patys realizuoti Moser-de Bruijn sekos generatorių? Štai efektyvūs įgyvendinimai populiariomis programavimo kalbomis. Kiekvienas pavyzdys apima tiek sekos generatorių, tiek narystės patikrinimo funkciją.

1def moser_de_bruijn(n):
2    """Sugeneruoti pirmus n Moser-de Bruijn sekos narių."""
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:  # Patikrinti, ar mažiausias reikšmingasis bitas yra 1
10                term += power
11            power *= 4
12            temp >>= 1  # Pastumti į dešinę, kad patikrinti kitą bitą
13        sequence.append(term)
14    return sequence
15
16# Naudojimo pavyzdys:
17terms = moser_de_bruijn(20)
18print("Pirmieji 20 Moser-de Bruijn sekos narių:")
19print(terms)
20# Išvestis: [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    """Patikrinti, ar skaičius priklauso Moser-de Bruijn sekai."""
24    while num > 0:
25        digit = num % 4
26        if digit > 1:
27            return False
28        num //= 4
29    return True
30
31# Patikrinti, ar 21 yra sekoje
32print(f"Ar 21 yra sekoje? {is_moser_de_bruijn(21)}")  # True
33print(f"Ar 22 yra sekoje? {is_moser_de_bruijn(22)}")  # False
34

1function 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) {  // Patikrinti, ar mažiausias reikšmingasis bitas yra 1
9        term += power;
10      }
11      power *= 4;
12      temp >>= 1;  // Pastumti į dešinę, kad patikrinti kitą bitą
13    }
14    sequence.push(term);
15  }
16  return sequence;
17}
18
19// Naudojimo pavyzdys:
20const terms = moserDeBruijn(20);
21console.log("Pirmieji 20 Moser-de Bruijn sekos narių:");
22console.log(terms);
23// Išvestis: [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// Patikrinti konkrečius skaičius
37console.log(`Ar 21 yra sekoje? ${isMoserDeBruijn(21)}`);  // true
38console.log(`Ar 22 yra sekoje? ${isMoserDeBruijn(22)}`);  // false
39

1import 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) {  // Patikrinti, ar mažiausias reikšmingasis bitas yra 1
14                    term += power;
15                }
16                power *= 4;
17                temp >>= 1;  // Pastumti į dešinę, kad patikrinti kitą 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("Pirmieji 20 Moser-de Bruijn sekos narių:");
38        System.out.println(terms);
39        
40        System.out.println("Ar 21 yra sekoje? " + isMoserDeBruijn(21));  // true
41        System.out.println("Ar 22 yra sekoje? " + isMoserDeBruijn(22));  // false
42    }
43}
44

1#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) {  // Patikrinti, ar mažiausias reikšmingasis bitas yra 1
12                term += power;
13            }
14            power *= 4;
15            temp >>= 1;  // Pastumti į dešinę, kad patikrinti kitą 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 << "Pirmieji 20 Moser-de Bruijn sekos narių:" << std::endl;
36    for (int term : terms) {
37        std::cout << term << " ";
38    }
39    std::cout << std::endl;
40    
41    std::cout << "Ar 21 yra sekoje? " << (isMoserDeBruijn(21) ? "taip" : "ne") << std::endl;
42    std::cout << "Ar 22 yra sekoje? " << (isMoserDeBruijn(22) ? "taip" : "ne") << std::endl;
43    
44    return 0;
45}
46

Pagrindinės realizacijos įžvalgos

Visi šie įgyvendinimai laikosi tos pačios schemos: naudoti bitų operacijas indekso dvejetainei reprezentacijai skaityti, tada konstruoti atitinkamą 4-ųjų laipsnių sumą. Narystės patikrinimo funkcijos naudoja bazės 4 metodą - tikrinant, ar skaitmenys yra ribojami 0 ir 1.

Našumo požiūriu, šios realizacijos yra labai efektyvios. Laiko sudėtingumas yra O(n × log n) generuojant n narių, kadangi kiekvienam nariui reikia ištirti O(log i) bitų. Vieno skaičiaus narystės patikrinimas yra O(log N), kur N yra tikrinamas skaičius.

Išsamūs Skaitiniai Pavyzdžiai

Lentelė žemiau rodo pirmuosius 32 narius su išsamiais išskaidymais. Pastebėkite, kaip bazės-4 atvaizdavimas turi tik 0 ir 1, ir kaip išskaidymas tiesiogiai atitinka dvejetainius indeksus:

Išsamus Žvilgsnis į 21 Narį

Išskaidykime 21 narį visiškai:

• Dešimtainis skaičius: 21
• Bazės-4 atvaizdavimas: 111 (naudoja tik 0 ir 1 ✓)
• Seka indekse: 7
• Dvejetainis indeksas: 111 (dvejetainis 7)
• Išskaidymas: 21 = 16 + 4 + 1 = 4² + 4¹ + 4⁰

Matote dėsningumą? Dvejetainis indeksas (111) tiesiogiai nurodo, kurias 4 laipsnio reikšmes įtraukti. Kiekvienas "1" bitas pasako, kurią laipsnio reikšmę įtraukti.

Augimo Modelio Stebėjimas

Seka auga eksponentiškai—n-tasis narys maždaug proporcingas 4^(log₂(n)). Ką tai reiškia praktiškai?

• Iki 10 nario pasiekiate 68
• Iki 20 nario pasiekiate 272
• Iki 100 nario patenkate į milijonus

Kuo skaičiai didesni, tuo seka tampa vis retesnė. Praleiskite vis daugiau sveikųjų skaičių. Nepaisant šio retėjimo, seka turi begalę narių—ji niekada nesustoja augusi.

Nuorodos ir papildoma literatūra

Pirminiai šaltiniai

1. OEIS A000695 - Moser-de Bruijn seka. Internetinė sveikųjų skaičių sekų enciklopedija. Išsami sekos duomenų ir savybių informacija.

2. De Bruijn, N. G. „Apie sveikųjų skaičių bazę". Publicationes Mathematicae Debrecen, t. 1, 1950, p. 232-242. Pagrindinis straipsnis, nustatantis pagrindinius sudėtinių bazių požymius.

3. Moser, Leo. „Generuojančių eilučių taikymas". Mathematics Magazine, t. 35, nr. 1, 1962, p. 37-38. Ankstyvieji darbai, nagrinėjantys sekos generuojančias funkcijas.

Papildomas matematinis kontekstas

4. Stolarsky, Kenneth B. „Skaitmeninių sumų galios ir eksponentinės sumos, susijusios su dvejetainių koeficientų lyginumu". SIAM Journal on Applied Mathematics, t. 32, nr. 4, 1977, p. 717-730. Nagrinėja skaitmeninių sumų savybes, susijusias su sekomis, panašiomis į Moser-de Bruijn.

5. Allouche, Jean-Paul ir Jeffrey Shallit. Automatinės sekos: teorija, taikymai, apibendrinimas. Cambridge University Press, 2003. Skyrius apie automatines sekas, įskaitant ryšius su Moser-de Bruijn seka.

Susiję konceptai

6. Sumų laisvos aibės - Vikipedija. Papildomas kontekstas sudėtinės skaičių teorijos srityje.

7. Sudėtinės bazės - Vikipedija. Apžvalga apie aibes, galinčias reprezentuoti sveikuosius skaičius kaip sumas.

Dažniausiai užduodami klausimai

Kam naudojama Moser-de Bruijn seka?

Seka turi kelias taikymo sritis: skaičių teorijos tyrimai, nagrinėjantys sudėtinius pagrindus, kombinatorikos darbai apie sumų laisvas aibes, kompiuterijos švietimas (ypač mokant bitinių operacijų ir efektyvių algoritmų), bei matematinių modelių analizė. Tai taip pat puikus mokomasis įrankis siekiant suprasti, kaip skirtingos skaičių sistemos siejasi tarpusavyje.

Kaip sugeneruoti Moser-de Bruijn seką?

Paimkite kiekvieną indeksą n pradedant nuo 0, konvertuokite į dvejetainę sistemą, tada pakeiskite kiekvieną "1" bitą atitinkamu 4-ojo laipsnio skaičiumi. Pavyzdžiui, indeksas 5 turi dvejetainę reprezentaciją 101, todėl apskaičiuojate 4² + 4⁰ = 16 + 1 = 17. Tai yra 5-asis narys (skaičiuojant nuo 0 indekso).

Kas daro Moser-de Bruijn seką ypatinga?

Kiekvienas sekos skaičius turi išskirtinę savybę: jo ketvirtainė reprezentacija turi tik 0 ir 1 – niekada 2 ar 3. Tai reiškia, kad galite sukurti kiekvieną narį pridedant 4-ojo laipsnio galias, kur kiekviena galia pasirodo ne daugiau kaip vieną kartą. Tai panašu į dvejetainę sistemą, tačiau naudojant 4-ojo laipsnio galias vietoj 2-ojo laipsnio.

Kaip patikrinti, ar konkretus skaičius yra sekoje?

Konvertuokite skaičių į ketvirtainę sistemą ir pažiūrėkite į skaitmenis. Jei matote tik 0 ir 1, jis yra sekoje. Jei bet kuris skaitmuo yra 2 ar 3, jo nėra. Pavyzdžiui, 21 ketvirtainėje sistemoje yra 111 (visi 1 ir 0), todėl jis yra. Bet 22 ketvirtainėje sistemoje yra 112 (turi 2), todėl jo nėra.

Koks yra n-ojo nario formulės pagrindas?

N-asis narys M(n) seka šią formulę: M(n) = Σ(b_i × 4^i), kur b_i reiškia n dvejetainius skaitmenis. Paprastais žodžiais: užrašykite n dvejetainėje sistemoje, tada kiekvienoje pozicijoje su 1 pridėkite atitinkamą 4-ojo laipsnio galią.

Ar seka yra begalinė?

Taip, ji tęsiasi amžinai. Moser-de Bruijn sekoje yra begalė narių. Tačiau kylant aukštyn, seka tampa vis retesnė – praleidžiate vis daugiau įprastinių skaičių tarp sekos narių.

Kuo ši seka skiriasi nuo dvejetainių sekų?

Dvejetainės sekos (2-ojo laipsnio sumų) gali reprezentuoti kiekvieną neneigiamą sveikąjį skaičių – tai tai, ką daro dvejetainė reprezentacija. Moser-de Bruijn seka naudoja 4-ojo laipsnio galias, kas sukuria daug retesnį rinkinį. Dauguma skaičių nepatenka į Moser-de Bruijn seką.

Kas atrado šią seką?

Leo Moser (1921-1970), austrų-kanadietis matematikas, ir Nicolaas Govert de Bruijn (1918-2012), olandų matematikas, abu išsamiai tyrė šią seką 1960-aisiais kaip sudėtinės skaičių teorijos tyrimo dalį. Seka pavadinta jų abiejų vardais.

Pasiruošę tyrinėti?

Šis generatorius veikia visiškai jūsų naršyklėje – jokio diegimo, jokios registracijos, jokio laukimo. Nesvarbu, ar esate studentas, besimokantis apie skaičių sistemas, tyrėjas, nagrinėjantis sudėtinius pagrindus, ar tiesiog matematiškai smalsaujantis, galite iš karto generuoti terminus ir patys stebėti dėsningumus. Pabandykite generuoti skirtingus kiekius ir stebėkite, kaip seka auga ir kokie sveikieji skaičiai į ją patenka.