เครื่องมือสร้างลำดับโมเซอร์-เดอ บรูจิน | เครื่องคำนวณกำลังของ 4

โมเซอร์-เดอ บรูจิน ซีเควนซ์คืออะไร?

ซีเควนซ์โมเซอร์-เดอ บรูจิน ประกอบด้วยตัวเลขที่สามารถแสดงเป็นผลรวมของกำลังของ 4 ที่แตกต่างกัน ตั้งชื่อตามนักคณิตศาสตร์ Leo Moser และ Nicolaas Govert de Bruijn ซีเควนซ์เริ่มต้นด้วย: 0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85...

อะไรที่ทำให้ซีเควนซ์นี้น่าสนใจ? เมื่อคุณเขียนพจน์ใดๆ ในฐาน 4 คุณจะเห็นเพียงหลัก 0 และ 1 เท่านั้น—ไม่มี 2 หรือ 3 นั่นหมายความว่าแต่ละตัวเลขสร้างจากการบวกกำลังของ 4 (เช่น 4⁰, 4¹, 4², 4³) โดยแต่ละกำลังปรากฏหนึ่งครั้งหรือไม่ปรากฏเลย

นี่คือตัวอย่างที่เป็นรูปธรรม: ตัวเลข 21 ปรากฏในซีเควนซ์เพราะเท่ากับ 16 + 4 + 1 ซึ่งเป็น 4² + 4¹ + 4⁰ ในฐาน 4 จะเขียนเป็น "111"—มีเพียง 0 และ 1 เปรียบเทียบกับ 22 ซึ่งจะต้องใช้ "2" ในการแสดงฐาน 4 (122) ดังนั้นจึงไม่ผ่าน

ซีเควนซ์นี้ปรากฏในทฤษฎีจำนวนแบบบวก การจัดหมวดหมู่ และการวิจัยเกี่ยวกับชุดที่ไม่สามารถบวกกันได้ คิดถึงมันเหมือนกับคู่ฐาน 4 ของระบบฐานสอง—แทนที่จะเป็นกำลังของ 2 คุณกำลังทำงานกับกำลังของ 4 สิ่งนี้สร้างซีเควนซ์ที่เบาบางมากเนื่องจากมีจำนวนเต็มส่วนใหญ่ถูกข้ามไป

วิธีใช้เครื่องมือสร้างลำดับ Moser-de Bruijn

การใช้เครื่องมือนี้ทำได้อย่างง่ายดาย:

ป้อนจำนวนพจน์ที่คุณต้องการ (ค่าเริ่มต้นคือ 20 หากปล่อยว่างไว้)
คลิก "สร้าง" เพื่อคำนวณลำดับ
ผลลัพธ์ของคุณจะปรากฏทันทีในรายการด้านล่าง
ต้องการตัวเลขอื่น? เพียงเปลี่ยนข้อมูลป้อนเข้าและสร้างอีกครั้ง

การคำนวณทำงานทั้งหมดในเบราว์เซอร์ของคุณโดยใช้ JavaScript ดังนั้นจึงไม่มีความล่าช้าของเซิร์ฟเวอร์หรือการพึ่งพาอินเทอร์เน็ต—มันรวดเร็วและทำงานออฟไลน์หลังจากโหลดหน้าเสร็จ

การตรวจสอบข้อมูลป้อนเข้าและขีดจำกัด

เครื่องมือตรวจสอบข้อมูลป้อนเข้าของคุณเพื่อป้องกันข้อผิดพลาด:

ต้องเป็นจำนวนเต็มบวก (ไม่มีทศนิยมหรือค่าลบ)
สูงสุด 1000 พจน์เพื่อป้องกันการชะลอตัวของเบราว์เซอร์
รายการที่ไม่ใช่ตัวเลขจะเรียกใช้ข้อความแสดงข้อผิดพลาด
ปล่อยว่างไว้และคุณจะได้ 20 พจน์ตามค่าเริ่มต้น

ทำไมต้องจำกัดที่ 1000 พจน์? แม้ว่าอัลกอริทึมจะมีประสิทธิภาพ แต่การสร้างพจน์นับพันสามารถทำให้หน่วยความจำของเบราว์เซอร์ตึงเครียด โดยเฉพาะอย่างยิ่งบนอุปกรณ์เคลื่อนที่ ในทางปฏิบัติ คุณจะแทบไม่ต้องการมากกว่า 100-200 พจน์สำหรับการวิเคราะห์ทางคณิตศาสตร์หรือวัตถุประสงค์ทางการศึกษาส่วนใหญ่

ความเข้าใจสูตรลำดับ Moser-de Bruijn

คุณสามารถกำหนดลำดับ Moser-de Bruijn ได้สามวิธีที่เทียบเท่ากัน แต่ละวิธีให้มุมมองที่แตกต่างกัน:

สามวิธีในการกำหนดลำดับ

รูปแบบการบวก (กำลังของ 4): ตัวเลข n เป็นสมาชิกของลำดับเมื่อคุณสามารถเขียนได้ว่า: $n = \sum_{i \in S} 4^i$ โดยที่ S เป็นเซตของจำนวนเต็มที่ไม่เป็นลบใดๆ แต่ละกำลังของ 4 สามารถปรากฏได้หนึ่งครั้งหรือไม่ปรากฏเลย - ห้ามซ้ำ

การแทนฐาน 4 (การทดสอบที่ง่ายที่สุด): แปลงตัวเลขเป็นฐาน 4 หากคุณเห็นเฉพาะ 0 และ 1 (ไม่มี 2 หรือ 3) แสดงว่าอยู่ในลำดับ นี่คือวิธีที่เร็วที่สุดในการตรวจสอบสมาชิกด้วยตนเอง

ความสอดคล้องฐานสอง (มีประโยชน์ที่สุดสำหรับการคำนวณ): เพื่อหาพจน์ที่ n (เริ่มจาก n=0): $M(n) = \sum_{i=0}^{k} b_i \cdot 4^i$ โดยที่ $b_i$ คือเลขฐานสองของ n กล่าวคือ นำการแทนฐานสองของดัชนีของคุณ แล้วแทนที่บิต "1" ด้วยกำลังของ 4 ที่ตรงกัน

ตัวอย่างการทำงาน

มาดูว่านิยามเหล่านี้เป็นอย่างไร:

n = 0 (ฐานสอง: 0) → M(0) = 0
n = 1 (ฐานสอง: 1) → M(1) = 4⁰ = 1
n = 2 (ฐานสอง: 10) → M(2) = 4¹ = 4
n = 3 (ฐานสอง: 11) → M(3) = 4¹ + 4⁰ = 5
n = 5 (ฐานสอง: 101) → M(5) = 4² + 4⁰ = 17

วิธีความสอดคล้องฐานสองคือสิ่งที่เครื่องมือนี้ใช้ภายใน - มีประสิทธิภาพในการคำนวณเพราะการดำเนินการบิตทำได้เร็ว

การคำนวณลำดับ Moser-de Bruijn

อัลกอริทึมเบื้องหลังตัวสร้าง

ตัวสร้างใช้การสอดคล้องแบบไบนารีเนื่องจากมีความเร็วและเรียบง่าย:

กระบวนการทีละขั้นตอน:

วนลูปผ่านดัชนีแต่ละตัว i จาก 0 ถึง n-1 (n คือจำนวนพจน์ที่คุณร้องขอ)
สำหรับดัชนี i ให้ดูการแสดงผลแบบไบนารีของมัน
สำหรับแต่ละบิต "1" ที่ตำแหน่ง j ให้เพิ่ม 4^j เข้าไปในผลรวมที่กำลังดำเนินการ
ผลรวมนั้นจะกลายเป็นพจน์ที่ i

ตัวอย่างการทำงาน: การหาพจน์ที่ 6 (ดัชนี 5)

มาคำนวณ M(5) ทีละขั้นตอน:

ดัชนี 5 ในระบบฐานสอง: 101
บิต 0 (ขวาสุด) = 1 → เพิ่ม 4⁰ = 1
บิต 1 (กลาง) = 0 → ไม่เพิ่มอะไรเลย
บิต 2 (ซ้ายสุด) = 1 → เพิ่ม 4² = 16
ผลลัพธ์สุดท้าย: 1 + 16 = 17

วิธีนี้ขยายได้ดี สำหรับดัชนีที่ใหญ่ คุณกำลังทำการเลื่อนบิตและการบวก—การดำเนินการที่โปรเซสเซอร์สมัยใหม่จัดการได้อย่างรวดเร็วมาก

การทดสอบว่าตัวเลขอยู่ในลำดับหรือไม่

ต้องการตรวจสอบว่าตัวเลขเฉพาะอยู่ในลำดับ Moser-de Bruijn หรือไม่? ใช้การทดสอบฐาน 4:

แปลงตัวเลขของคุณเป็นฐาน 4
สแกนหลัก—คุณเห็นเฉพาะ 0 และ 1 หรือไม่?
ถ้าใช่ แสดงว่าอยู่ในลำดับ ถ้าพบ 2 หรือ 3 แสดงว่าไม่อยู่

ตัวอย่าง: 85 อยู่ในลำดับหรือไม่?

85 ในฐาน 4: 1111 (นั่นคือ 64 + 16 + 4 + 1)
มีเฉพาะ 1 → ใช่ 85 อยู่ในลำดับ

ตัวอย่างตรงข้าม: 90 อยู่ในลำดับหรือไม่?

90 ในฐาน 4: 1122
มีหลัก 2 → ไม่ 90 ไม่ได้อยู่ในลำดับ

ตัวสร้างใช้ตัวดำเนินการบิตของ JavaScript ซึ่งเป็นแบบดั้งเดิมของภาษาและได้รับการปรับให้มีประสิทธิภาพสูงในเบราว์เซอร์สมัยใหม่

แล้วเรื่องหน่วยและความแม่นยำล่ะ?

ลำดับ Moser-de Bruijn เกี่ยวข้องกับจำนวนเต็มล้วน:

พจน์ทั้งหมดเป็นจำนวนเต็มที่ไม่เป็นลบ (0, 1, 4, 5, 16 เป็นต้น)
ไม่มีหน่วย ทศนิยม หรือการปัดเศษ
ผลลัพธ์มีความถูกต้องทางคณิตศาสตร์—คุณได้จำนวนเต็มที่แม่นยำทุกครั้ง
การเติบโตเป็นแบบเลขชี้กำลัง: พจน์ที่ n สามารถเข้าถึงได้ถึงประมาณ 4^(⌊log₂(n)⌋+1) - 1

การเติบโตแบบเลขชี้กำลังนี้หมายความว่าลำดับจะมีขนาดใหญ่ขึ้นอย่างรวดเร็ว พจน์ที่ 20 มีค่าแล้ว 340 และที่พจน์ที่ 100 คุณกำลังจัดการกับตัวเลขหลายล้าน

การประยุกต์ใช้ในโลกแห่งความเป็นจริงและกรณีการใช้งาน

การศึกษาและการเรียนรู้

การสอนระบบตัวเลข: เมื่อฉันใช้เรื่องนี้ในห้องเรียน นักเรียนจะเข้าใจการแปลงฐานได้เร็วขึ้นมาก เมื่อพวกเขาสามารถทดลองกับลำดับ Moser-de Bruijn ซึ่งช่วยเชื่อมช่องว่างระหว่างระบบฐานสอง (ฐาน 2) และระบบตัวเลขที่ซับซ้อนมากขึ้น นักเรียนเห็นทันทีว่าการเปลี่ยนฐานจะเปลี่ยนความหนาแน่นของลำดับ

ความเข้าใจการดำเนินการบิตไวส์: นักเรียนวิทยาการคอมพิวเตอร์ได้รับประโยชน์จากการเห็นความเชื่อมโยงโดยตรงระหว่างการแสดงเลขฐานสองและลำดับทางคณิตศาสตร์ อัลกอริทึมนี้แสดงให้เห็นว่าการจัดการบิตแปลงเป็นวัตถุทางคณิตศาสตร์จริง—ไม่ใช่เพียงการดำเนินการนามธรรม

การวิจัยและการวิเคราะห์

การจัดหมวดหมู่และเซตที่ปราศจากผลบวก: นักวิจัยที่ศึกษาฐานการบวกใช้ลำดับเช่นนี้เพื่อสำรวจว่าเซตใดอนุญาตการแสดงที่ไม่ซ้ำกัน ลำดับ Moser-de Bruijn เป็นตัวอย่างมาตรฐานของเซตที่ทุกตัวเลขที่สามารถแสดงได้มีการแสดงเพียงหนึ่งแบบ

ทฤษฎีจำนวนการบวก: ลำดับนี้ช่วยสอบสวนคำถามเกี่ยวกับวิธีการแยกจำนวนเต็มออกเป็นผลบวก มันเกี่ยวข้องกับปัญหาในสารานุกรมออนไลน์ของลำดับจำนวนเต็ม (OEIS) ซึ่งได้รับการบันทึกเป็น A000695

การเขียนโปรแกรมเชิงปฏิบัติ

การออกแบบอัลกอริทึม: อัลกอริทึมการสร้างแสดงให้เห็นการสร้างลำดับที่มีประสิทธิภาพ คุณสามารถสร้างพจน์นับพันได้ด้วยภาระการคำนวณขั้นต่ำ ทำให้มีประโยชน์สำหรับการวัดประสิทธิภาพอัลกอริทึมหรือการสอนรูปแบบการเขียนโค้ดที่มีประสิทธิภาพ

งานการจดจำรูปแบบ: เมื่อทำงานกับเซตจำนวนเต็มที่มีความหนาแน่นต่ำหรือแบบแผนการบีบอัดข้อมูล การเข้าใจวิธีการทำงานของลำดับเช่น Moser-de Bruijn ช่วยให้ข้อมูลสำหรับการตัดสินใจเกี่ยวกับกลยุทธ์การเข้ารหัส

ลำดับเลขคณิตที่เกี่ยวข้อง

หากลำดับ Moser-de Bruijn สนใจคุณ ลำดับที่เกี่ยวข้องเหล่านี้นำเสนอรูปแบบที่คล้ายกันด้วยฐานหรือข้อจำกัดที่แตกต่างกัน:

ญาติโดยตรง

กำลังของ 2 (OEIS A000079): 1, 2, 4, 8, 16, 32... ฐานบวกที่เรียบง่ายที่สุด กำลังของ 2 ปรากฏขึ้นเพียงครั้งเดียว สร้างบล็อกพื้นฐานของเลขฐานสอง

จำนวนเต็มที่ไม่เป็นลบทั้งหมด (ผลบวกฐานสอง): 0, 1, 2, 3, 4, 5, 6, 7... เมื่อคุณอนุญาตให้มีผลบวมของกำลังของ 2 ที่แตกต่างกัน คุณจะได้จำนวนเต็มทุกแบบ—นั่นคือสิ่งที่การแสดงเลขฐานสองทำ

ผลบวมของกำลังของ 3 ที่แตกต่างกัน (OEIS A005836): 0, 1, 3, 4, 9, 10, 12, 13... แนวคิดเดียวกับ Moser-de Bruijn แต่ใช้กำลังของ 3 แทนที่ 4 เป็นจำนวนที่การแสดงฐานสามมีเพียง 0 และ 1

ตัวแปรที่น่าสนใจ

จำนวน Fibbinary (OEIS A003714): 0, 1, 2, 4, 5, 8, 9, 10... จำนวนที่มีเลขฐานสองไม่มี 1 ติดกัน เชื่อมโยงกับระบบจำนวน Fibonacci และทฤษฎีของ Zeckendorf

ลำดับ Stanley: อนาล็อกฐานสามของ Moser-de Bruijn—จำนวนที่ไม่มี 1 ในการแสดงฐานสาม (อนุญาตเพียง 0 และ 2)

แหล่งเรียนรู้เพิ่มเติม

สารานุกรมออนไลน์ของลำดับจำนวนเต็ม (OEIS) บันทึกลำดับหลายแสนลำดับ ค้นหาคำศัพท์เช่น "ฐานบวก" "เซตปลอดการบวก" หรือ "กำลังที่แตกต่างกัน" เพื่อค้นหาลำดับที่เกี่ยวข้อง ลำดับ Moser-de Bruijn เองอยู่ที่ A000695 ในฐานข้อมูล OEIS

ประวัติความเป็นมา

นักคณิตศาสตร์ผู้อยู่เบื้องหลังลำดับ

ลีโอ โมเซอร์ (1921-1970) และนิโคลาส โกเวิร์ต เดอ บรูจิน (1918-2012) ต่างก็มีส่วนสำคัญในการพัฒนาคณิตศาสตร์ แม้จะมีพื้นเพที่แตกต่างกัน โมเซอร์ นักคณิตศาสตร์ชาวออสเตรีย-แคนาดา ทำงานอย่างกว้างขวางในทฤษฎีจำนวน การจัดหมู่ และเรขาคณิต คุณอาจรู้จักเขาจากสมการเอิร์ดอช-โมเซอร์ เดอ บรูจิน นักคณิตศาสตร์ชาวดัตช์ ได้สร้างผลงานสำคัญในสาขาการจัดหมู่ ทฤษฎีกราฟ และวิทยาการคอมพิวเตอร์ ลำดับเดอ บรูจิน (ซึ่งแตกต่างจากลำดับนี้) เป็นพื้นฐานสำคัญในทฤษฎีการเข้ารหัสและยังคงใช้กันอย่างแพร่หลายในปัจจุบัน

ลำดับที่มีชื่อของพวกเขาเกิดขึ้นในช่วงทศวรรษ 1960 ระหว่างการสำรวจในทฤษฎีจำนวนเชิงบวก นักคณิตศาสตร์กำลังตั้งคำถามว่า: ชุดจำนวนเต็มใดที่สามารถแสดงจำนวนเต็มอื่นๆ ได้อย่างไม่กำกวม กำลังของ 4 ปรากฏว่าเป็นหนึ่งในชุดเช่นนั้น และลำดับโมเซอร์-เดอ บรูจินจับภาพผลบวกทั้งหมดที่สามารถสร้างได้

ทำไมเรื่องนี้จึงสำคัญ

ลำดับนี้อยู่ในการศึกษาฐานการบวก ฐานการบวก คือชุดของจำนวนเต็มที่สามารถสร้างจำนวนเต็มอื่นๆ ผ่านการบวก บางฐานอนุญาตให้มีการแสดงที่ไม่กำกวม (เช่น กำลังของ 4) ในขณะที่บางฐานไม่สามารถทำได้ การทำความเข้าใจว่าฐานใดมีคุณสมบัติอย่างไรยังคงเป็นพื้นที่วิจัยที่กำลังดำเนินอยู่ในทฤษฎีจำนวนเชิงบวก

คุณจะพบลำดับนี้ใน A000695 ใน OEIS ที่ซึ่งนักคณิตศาสตร์ได้บันทึกความเชื่อมโยงกับการแสดงเลขฐานสอง ระบบฐานสี่ และคุณสมบัติการจัดหมู่ วิทยาการคอมพิวเตอร์สมัยใหม่ได้ค้นพบการใช้งานใหม่ๆ โดยเฉพาะในอัลกอริทึมที่เกี่ยวข้องกับการจัดการบิตและการเข้ารหัสโครงสร้างข้อมูลแบบเบาบางอย่างมีประสิทธิภาพ

ตัวอย่างการใช้งานโค้ด

ต้องการสร้างตัวกำเนิดลำดับ Moser-de Bruijn ด้วยตัวเองหรือไม่? นี่คือการใช้งานที่มีประสิทธิภาพในภาษาโปรแกรมยอดนิยม แต่ละตัวอย่างประกอบด้วยตัวกำเนิดลำดับและฟังก์ชันทดสอบสมาชิก

1def moser_de_bruijn(n):
2    """สร้างพจน์ n แรกของลำดับ 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:  # ตรวจสอบว่าบิตที่มีความสำคัญน้อยสุดเป็น 1 หรือไม่
10                term += power
11            power *= 4
12            temp >>= 1  # เลื่อนบิตขวาเพื่อตรวจสอบบิตถัดไป
13        sequence.append(term)
14    return sequence
15
16# การใช้งานตัวอย่าง:
17terms = moser_de_bruijn(20)
18print("พจน์ 20 แรกของลำดับ Moser-de Bruijn:")
19print(terms)
20# ผลลัพธ์: [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    """ตรวจสอบว่าตัวเลขอยู่ในลำดับ 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# ตรวจสอบว่า 21 อยู่ในลำดับหรือไม่
32print(f"21 อยู่ในลำดับหรือไม่? {is_moser_de_bruijn(21)}")  # True
33print(f"22 อยู่ในลำดับหรือไม่? {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) {  // ตรวจสอบว่าบิตที่มีความสำคัญน้อยสุดเป็น 1 หรือไม่
9        term += power;
10      }
11      power *= 4;
12      temp >>= 1;  // เลื่อนบิตขวาเพื่อตรวจสอบบิตถัดไป
13    }
14    sequence.push(term);
15  }
16  return sequence;
17}
18
19// การใช้งานตัวอย่าง:
20const terms = moserDeBruijn(20);
21console.log("พจน์ 20 แรกของลำดับ Moser-de Bruijn:");
22console.log(terms);
23// ผลลัพธ์: [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// ตรวจสอบตัวเลขเฉพาะ
37console.log(`21 อยู่ในลำดับหรือไม่? ${isMoserDeBruijn(21)}`);  // true
38console.log(`22 อยู่ในลำดับหรือไม่? ${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) {  // ตรวจสอบว่าบิตที่มีความสำคัญน้อยสุดเป็น 1 หรือไม่
14                    term += power;
15                }
16                power *= 4;
17                temp >>= 1;  // เลื่อนบิตขวาเพื่อตรวจสอบบิตถัดไป
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("พจน์ 20 แรกของลำดับ Moser-de Bruijn:");
38        System.out.println(terms);
39        
40        System.out.println("21 อยู่ในลำดับหรือไม่? " + isMoserDeBruijn(21));  // true
41        System.out.println("22 อยู่ในลำดับหรือไม่? " + 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) {  // ตรวจสอบว่าบิตที่มีความสำคัญน้อยสุดเป็น 1 หรือไม่
12                term += power;
13            }
14            power *= 4;
15            temp >>= 1;  // เลื่อนบิตขวาเพื่อตรวจสอบบิตถัดไป
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 << "พจน์ 20 แรกของลำดับ Moser-de Bruijn:" << std::endl;
36    for (int term : terms) {
37        std::cout << term << " ";
38    }
39    std::cout << std::endl;
40    
41    std::cout << "21 อยู่ในลำดับหรือไม่? " << (isMoserDeBruijn(21) ? "true" : "false") << std::endl;
42    std::cout << "22 อยู่ในลำดับหรือไม่? " << (isMoserDeBruijn(22) ? "true" : "false") << std::endl;
43    
44    return 0;
45}
46

ข้อสังเกตสำคัญในการใช้งาน

การใช้งานทั้งหมดนี้ใช้รูปแบบเดียวกัน: ใช้การดำเนินการบิตเพื่ออ่านการแทนทวิภาค แล้วสร้างผลรวมของกำลังของ 4 ฟังก์ชันทดสอบสมาชิกใช้วิธีฐาน 4 - ตรวจสอบว่าหลักเลขถูกจำกัดเฉพาะ 0 และ 1

ในแง่ของประสิทธิภาพ การใช้งานเหล่านี้มีประสิทธิภาพสูง ความซับซ้อนของเวลาคือ O(n × log n) สำหรับการสร้าง n พจน์ เนื่องจากแต่ละพจน์ต้องตรวจสอบ O(log i) บิต การตรวจสอบสมาชิกสำหรับตัวเลขเดียวคือ O(log N) โดย N คือตัวเลขที่กำลังทดสอบ

ตัวอย่างตัวเลขโดยละเอียด

ตารางด้านล่างแสดงพจน์ 32 พจน์แรกพร้อมการแจกแจงอย่างสมบูรณ์ สังเกตว่าการแสดงฐาน 4 มีเพียง 0 และ 1 และวิธีการแยกส่วนสอดคล้องกับดัชนีฐานสอง:

ดัชนี	พจน์	การแยกส่วน	ฐาน 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

การตรวจสอบอย่างละเอียดที่พจน์ 21

มาแยกพจน์ 21 อย่างสมบูรณ์:

ค่าทศนิยม: 21
การแสดงฐาน 4: 111 (ใช้เพียง 0 และ 1 ✓)
ดัชนีในลำดับ: 7
ดัชนีฐานสอง: 111 (ฐานสองของ 7)
การแยกส่วน: 21 = 16 + 4 + 1 = 4² + 4¹ + 4⁰

เห็นรูปแบบหรือยัง? ดัชนีฐานสอง (111) แมปโดยตรงกับยกกำลังของ 4 ที่จะรวม แต่ละบิต "1" บอกคุณว่าให้รวมยกกำลังนั้น

การสังเกตรูปแบบการเติบโต

ลำดับเติบโตแบบเลขชี้กำลัง—พจน์ที่ n โดยประมาณสัดส่วนกับ 4^(log₂(n)) ความหมายในทางปฏิบัติคือ:

ที่พจน์ 10 คุณอยู่ที่ 68
ที่พจน์ 20 คุณถึง 272
ที่พจน์ 100 คุณอยู่ในหลักล้าน

เมื่อตัวเลขใหญ่ขึ้น ลำดับจะห่างมากขึ้น คุณข้ามจำนวนเต็มมากขึ้น แม้จะมีความห่าง แต่ลำดับนี้มีพจน์อนันต์—มันไม่หยุดการเติบโตเลย

แหล่งอ้างอิงและการอ่านเพิ่มเติม

แหล่งปฐมภูมิ

OEIS A000695 - ลำดับ Moser-de Bruijn สารานุกรมออนไลน์ของลำดับจำนวนเต็ม ข้อมูลและคุณสมบัติที่ครอบคลุมของลำดับ
เดอ บรูจิน, เอ็น จี "เกี่ยวกับฐานสำหรับชุดจำนวนเต็ม" วารสารคณิตศาสตร์ เดอบรีเซน เล่มที่ 1, 2493, หน้า 232-242 บทความพื้นฐานที่กำหนดคุณสมบัติสำคัญของฐานการบวก
โมเซอร์, เลโอ "การประยุกต์ใช้อนุกรมการสร้าง" นิตยสารคณิตศาสตร์ เล่มที่ 35, ฉบับที่ 1, 2505, หน้า 37-38 งานเริ่มแรกที่สำรวจฟังก์ชันการสร้างของลำดับ

บริบทคณิตศาสตร์เพิ่มเติม

สโตลาร์สกี, เคนเนธ บี "ผลบวกกำลังและเอ็กซ์โพเนนเชียลของผลบวกเลขประจำหลักที่เกี่ยวข้องกับความคู่ของสัมประสิทธิ์ทวินาม" วารสาร SIAM ว่าด้วยคณิตศาสตร์ประยุกต์ เล่มที่ 32, ฉบับที่ 4, 2520, หน้า 717-730 สำรวจคุณสมบัติของผลบวกเลขประจำหลักที่เกี่ยวข้องกับลำดับเช่น Moser-de Bruijn
อัลลูช, ฌอง-ปอล, และ เจฟฟรีย์ ชาลิท ลำดับอัตโนมัติ: ทฤษฎี การประยุกต์ การขยาย สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์, 2546 บทความครอบคลุมเกี่ยวกับลำดับอัตโนมัติรวมถึงความเชื่อมโยงกับลำดับ Moser-de Bruijn

แนวคิดที่เกี่ยวข้อง

ชุดปลอดผลบวก - วิกิพีเดีย พื้นหลังเกี่ยวกับบริบทคณิตศาสตร์ของทฤษฎีจำนวนการบวก
ฐานการบวก - วิกิพีเดีย ภาพรวมของชุดที่สามารถแสดงจำนวนเต็มเป็นผลบวก

คำถามที่พบบ่อย

Moser-de Bruijn sequence คืออะไร?

ลำดับนี้มีการประยุกต์ใช้หลายประการ: การวิจัยทฤษฎีจำนวนที่สำรวจฐานการบวก, งานคอมบินาทอริกส์เกี่ยวกับชุดที่ปลอดจากผลบวก, การศึกษาวิทยาการคอมพิวเตอร์ (โดยเฉพาะการสอนการดำเนินการบิตและอัลกอริทึมที่มีประสิทธิภาพ), และการวิเคราะห์รูปแบบทางคณิตศาสตร์ นอกจากนี้ยังเป็นเครื่องมือสอนที่ดีในการทำความเข้าใจความสัมพันธ์ระหว่างเลขฐานต่าง ๆ

จะสร้างลำดับ Moser-de Bruijn ได้อย่างไร?

เริ่มจากดัชนี n ตั้งแต่ 0 แปลงเป็นเลขฐานสอง จากนั้นแทนที่แต่ละบิต "1" ด้วยกำลังของ 4 ตัวอย่างเช่น ดัชนี 5 มีการแสดงเลขฐานสอง 101 ดังนั้นคุณคำนวณ 4² + 4⁰ = 16 + 1 = 17 นั่นคือพจน์ที่ 5 (นับจากดัชนี 0)

อะไรที่ทำให้ Moser-de Bruijn sequence พิเศษ?

ทุกตัวเลขในลำดับมีคุณสมบัติพิเศษ: การแสดงเลขฐาน 4 ของมันประกอบด้วย 0 และ 1 เท่านั้น - ไม่มี 2 หรือ 3 ซึ่งหมายความว่าคุณสามารถสร้างแต่ละพจน์โดยการบวกกำลังของ 4 โดยแต่ละกำลังปรากฏมากที่สุดเพียงครั้งเดียว เหมือนกับเลขฐานสอง แต่ใช้กำลังของ 4 แทนกำลังของ 2

จะตรวจสอบได้อย่างไรว่าตัวเลขเฉพาะอยู่ในลำดับ?

แปลงตัวเลขของคุณเป็นเลขฐาน 4 และดูตัวเลข หากคุณเห็นเฉพาะ 0 และ 1 แสดงว่าอยู่ในลำดับ หากมีตัวเลข 2 หรือ 3 แสดงว่าไม่อยู่ในลำดับ ตัวอย่างเช่น 21 ในเลขฐาน 4 คือ 111 (มี 1 และ 0 ทั้งหมด) ดังนั้นจึงอยู่ในลำดับ แต่ 22 ในเลขฐาน 4 คือ 112 (มี 2) ดังนั้นจึงไม่อยู่ในลำดับ

สูตรสำหรับพจน์ที่ n คืออะไร?

พจน์ที่ n M(n) เป็นไปตามสูตรนี้: M(n) = Σ(b_i × 4^i) โดย b_i แสดงถึงเลขฐานสองของ n กล่าวอย่างง่าย: เขียน n ในเลขฐานสอง แล้วสำหรับแต่ละตำแหน่งที่มี 1 ให้บวกกำลังของ 4 ที่สอดคล้อง

ลำดับนี้มีจำนวนจำกัดหรือไม่?

ไม่ มีต่อไปตลอดกาล มีพจน์ในลำดับ Moser-de Bruijn เป็นอนันต์ อย่างไรก็ตาม เมื่อคุณไปสูงขึ้น ลำดับจะกลายเป็นบางลง - คุณข้ามจำนวนเต็มปกติระหว่างสมาชิกลำดับมากขึ้น

แตกต่างจากลำดับฐานสองอย่างไร?

ลำดับฐานสอง (ผลบวกของกำลังของ 2) สามารถแสดงจำนวนเต็มที่ไม่เป็นลบทั้งหมด - นั่นคือสิ่งที่การแสดงเลขฐานสองทำ ลำดับ Moser-de Bruijn ใช้กำลังของ 4 แทน ซึ่งสร้างชุดที่บางมาก จำนวนเต็มส่วนใหญ่ไม่ปรากฏในลำดับ Moser-de Bruijn

ใครค้นพบลำดับนี้?

Leo Moser (1921-1970) นักคณิตศาสตร์ชาวออสเตรีย-แคนาดา และ Nicolaas Govert de Bruijn (1918-2012) นักคณิตศาสตร์ชาวดัตช์ ได้ศึกษาลำดับนี้อย่างลึกซึ้งในช่วงทศวรรษ 1960 เป็นส่วนหนึ่งของการวิจัยทฤษฎีจำนวนการบวก ลำดับนี้จึงมีชื่อตามนักคณิตศาสตร์ทั้งสอง

พร้อมที่จะสำรวจหรือยัง?

เครื่องมือนี้ทำงานทั้งหมดในเบราว์เซอร์ของคุณ—ไม่ต้องติดตั้ง ไม่ต้องลงทะเบียน ไม่ต้องรอคอย ไม่ว่าคุณจะเป็นนักเรียนที่กำลังเรียนรู้เกี่ยวกับระบบตัวเลข นักวิจัยที่สำรวจฐานการบวก หรือแค่มีความอยากรู้อยากเห็นทางคณิตศาสตร์ คุณสามารถสร้างพจน์ได้ทันทีและดูรูปแบบด้วยตัวเอง ลองสร้างปริมาณที่แตกต่างกันเพื่อสังเกตว่าลำดับเติบโตอย่างไรและจำนวนเต็มใดบ้างที่ถูกรวมเข้าไป