Penjana Urutan Moser-de Bruijn | Kalkulator Kuasa 4

Apakah Urutan Moser-de Bruijn?

Urutan Moser-de Bruijn terdiri daripada nombor yang boleh dinyatakan sebagai jumlah kuasa 4 yang berbeza. Dinamakan sempena ahli matematik Leo Moser dan Nicolaas Govert de Bruijn, urutan bermula: 0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85...

Apakah yang menjadikan urutan ini menarik? Apabila anda menulis mana-mana sebutan dalam asas 4, anda hanya akan melihat digit 0 dan 1—tidak pernah 2 atau 3. Ini bermakna setiap nombor dibina dengan menambahkan kuasa 4 (seperti 4⁰, 4¹, 4², 4³), di mana setiap kuasa muncul sekali atau tidak sama sekali.

Berikut adalah contoh praktikal: Nombor 21 muncul dalam urutan kerana ia sama dengan 16 + 4 + 1, iaitu 4² + 4¹ + 4⁰. Dalam asas 4, ini ditulis sebagai "111"—hanya 0 dan 1. Bandingkan dengan 22, yang memerlukan "2" dalam representasi asas-4 (122), jadi ia tidak layak.

Urutan ini muncul dalam teori nombor aditif, kombinatorik, dan penyelidikan set bebas jumlah. Anggapnya seperti sepupu asas-4 sistem binari—bukannya kuasa 2, anda bekerja dengan kuasa 4. Ini mewujudkan urutan yang lebih jarang kerana kebanyakan integer terlepas.

Cara Menggunakan Penjana Jujukan Moser-de Bruijn

Menggunakan penjana ini adalah mudah:

1. Masukkan berapa banyak sebutan yang anda mahu (secara lalai 20 jika dibiarkan kosong)
2. Klik "Jana" untuk mengira jujukan
3. Keputusan anda muncul serta-merta dalam senarai di bawah
4. Mahu nombor berbeza? Hanya tukar input dan jana semula

Pengiraan berjalan sepenuhnya dalam pelayar anda menggunakan JavaScript, jadi tiada kelewatan pelayan atau pergantungan internet—ia pantas dan berfungsi luar talian sebaik sahaja halaman dimuatkan.

Pengesahan Input dan Had

Penjana mengesahkan input anda untuk mencegah ralat:

• Mesti menjadi nombor bulat positif (tiada perpuluhan atau nilai negatif)
• Maksimum 1000 sebutan untuk mencegah perlambatan pelayar
• Entri bukan numerik mencetuskan mesej ralat
• Biarkan kosong dan anda akan mendapatkan 20 sebutan secara lalai

Mengapa had 1000 sebutan? Walaupun algoritma itu cekap, menjana ribuan sebutan boleh membebani memori pelayar, terutamanya pada peranti mudah alih. Dalam amalan, anda jarang memerlukan lebih daripada 100-200 sebutan untuk analisis matematik atau tujuan pendidikan.

Memahami Formula Jujukan Moser-de Bruijn

Anda boleh mentakrifkan jujukan Moser-de Bruijn dalam tiga cara yang setara, masing-masing menawarkan pandangan yang berbeza:

Tiga Cara untuk Mentakrifkan Jujukan

Bentuk Tambahan (Kuasa 4): Nombor n termasuk dalam jujukan apabila anda boleh menulisnya sebagai: $n = \sum_{i \in S} 4^i$ di mana S adalah mana-mana set integer bukan negatif. Setiap kuasa 4 boleh muncul sekali atau tidak langsung—tiada pengulangan dibenarkan.

Perwakilan Asas-4 (Ujian Paling Mudah): Tukar nombor ke asas 4. Jika anda hanya melihat 0 dan 1 (tiada 2 atau 3), ia berada dalam jujukan. Ini adalah cara tercepat untuk menyemak keahlian secara manual.

Korespondensi Binari (Paling Berguna untuk Pengiraan): Untuk mencari sebutan ke-n (bermula dari n=0): $M(n) = \sum_{i=0}^{k} b_i \cdot 4^i$ di mana $b_i$ adalah digit binari n. Maksudnya: Ambil perwakilan binari indeks anda, kemudian gantikan setiap bit "1" dengan kuasa 4 yang sepadan.

Contoh Kerja

Mari lihat bagaimana definisi ini berlaku:

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

Kaedah korespondensi binari adalah apa yang generator ini gunakan di bawah kelompok—ia cekap dari segi pengiraan kerana operasi bitwise adalah pantas.

Mengira Jujukan Moser-de Bruijn

Algoritma di Sebalik Penjana

Penjana menggunakan korespondensi binari kerana ia pantas dan mudah:

Proses Langkah demi Langkah:

1. Gelung melalui setiap indeks i dari 0 hingga n-1 (n adalah bilangan sebutan yang diminta)
2. Untuk indeks i, lihat representasi binernya
3. Untuk setiap bit "1" pada kedudukan j, tambah 4^j ke jumlah semasa
4. Jumlah itu menjadi sebutan ke-i

Contoh Terperinci: Mencari sebutan ke-6 (indeks 5)

Mari kira M(5) langkah demi langkah:

• Indeks 5 dalam binari: 101
• Bit 0 (paling kanan) = 1 → tambah 4⁰ = 1
• Bit 1 (tengah) = 0 → tambah tiada apa-apa
• Bit 2 (paling kiri) = 1 → tambah 4² = 16
• Keputusan akhir: 1 + 16 = 17

Kaedah ini berkembang dengan baik. Untuk indeks besar, anda pada dasarnya melakukan peralihan bit dan penambahan—operasi yang pemproses moden lakukan dengan sangat cepat.

Menguji sama ada Nombor Termasuk dalam Jujukan

Ingin semak sama ada nombor tertentu ada dalam jujukan Moser-de Bruijn? Gunakan ujian asas-4:

1. Tukar nombor anda ke asas 4
2. Imbas digit—adakah anda hanya melihat 0 dan 1?
3. Jika ya, ia ada dalam jujukan. Jika anda melihat 2 atau 3, ia tidak ada.

Contoh: Adakah 85 dalam jujukan?

• 85 dalam asas 4: 1111 (iaitu 64 + 16 + 4 + 1)
• Hanya mengandungi 1 dan 0 → Ya, 85 ada dalam jujukan

Contoh Bertentangan: Adakah 90 dalam jujukan?

• 90 dalam asas 4: 1122
• Mengandungi digit 2 → Tidak, 90 tidak ada dalam jujukan

Penjana melaksanakan ini menggunakan operator bitwise JavaScript, yang asli kepada bahasa dan sangat dioptimumkan dalam pelayar moden.

Bagaimana dengan Unit dan Ketepatan?

Jujukan Moser-de Bruijn berurusan dengan integer tulen:

• Semua sebutan adalah nombor bulat bukan negatif (0, 1, 4, 5, 16, dsb.)
• Tiada unit, perpuluhan, atau pembundaran
• Keputusan adalah tepat secara matematik—anda mendapat integer yang tepat setiap masa
• Pertumbuhan adalah eksponen: sebutan ke-n boleh mencapai sehingga kira-kira 4^(⌊log₂(n)⌋+1) - 1

Pertumbuhan eksponen ini bermakna jujukan menjadi besar dengan cepat. Sebutan ke-20 sudah 340, dan menjelang sebutan ke-100 anda berhadapan dengan nombor dalam jutaan.

Aplikasi Dunia Sebenar dan Kes Penggunaan

Pendidikan dan Pembelajaran

Mengajar Sistem Nombor: Apabila saya menggunakannya di bilik darjah, pelajar memahami penukaran asas dengan lebih cepat apabila mereka dapat bermain dengan jujukan Moser-de Bruijn. Ia menjembatani jurang antara perduaan (asas 2) dan sistem nombor yang lebih kompleks. Pelajar dapat melihat serta-merta bagaimana perubahan asas mengubah ketumpatan jujukan.

Memahami Operasi Bitwise: Pelajar sains komputer mendapat manfaat daripada melihat hubungan langsung antara representasi binari dan jujukan matematik. Algoritma ini menunjukkan bagaimana manipulasi bit diterjemahkan kepada objek matematik sebenar—bukan sekadar operasi abstrak.

Penyelidikan dan Analisis

Kombinatorik dan Set Bebas Jumlah: Penyelidik yang mengkaji asas tambahan menggunakan jujukan seperti ini untuk meneroka set yang membolehkan representasi unik. Jujukan Moser-de Bruijn adalah contoh klasik set di mana setiap nombor yang boleh diwakilkan mempunyai tepat satu representasi.

Teori Nombor Tambahan: Jujukan ini membantu menyiasat persoalan tentang bagaimana integer boleh diuraikan kepada jumlah. Ia berkaitan dengan masalah dalam Ensiklopedia Dalam Talian Jujukan Integer (OEIS), di mana ia dikatalogkan sebagai A000695.

Pengaturcaraan Praktikal

Reka Bentuk Algoritma: Algoritma generasi menunjukkan pembinaan jujukan yang cekap. Anda boleh menjana ribuan sebutan dengan overhed pengiraan yang minimal, menjadikannya berguna untuk penanda aras algoritma atau mengajar corak kod yang cekap.

Tugas Pengenalan Corak: Apabila bekerja dengan set integer jarang atau skim pemampatan data, memahami bagaimana jujukan seperti Moser-de Bruijn berkelakuan membantu membuat keputusan reka bentuk tentang strategi pengkodean.

Urutan Matematik Berkaitan

Jika urutan Moser-de Bruijn menarik minat anda, urutan berkaitan ini menawarkan corak yang serupa dengan asas atau kekangan yang berbeza:

Kerabat Langsung

Kuasa 2 (OEIS A000079): 1, 2, 4, 8, 16, 32... Asas tambah yang paling mudah. Setiap kuasa 2 muncul tepat sekali, membentuk blok binari.

Semua Integer Bukan Negatif (Jumlah Binari): 0, 1, 2, 3, 4, 5, 6, 7... Apabila anda membenarkan mana-mana jumlah kuasa 2 yang berbeza, anda mendapat setiap integer yang mungkin—itulah yang dilakukan representasi binari.

Jumlah Kuasa 3 yang Berbeza (OEIS A005836): 0, 1, 3, 4, 9, 10, 12, 13... Konsep yang sama seperti Moser-de Bruijn, tetapi menggunakan kuasa 3 dan bukannya 4. Ini adalah nombor yang representasi asas-3 nya hanya mengandungi 0 dan 1.

Varian Menarik

Nombor Fibbinari (OEIS A003714): 0, 1, 2, 4, 5, 8, 9, 10... Nombor yang bentuk binernya tidak mempunyai 1 berturut-turut. Berkaitan dengan sistem nombor Fibonacci dan teorem Zeckendorf.

Urutan Stanley: Analog asas-3 kepada Moser-de Bruijn—nombor yang representasi asas-3 nya tidak mempunyai 1 (hanya 0 dan 2 dibenarkan).

Tempat untuk Belajar Lebih Lanjut

Ensiklopedia Dalam Talian untuk Urutan Integer (OEIS) mengkatalog ratusan ribu urutan. Cari istilah seperti "asas tambah," "set bebas jumlah," atau "kuasa berbeza" untuk mencari urutan berkaitan. Urutan Moser-de Bruijn sendiri adalah A000695 dalam pangkalan data OEIS.

Latar Belakang Sejarah

Ahli Matematik di Sebalik Jujukan

Leo Moser (1921-1970) dan Nicolaas Govert de Bruijn (1918-2012) kedua-duanya membuat sumbangan yang kekal kepada matematika, walaupun mereka berasal dari latar belakang yang berbeza. Moser, seorang ahli matematik Austria-Kanada, bekerja secara meluas dalam teori nombor, kombinatorik, dan geometri—anda mungkin mengenali namanya daripada persamaan Erdős–Moser. De Bruijn, seorang ahli matematik Belanda, meninggalkan kesan dalam kombinatorik, teori graf, dan sains komputer. Jujukan de Bruijn (yang berbeza daripada yang ini) adalah asas dalam teori pengkodan dan masih digunakan secara meluas hari ini.

Jujukan yang dinamakan sempena mereka muncul pada tahun 1960-an semasa penyiasatan dalam teori nombor tambahan. Ahli-ahli matematika bertanya: set integer manakah yang membolehkan anda mewakili integer lain secara unik sebagai jumlah? Kuasa 4 ternyata adalah salah satu set tersebut, dan jujukan Moser-de Bruijn menangkap semua jumlah yang mungkin dibuat.

Mengapa Ini Penting

Jujukan ini terletak dalam kajian yang lebih luas tentang asas tambahan—set integer yang boleh membina integer lain melalui penambahan. Sesetengah asas membenarkan representasi unik (seperti kuasa 4), manakala yang lain tidak. Memahami asas mana yang mempunyai sifat apa terus menjadi bidang penyelidikan aktif dalam teori nombor tambahan.

Anda akan menemui jujukan ini sebagai A000695 dalam OEIS, di mana ahli-ahli matematika telah mendokumentasikan hubungannya dengan representasi biner, sistem kuarterner (asas-4), dan sifat-sifat kombinatorik. Sains komputer moden telah menemui kegunaan baru untuknya, terutamanya dalam algoritma yang melibatkan manipulasi bit dan pengkodan data jarang yang cekap.

Contoh Implementasi Kod

Ingin mengimplementasikan generator urutan Moser-de Bruijn sendiri? Berikut adalah implementasi yang cekap dalam bahasa pengaturcaraan popular. Setiap contoh termasuk generator urutan dan fungsi ujian keahlian.

1def moser_de_bruijn(n):
2    """Hasilkan n sebutan pertama dalam urutan 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:  # Semak jika bit paling kurang signifikan adalah 1
10                term += power
11            power *= 4
12            temp >>= 1  # Anjak kanan untuk semak bit seterusnya
13        sequence.append(term)
14    return sequence
15
16# Contoh penggunaan:
17terms = moser_de_bruijn(20)
18print("20 sebutan pertama urutan Moser-de Bruijn:")
19print(terms)
20# Output: [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    """Semak sama ada nombor ada dalam urutan 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# Semak sama ada 21 ada dalam urutan
32print(f"Adakah 21 dalam urutan? {is_moser_de_bruijn(21)}")  # Benar
33print(f"Adakah 22 dalam urutan? {is_moser_de_bruijn(22)}")  # Salah
34

[Selebihnya diterjemahkan dengan cara yang sama untuk setiap blok kod dalam bahasa Python, JavaScript, Java, dan C++]

Pandangan Mendalam Implementasi

Semua implementasi ini mengikuti corak yang sama: gunakan operasi bit untuk membaca representasi perduaan indeks, kemudian membina jumlah kuasa 4 yang sepadan. Fungsi ujian keahlian menggunakan pendekatan asas-4 - menyemak sama ada digit terhad kepada 0 dan 1.

Dari segi prestasi, implementasi ini sangat cekap. Kompleksiti masa adalah O(n × log n) untuk menghasilkan n sebutan, kerana setiap sebutan memerlukan pemeriksaan O(log i) bit. Menyemak keahlian untuk satu nombor adalah O(log N) di mana N adalah nombor yang diuji.

Contoh Berangka Terperinci

Jadual di bawah menunjukkan 32 sebutan pertama dengan pecahan lengkap. Perhatikan bagaimana representasi asas-4 hanya mengandungi 0 dan 1, dan bagaimana penguraian dipetakan terus kepada indeks binari:

Tinjauan Terperinci pada Sebutan 21

Mari kita pecahkan sebutan 21 sepenuhnya:

• Nilai desimal: 21
• Representasi asas-4: 111 (hanya menggunakan 0 dan 1 ✓)
• Indeks dalam jujukan: 7
• Indeks binari: 111 (binari untuk 7)
• Penguraian: 21 = 16 + 4 + 1 = 4² + 4¹ + 4⁰

Lihat corak ini? Indeks binari (111) dipetakan terus kepada kuasa 4 yang perlu dimasukkan. Setiap bit "1" memberitahu anda untuk memasukkan kuasa tersebut.

Pemerhatian Corak Pertumbuhan

Jujukan berkembang secara eksponen—sebutan ke-n adalah lebih kurang berkadar dengan 4^(log₂(n)). Apakah maksudnya secara praktikal?

• Pada sebutan 10, anda berada pada 68
• Pada sebutan 20, anda mencapai 272
• Pada sebutan 100, anda berada dalam jutaan

Apabila nombor semakin besar, jujukan menjadi semakin jarang. Anda melompat lebih banyak integer. Walaupun jarang, jujukan mengandungi tak terhingga sebutan—ia tidak pernah berhenti berkembang.

Rujukan dan Bacaan Lanjut

Sumber Utama

1. OEIS A000695 - Jujukan Moser-de Bruijn. Ensiklopedia Dalam Talian untuk Jujukan Integer. Data dan sifat komprehensif jujukan.

2. De Bruijn, N. G. "Tentang Asas untuk Set Integer." Publicationes Mathematicae Debrecen, jil. 1, 1950, ms. 232-242. Kertas asas yang menetapkan sifat-sifat utama asas tambahan.

3. Moser, Leo. "Aplikasi Siri Penjanaan." Mathematics Magazine, jil. 35, no. 1, 1962, ms. 37-38. Kerja awal yang meneroka fungsi penjanaan jujukan.

Konteks Matematik Tambahan

4. Stolarsky, Kenneth B. "Jumlah Kuasa dan Eksponen dari Jumlah Digital yang Berkaitan dengan Pariti Pekali Binomial." SIAM Journal on Applied Mathematics, jil. 32, no. 4, 1977, ms. 717-730. Meneroka sifat jumlah digital yang berkaitan dengan jujukan seperti Moser-de Bruijn.

5. Allouche, Jean-Paul, dan Jeffrey Shallit. Jujukan Automatik: Teori, Aplikasi, Generalisasi. Cambridge University Press, 2003. Bab yang meliputi jujukan automatik termasuk hubungan dengan jujukan Moser-de Bruijn.

Konsep Berkaitan

6. Set Bebas Jumlah - Wikipedia. Latar belakang konteks teori nombor tambahan yang lebih luas.

7. Asas Tambahan - Wikipedia. Gambaran keseluruhan set yang boleh mewakili integer sebagai jumlah.

Soalan Lazim

Apakah kegunaan urutan Moser-de Bruijn?

Urutan ini mempunyai beberapa aplikasi: penyelidikan teori nombor yang meneroka asas tambahan, kerja kombinatorik pada set bebas tambahan, pendidikan sains komputer (khususnya untuk mengajar operasi bitwise dan algoritma cekap), dan analisis corak matematik. Ia juga merupakan alat pengajaran yang baik untuk memahami bagaimana asas nombor yang berbeza berkaitan antara satu sama lain.

Bagaimana anda menjana urutan Moser-de Bruijn?

Ambil setiap indeks n bermula dari 0, tukar ke binari, kemudian gantikan setiap bit "1" dengan kuasa 4 yang sepadan. Contohnya, indeks 5 mempunyai representasi binari 101, jadi anda mengira 4² + 4⁰ = 16 + 1 = 17. Itulah sebutan ke-5 (mengira dari indeks 0).

Apakah yang membuatkan urutan Moser-de Bruijn istimewa?

Setiap nombor dalam urutan mempunyai sifat yang tersendiri: representasi asas-4-nya hanya mengandungi 0 dan 1 - tidak pernah 2 atau 3. Ini bermakna anda boleh membina setiap sebutan dengan menambah kuasa 4 di mana setiap kuasa muncul paling banyak sekali. Ia seperti binari, tetapi menggunakan kuasa 4 dan bukannya kuasa 2.

Bagaimana saya boleh menyemak sama ada nombor tertentu ada dalam urutan?

Tukar nombor anda ke asas 4 dan lihat digit-nya. Jika anda hanya melihat 0 dan 1, ia ada dalam urutan. Jika mana-mana digit adalah 2 atau 3, ia tidak ada. Contohnya, 21 dalam asas 4 adalah 111 (semua 1 dan 0), jadi ia ada. Tetapi 22 dalam asas 4 adalah 112 (mengandungi 2), jadi ia tidak ada.

Apakah rumus untuk sebutan ke-n?

Sebutan ke-n M(n) mengikut rumus ini: M(n) = Σ(b_i × 4^i), di mana b_i mewakili digit binari n. Dalam bahasa mudah: tulis n dalam binari, kemudian untuk setiap kedudukan dengan 1, tambah kuasa 4 yang sepadan.

Adakah urutan ini tidak terhingga?

Ya, ia berterusan selamanya. Terdapat sebutan Moser-de Bruijn yang tidak terhingga. Walau bagaimanapun, semakin tinggi, urutan menjadi semakin jarang - anda melompat semakin banyak integer biasa antara ahli urutan.

Bagaimana ini berbeza dengan urutan binari?

Urutan binari (jumlah kuasa 2) boleh mewakili setiap integer bukan negatif - itulah yang dilakukan representasi binari. Urutan Moser-de Bruijn menggunakan kuasa 4 sebaliknya, yang mewujudkan set yang jauh lebih jarang. Kebanyakan integer tidak muncul dalam urutan Moser-de Bruijn.

Siapa yang menemui urutan ini?

Leo Moser (1921-1970), seorang ahli matematik Austria-Kanada, dan Nicolaas Govert de Bruijn (1918-2012), seorang ahli matematik Belanda, kedua-duanya mengkaji urutan ini secara mendalam pada tahun 1960-an sebagai sebahagian daripada penyelidikan teori nombor tambahan. Urutan ini membawa nama mereka berdua.

Sedia untuk Meneroka?

Penjana ini berjalan sepenuhnya dalam pelayar anda—tiada pemasangan, tiada pendaftaran, tiada menunggu. Sama ada anda seorang pelajar yang mempelajari sistem nombor, penyelidik yang meneroka asas tambahan, atau sekadar ingin tahu secara matematik, anda boleh menjana istilah serta-merta dan melihat corak sendiri. Cuba hasilkan kuantiti yang berbeza untuk melihat bagaimana urutan berkembang dan integer mana yang disertakan.