Penjana Urutan Moser-de Bruijn | Kalkulator Kuasa 4

Apakah Jujukan Moser-de Bruijn?

Jujukan Moser-de Bruijn ialah senarai nombor bulat yang setiap satunya boleh ditulis sebagai jumlah kuasa 4 yang berlainan. Jujukan ini bermula dengan 0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85, dan berterusan tanpa penghujung. Jujukan ini dinamakan sempena ahli matematik Leo Moser dan Nicolaas Govert de Bruijn. Dalam Ensiklopedia Dalam Talian Jujukan Integer, jujukan ini dikatalogkan sebagai A000695.

Sesuatu nombor tergolong dalam jujukan ini tepat apabila perwakilannya dalam asas-4 hanya menggunakan digit 0 dan 1, bukan 2 atau 3. Sebagai contoh, 21 dalam asas 4 ditulis sebagai 111, maka nombor itu tergolong dalam jujukan. Nombor 22 dalam asas 4 ditulis sebagai 112, maka nombor itu tidak tergolong dalam jujukan.

Formula Jujukan Moser-de Bruijn

Jujukan ini boleh ditakrifkan dalam tiga cara yang setara.

Hasil tambah kuasa-kuasa berbeza bagi 4

Sesuatu nombor n berada dalam jujukan ini jika nombor itu boleh ditulis sebagai

$n = \sum_{i \in S} 4^i$

bagi suatu himpunan S yang terdiri daripada integer bukan negatif, dengan setiap kuasa 4 digunakan paling banyak sekali.

Ujian digit asas-4

Tulis nombor itu dalam asas 4. Jika setiap digit ialah 0 atau 1, nombor itu berada dalam jujukan. Jika terdapat mana-mana digit 2 atau 3, nombor itu tidak berada dalam jujukan.

Penggantian binari kepada asas-4

Dengan mengira sebutan bermula daripada n = 0, sebutan pada indeks n ialah

$M(n) = \sum_{i=0}^{k} b_i \cdot 4^i$

dengan $b_i$ ialah digit binari bagi n. Ringkasnya, tulis n dalam bentuk binari, kemudian baca setiap digit binari sebagai digit asas-4 pada kedudukan yang sama. Inilah kaedah yang digunakan oleh penjana kerana kaedah ini hanya perlu menyemak bit dan menjumlahkan nombor.

Cara Mengira Sebutan Ke-N

Untuk mencari M(n), penjana melakukan langkah berikut bagi setiap indeks n, bermula dengan n = 0:

1. Lihat bentuk binari n.
2. Bagi setiap bit yang sama dengan 1, pada kedudukan j, tambahkan 4^j kepada jumlah semasa.
3. Abaikan bit yang sama dengan 0.
4. Jumlah semasa ialah M(n).

Contoh pengiraan: M(5)

• 5 dalam bentuk binari ialah 101.
• Bit 0 (paling kanan) ialah 1, maka tambahkan 4⁰ = 1.
• Bit 1 ialah 0, maka tiada apa-apa ditambahkan.
• Bit 2 ialah 1, maka tambahkan 4² = 16.
• Jumlah: 1 + 16 = 17.

Jadi, M(5) = 17. Ini ialah nilai keenam yang dihasilkan oleh penjana kerana pengiraan bermula pada M(0).

Contoh: 32 Sebutan Pertama

Cara Menyemak Sama Ada Sesuatu Nombor Tergolong dalam Jujukan

Tukarkan nombor itu kepada asas 4 dan baca digit-digitnya.

• 85: dalam asas 4, 85 ialah 1111 (64 + 16 + 4 + 1). Hanya 0 dan 1 muncul, maka 85 tergolong dalam jujukan.
• 90: dalam asas 4, 90 ialah 1122. Ia mengandungi 2, maka 90 tidak tergolong dalam jujukan.

Kadar Pertumbuhan

Jujukan ini berkembang dengan cepat kerana setiap bit tambahan pada indeks boleh meningkatkan nilai yang ditambah kira-kira empat kali ganda. M(19) ialah 261. M(99) ialah 5,125. M(999), iaitu sebutan terbesar yang boleh dihasilkan oleh penjana ini, ialah 349,205. Sebutan semakin berjauhan apabila indeks bertambah, menjadikan jujukan ini jarang: kebanyakan nombor bulat tidak pernah muncul dalamnya walaupun jujukan ini mempunyai bilangan sebutan yang tidak terhingga.

Cara Menggunakan Penjana Jujukan Moser-de Bruijn

1. Masukkan bilangan sebutan yang hendak dijana. Medan ini ditetapkan kepada 20 secara lalai jika dibiarkan kosong.
2. Senarai sebutan dikemas kini secara automatik, bermula daripada M(0).
3. Salin senarai penuh dengan butang Copy Result.

Alat ini menerima nombor bulat daripada 1 hingga 1000. Nombor perpuluhan, nombor negatif dan entri bukan angka akan ditolak. Permintaan untuk 20 sebutan menghasilkan M(0) hingga M(19); nilai terakhir yang dipaparkan ialah 261. Semua pengiraan berlaku dalam pelayar, maka hasil dipaparkan serta-merta dan tiada data dihantar ke pelayan.

Jujukan Berkaitan

• Kuasa-kuasa 2 (OEIS A000079): 1, 2, 4, 8, 16, 32 dan seterusnya. Inilah blok binaan nombor binari biasa.
• Hasil tambah kuasa-kuasa berbeza bagi 3 (OEIS A005836): 0, 1, 3, 4, 9, 10, 12, 13 dan seterusnya. Idea yang sama seperti jujukan Moser-de Bruijn, tetapi dibina daripada asas 3 dan bukannya asas 4.
• Nombor Fibbinary (OEIS A003714): 0, 1, 2, 4, 5, 8, 9, 10 dan seterusnya. Nombor yang bentuk binarinya tidak mempunyai dua 1 berturut-turut.

Sejarah

Leo Moser (1921-1970) ialah ahli matematik Austria-Kanada yang bekerja dalam bidang teori nombor, kombinatorik dan geometri. Nicolaas Govert de Bruijn (1918-2012) ialah ahli matematik Belanda yang terkenal dengan hasil kerjanya dalam bidang kombinatorik, teori graf dan sains komputer; jujukan de Bruijn beliau yang tidak berkaitan digunakan secara meluas dalam teori pengekodan. Kedua-duanya mengkaji asas aditif: set integer, seperti kuasa-kuasa 4, yang setiap nombor boleh diwakili mempunyai tepat satu perwakilan sebagai hasil tambah. Jujukan yang membawa nama mereka ialah salah satu contoh asas sedemikian.

Soalan lazim

Untuk apakah jujukan Moser-de Bruijn digunakan?

Jujukan ini muncul dalam teori nombor aditif dan kombinatorik, khususnya dalam kajian set bebas hasil tambah dan asas aditif. Jujukan ini juga digunakan untuk mengajar penukaran asas dan operasi bit demi bit dalam sains komputer.

Bagaimanakah jujukan Moser-de Bruijn dijana?

Tulis indeks n dalam bentuk binari, kemudian baca setiap digit binari sebagai digit asas-4 pada kedudukan yang sama. Bagi n = 5 (binari 101), hasilnya ialah 4² + 4⁰ = 17.

Bagaimanakah saya boleh menyemak sama ada sesuatu nombor tergolong dalam jujukan?

Tukarkannya kepada asas 4. Jika setiap digit ialah 0 atau 1, nombor itu tergolong dalam jujukan. Jika terdapat mana-mana digit 2 atau 3, nombor itu tidak tergolong dalam jujukan.

Apakah formula bagi sebutan ke-n?

M(n) = jumlah, bagi semua i, untuk $b_i \cdot 4^i$, dengan $b_i$ ialah digit binari bagi n.

Adakah jujukan ini tidak terhingga?

Ya. Jujukan ini mempunyai bilangan sebutan yang tidak terhingga, walaupun sebutan-sebutannya semakin berjauhan apabila n bertambah.

Apakah perbezaannya dengan binari?

Binari, iaitu hasil tambah kuasa-kuasa berbeza bagi 2, boleh mewakili setiap integer bukan negatif. Jujukan Moser-de Bruijn menggunakan kuasa-kuasa 4 pula, maka kebanyakan integer tidak termasuk dalam jujukan.