تولیدکننده دنباله موسر-دی بروین

توالی موسر-دی بروین چیست؟

توالی موسر-دی بروین شامل اعدادی است که می‌توان آن‌ها را به صورت مجموع توان‌های متمایز 4 بیان کرد. به نام ریاضیدانان لئو موسر و نیکولاس گوورت دی بروین، توالی به این صورت شروع می‌شود: 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 کار می‌کنید. این یک توالی بسیار متراکم‌تر ایجاد می‌کند زیرا اکثر اعداد صحیح حذف می‌شوند.

چگونگی استفاده از تولیدکننده دنباله موسر-دی بروین

استفاده از این تولیدکننده بسیار ساده است:

۱. تعداد عبارات مورد نظر خود را وارد کنید (در صورت خالی گذاشتن، پیش‌فرض ۲۰ عبارت است) ۲. برای محاسبه دنباله، روی "تولید" کلیک کنید ۳. نتایج شما بلافاصله در فهرستی زیر ظاهر می‌شوند ۴. می‌خواهید اعداد متفاوتی داشته باشید؟ فقط ورودی را تغییر دهید و دوباره تولید کنید

محاسبات کاملاً در مرورگر شما با استفاده از جاوااسکریپت انجام می‌شود، بنابراین هیچ تأخیری در سرور یا وابستگی به اینترنت وجود ندارد - سریع است و پس از بارگذاری صفحه، به صورت آفلاین کار می‌کند.

اعتبارسنجی ورودی و محدودیت‌ها

تولیدکننده ورودی شما را برای جلوگیری از خطا اعتبارسنجی می‌کند:

باید یک عدد صحیح مثبت باشد (بدون اعشار یا مقادیر منفی)
حداکثر ۱۰۰۰ عبارت برای جلوگیری از کندی مرورگر
ورودی‌های غیرعددی پیام خطا را فعال می‌کنند
در صورت خالی گذاشتن، به طور پیش‌فرض ۲۰ عبارت دریافت می‌کنید

چرا محدودیت ۱۰۰۰ عبارت؟ اگرچه الگوریتم کارآمد است، تولید هزاران عبارت می‌تواند حافظه مرورگر را به ویژه در دستگاه‌های تلفن همراه تحت فشار قرار دهد. در عمل، برای اکثر تحلیل‌های ریاضی یا اهداف آموزشی، به ندرت به بیش از ۱۰۰-۲۰۰ عبارت نیاز خواهید داشت.

درک دنباله موسر-دی بروین

می‌توان دنباله موسر-دی بروین را به سه روش معادل تعریف کرد که هر کدام بینش‌های متفاوتی ارائه می‌دهند:

سه روش تعریف دنباله

فرم جمعی (توان‌های 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

روش تناظر باینری همان چیزی است که این تولیدکننده در زیر پوسته استفاده می‌کند - از نظر محاسباتی کارآمد است زیرا عملیات بیتی سریع هستند.

محاسبه دنباله موسر-دی بروین

الگوریتم پشت تولیدکننده

تولیدکننده از تناظر باینری استفاده می‌کند زیرا سریع و ساده است:

فرآیند گام به گام:

حلقه زدن از هر اندیس i از 0 تا n-1 (n تعداد عبارات درخواستی شماست)
برای اندیس i، نمایش باینری آن را نگاه کنید
برای هر بیت "1" در موقعیت j، 4^j را به مجموع جاری اضافه کنید
آن مجموع عبارت i-ام می‌شود

مثال عملی: یافتن عبارت ششم (اندیس 5)

بیایید M(5) را گام به گام محاسبه کنیم:

اندیس 5 در باینری: 101
بیت 0 (سمت راست) = 1 → اضافه کنید 4⁰ = 1
بیت 1 (میانی) = 0 → چیزی اضافه نکنید
بیت 2 (سمت چپ) = 1 → اضافه کنید 4² = 16
نتیجه نهایی: 1 + 16 = 17

این روش به خوبی مقیاس‌پذیر است. برای اندیس‌های بزرگ، اساساً در حال انجام عملیات بیت شیفت و جمع هستید - عملیاتی که پردازنده‌های مدرن بسیار سریع انجام می‌دهند.

آزمایش تعلق یک عدد به دنباله

می‌خواهید بررسی کنید آیا یک عدد خاص در دنباله موسر-دی بروین است؟ از آزمایش پایه 4 استفاده کنید:

عدد خود را به پایه 4 تبدیل کنید
ارقام را اسکن کنید - آیا فقط 0 و 1 می‌بینید؟
اگر بله، در دنباله است. اگر 2 یا 3 را مشاهده کردید، نیست.

مثال: آیا 85 در دنباله است؟

85 در پایه 4: 1111 (یعنی 64 + 16 + 4 + 1)
فقط شامل 1 و 0 می‌شود → بله، 85 در دنباله است

مثال معکوس: آیا 90 در دنباله است؟

90 در پایه 4: 1122
شامل رقم 2 می‌شود → خیر، 90 در دنباله نیست

تولیدکننده این کار را با استفاده از عملگرهای بیتی جاوااسکریپت انجام می‌دهد که بومی زبان هستند و در مرورگرهای مدرن بسیار بهینه شده‌اند.

درباره واحدها و دقت

دنباله موسر-دی بروین با اعداد صحیح خالص سر و کار دارد:

تمام عبارات اعداد صحیح غیر منفی هستند (0، 1، 4، 5، 16 و غیره)
بدون واحد، اعشار یا گرد کردن
نتایج دقیقاً ریاضی هستند - هر بار اعداد صحیح دقیق دریافت می‌کنید
رشد نمایی است: عبارت n-ام می‌تواند تا حدود 4^(⌊log₂(n)⌋+1) - 1 برسد

این رشد نمایی یعنی دنباله به سرعت بزرگ می‌شود. عبارت بیستم از همین الان 340 است و در عبارت صدم با اعدادی در میلیون‌ها سر و کار دارید.

کاربردهای دنیای واقعی و موارد استفاده

آموزش و یادگیری

آموزش سیستم‌های عددی: زمانی که این را در کلاس‌ها استفاده کرده‌ام، دانش‌آموزان تبدیل پایه‌ها را بسیار سریع‌تر درک می‌کنند وقتی می‌توانند با دنباله موسر-دی بروین بازی کنند. این پلی بین باینری (پایه ۲) و سیستم‌های عددی پیچیده‌تر است. دانش‌آموزان بلافاصله می‌بینند که تغییر پایه چگونه چگالی دنباله را تغییر می‌دهد.

درک عملیات بیتی: دانشجویان علوم کامپیوتر از دیدن ارتباط مستقیم بین نمایش باینری و دنباله‌های ریاضی سود می‌برند. الگوریتم نشان می‌دهد که دستکاری بیت چگونه به اشیاء ریاضی واقعی ترجمه می‌شود - نه فقط عملیات انتزاعی.

تحقیق و تحلیل

ترکیبیات و مجموعه‌های بدون جمع: محققانی که پایه‌های جمعی را مطالعه می‌کنند از دنباله‌هایی مانند این برای کاوش مجموعه‌هایی که نمایش‌های یکتا را مجاز می‌دانند استفاده می‌کنند. دنباله موسر-دی بروین مثال کلاسیکی از مجموعه‌ای است که در آن هر عدد قابل نمایش دقیقاً یک نمایش دارد.

نظریه اعداد جمعی: این دنباله به بررسی سؤالاتی در مورد چگونگی تجزیه اعداد صحیح به مجموع‌ها کمک می‌کند. این مرتبط با مسائلی در دانشنامه آنلاین دنباله‌های صحیح (OEIS) است، که در آن به عنوان A000695 فهرست شده است.

برنامه‌نویسی عملی

طراحی الگوریتم: الگوریتم تولید، ساخت کارآمد دنباله را نشان می‌دهد. می‌توانید هزاران جمله را با حداقل بار محاسباتی تولید کنید، که آن را برای معیارسنجی الگوریتم یا آموزش الگوهای کد کارآمد مفید می‌سازد.

کارهای تشخیص الگو: هنگام کار با مجموعه‌های صحیح تنک یا طرح‌های فشرده‌سازی داده، درک رفتار دنباله‌هایی مانند موسر-دی بروین به تصمیم‌گیری درباره راهبردهای کدگذاری کمک می‌کند.

توالی‌های ریاضی مرتبط

اگر توالی موسر-دی بروین برایتان جذاب است، این توالی‌های مرتبط الگوهای مشابهی با مبناها یا محدودیت‌های متفاوت ارائه می‌دهند:

خویشاوندان مستقیم

توان‌های 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... مفهوم مشابه موسر-دی بروین، اما با استفاده از توان‌های 3 به جای 4. این‌ها اعدادی هستند که در نمایش پایه 3 فقط 0 و 1 دارند.

گونه‌های جالب

اعداد فیبری (OEIS A003714): 0، 1، 2، 4، 5، 8، 9، 10... اعدادی که در نمایش دودویی آنها 1های متوالی وجود ندارد. مرتبط با سیستم‌های اعداد فیبوناچی و قضیه زکندورف.

توالی استنلی: آنالوگ پایه 3 موسر-دی بروین—اعدادی که در نمایش پایه 3 آنها 1 وجود ندارد (فقط 0 و 2 مجاز هستند).

برای اطلاعات بیشتر

دانشنامه آنلاین توالی‌های صحیح (OEIS) صدها هزار توالی را فهرست می‌کند. برای یافتن توالی‌های مرتبط، عباراتی مانند "مبنای جمعی"، "مجموعه بدون جمع" یا "توان‌های متمایز" را جستجو کنید. خود توالی موسر-دی بروین در پایگاه داده OEIS با شناسه A000695 موجود است.

پیشینه تاریخی

ریاضیدانان پشت توالی

لئو موسر (۱۹۲۱-۱۹۷۰) و نیکولاس گوورت دی بروین (۱۹۱۸-۲۰۱۲) هر دو مشارکت‌های ماندگاری در ریاضیات داشتند، اگرچه از پیش‌زمینه‌های متفاوتی می‌آمدند. موسر، یک ریاضیدان اتریشی-کانادایی، به طور گسترده در نظریه اعداد، ترکیبیات و هندسه کار کرد - شاید نام او را از معادله اردوش-موسر بشناسید. دی بروین، یک ریاضیدان هلندی، اثر خود را در ترکیبیات، نظریه گراف و علوم کامپیوتر گذاشت. توالی‌های دی بروین او (متفاوت از این توالی) در نظریه کدگذاری بنیادی هستند و همچنان امروزه به طور گسترده‌ای استفاده می‌شوند.

توالی نام‌دار آنها در دهه ۱۹۶۰ میلادی در تحقیقات نظریه اعداد جمعی ظهور کرد. ریاضیدانان این سوال را مطرح می‌کردند: کدام مجموعه‌های اعداد صحیح اجازه می‌دهند تا اعداد صحیح دیگر را به صورت یکتا به عنوان مجموع نشان داد؟ توان‌های ۴ یکی از چنین مجموعه‌هایی بود، و توالی موسر-دی بروین تمام مجموع‌های ممکن را نشان می‌دهد.

چرا این مهم است

این توالی در مطالعه گسترده‌تر مبانی جمعی - مجموعه‌های اعداد صحیحی که می‌توانند اعداد دیگر را از طریق جمع بسازند - قرار دارد. برخی از مبانی اجازه نمایش‌های یکتا را می‌دهند (مانند توان‌های ۴)، در حالی که برخی دیگر چنین نمی‌کنند. درک اینکه کدام مبانی چه خواصی دارند همچنان یک حوزه تحقیقاتی فعال در نظریه اعداد جمعی است.

این توالی را می‌توانید در A000695 در OEIS پیدا کنید، جایی که ریاضیدانان ارتباطات آن را با نمایش باینری، سیستم‌های چهارگانه (پایه ۴) و خواص ترکیبیاتی مستند کرده‌اند. علوم کامپیوتر مدرن کاربردهای جدیدی برای آن پیدا کرده، به‌ویژه در الگوریتم‌های مرتبط با دستکاری بیت و کدگذاری کارآمد ساختارهای داده متراکم.

نمونه‌های پیاده‌سازی کد

آیا می‌خواهید تولیدکننده دنباله موسر-دی بروین را خودتان پیاده‌سازی کنید؟ در اینجا پیاده‌سازی‌های کارآمدی در زبان‌های برنامه‌نویسی محبوب آورده شده است. هر مثال شامل یک تولیدکننده دنباله و یک تابع آزمون عضویت است.

1def moser_de_bruijn(n):
2    """تولید n جمله اول دنباله موسر-دی بروین."""
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 جمله دنباله موسر-دی بروین:")
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    """بررسی اینکه آیا یک عدد در دنباله موسر-دی بروین است."""
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 جمله دنباله موسر-دی بروین:");
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 جمله دنباله موسر-دی بروین:");
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 جمله دنباله موسر-دی بروین:" << std::endl;
36    for (int term : terms) {
37        std::cout << term << " ";
38    }
39    std::cout << std::endl;
40    
41    std::cout << "آیا 21 در دنباله است؟ " << (isMoserDeBruijn(21) ? "بله" : "خیر") << std::endl;
42    std::cout << "آیا 22 در دنباله است؟ " << (isMoserDeBruijn(22) ? "بله" : "خیر") << std::endl;
43    
44    return 0;
45}
46

نکات کلیدی پیاده‌سازی

تمام این پیاده‌سازی‌ها از یک الگوی مشابه پیروی می‌کنند: استفاده از عملیات بیتی برای خواندن نمایش باینری یک اندیس، سپس ساخت مجموع متناظر توان‌های 4. توابع آزمون عضویت از رویکرد پایه 4 استفاده می‌کنند - بررسی اینکه آیا ارقام محدود به 0 و 1 هستند.

از نظر کارایی، این پیاده‌سازی‌ها بسیار کارآمد هستند. پیچیدگی زمانی برای تولید n جمله O(n × log n) است، زیرا هر جمله نیاز به بررسی O(log i) بیت دارد. بررسی عضویت برای یک عدد واحد O(log N) است، جایی که N عدد مورد آزمون است.

مثال‌های عددی دقیق

جدول زیر اولین ۳۲ عبارت را با تجزیه کامل نشان می‌دهد. توجه کنید که نمایش پایه-۴ فقط شامل ۰ و ۱ است و تجزیه مستقیماً به اندیس‌های باینری نگاشت می‌شود:

اندیس	عبارت	تجزیه	پایه-۴
۰	۰	۰	۰
۱	۱	۴⁰	۱
۲	۴	۴¹	۱۰
۳	۵	۴¹ + ۴⁰	۱۱
۴	۱۶	۴²	۱۰۰
۵	۱۷	۴² + ۴⁰	۱۰۱
۶	۲۰	۴² + ۴¹	۱۱۰
۷	۲۱	۴² + ۴¹ + ۴⁰	۱۱۱
۸	۶۴	۴³	۱۰۰۰
۹	۶۵	۴³ + ۴⁰	۱۰۰۱
۱۰	۶۸	۴³ + ۴¹	۱۰۱۰
۱۱	۶۹	۴³ + ۴¹ + ۴⁰	۱۰۱۱
۱۲	۸۰	۴³ + ۴²	۱۱۰۰
۱۳	۸۱	۴³ + ۴² + ۴⁰	۱۱۰۱
۱۴	۸۴	۴³ + ۴² + ۴¹	۱۱۱۰
۱۵	۸۵	۴³ + ۴² + ۴¹ + ۴⁰	۱۱۱۱
۱۶	۲۵۶	۴⁴	۱۰۰۰۰
۱۷	۲۵۷	۴⁴ + ۴⁰	۱۰۰۰۱
۱۸	۲۶۰	۴⁴ + ۴¹	۱۰۰۱۰
۱۹	۲۶۱	۴⁴ + ۴¹ + ۴⁰	۱۰۰۱۱
۲۰	۲۷۲	۴⁴ + ۴²	۱۰۱۰۰
۲۱	۲۷۳	۴⁴ + ۴² + ۴⁰	۱۰۱۰۱
۲۲	۲۷۶	۴⁴ + ۴² + ۴¹	۱۰۱۱۰
۲۳	۲۷۷	۴⁴ + ۴² + ۴¹ + ۴⁰	۱۰۱۱۱
۲۴	۳۲۰	۴⁴ + ۴³	۱۱۰۰۰
۲۵	۳۲۱	۴⁴ + ۴³ + ۴⁰	۱۱۰۰۱
۲۶	۳۲۴	۴⁴ + ۴³ + ۴¹	۱۱۰۱۰
۲۷	۳۲۵	۴⁴ + ۴³ + ۴¹ + ۴⁰	۱۱۰۱۱
۲۸	۳۳۶	۴⁴ + ۴³ + ۴²	۱۱۱۰۰
۲۹	۳۳۷	۴⁴ + ۴³ + ۴² + ۴⁰	۱۱۱۰۱
۳۰	۳۴۰	۴⁴ + ۴³ + ۴² + ۴¹	۱۱۱۱۰
۳۱	۳۴۱	۴⁴ + ۴³ + ۴² + ۴¹ + ۴⁰	۱۱۱۱۱

نگاه دقیق به عبارت ۲۱

بیایید عبارت ۲۱ را به طور کامل تجزیه کنیم:

مقدار دهدهی: ۲۱
نمایش پایه-۴: ۱۱۱ (فقط از ۰ و ۱ استفاده می‌کند ✓)
اندیس در دنباله: ۷
اندیس باینری: ۱۱۱ (باینری برای ۷)
تجزیه: ۲۱ = ۱۶ + ۴ + ۱ = ۴² + ۴¹ + ۴⁰

آیا الگو را می‌بینید؟ اندیس باینری (۱۱۱) مستقیماً به توان‌های ۴ که باید شامل شوید نگاشت می‌شود. هر بیت "۱" به شما می‌گوید که آن توان را شامل کنید.

مشاهده الگوی رشد

دنباله به صورت نمایی رشد می‌کند - عبارت n-ام تقریباً متناسب با ۴^(log₂(n)) است. این به چه معنای عملی است؟

تا عبارت ۱۰، به ۶۸ می‌رسید
تا عبارت ۲۰، به ۲۷۲ می‌رسید
تا عبارت ۱۰۰، در میلیون‌ها خواهید بود

همانطور که اعداد بزرگتر می‌شوند، دنباله به تدریج متراکم‌تر می‌شود. شما اعداد بیشتری را رد می‌کنید. با وجود این تُنُکی، دنباله شامل عبارات نامحدودی است - هرگز متوقف نمی‌شود.

مراجع و مطالعات بیشتر

منابع اصلی

OEIS A000695 - دنباله موسر-دی بروین. دانشنامه آنلاین دنباله‌های صحیح. داده‌ها و ویژگی‌های جامع دنباله.
دی بروین، ن. گ. "درباره مبناها برای مجموعه اعداد صحیح." انتشارات ریاضی دبرسن، جلد 1، 1950، صص 232-242. مقاله بنیادی که خصوصیات کلیدی مبناهای جمعی را تعیین می‌کند.
موسر، لئو. "کاربردی از سری‌های تولید." مجله ریاضی، جلد 35، شماره 1، 1962، صص 37-38. کار اولیه در کاوش توابع تولیدکننده دنباله.

زمینه ریاضی اضافی

استولارسکی، کنت ب. "مجموع‌های توان و نمایی از مجموع‌های رقمی مرتبط با پاریته ضرایب دوجمله‌ای." مجله کاربردی SIAM در ریاضیات، جلد 32، شماره 4، 1977، صص 717-730. کاوش خصوصیات مجموع رقمی مرتبط با دنباله‌هایی مانند موسر-دی بروین.
آلوش، ژان-پل، و جفری شالیت. دنباله‌های خودکار: نظریه، کاربردها، تعمیم‌ها. انتشارات دانشگاه کمبریج، 2003. فصل مربوط به دنباله‌های خودکار شامل ارتباطات با دنباله موسر-دی بروین.

مفاهیم مرتبط

مجموعه‌های بدون جمع - ویکی‌پدیا. زمینه ریاضی گسترده‌تر نظریه عددی جمعی.
مبناهای جمعی - ویکی‌پدیا. نمای کلی از مجموعه‌هایی که می‌توانند اعداد صحیح را به صورت مجموع نشان دهند.

سؤالات متداول

دنباله موسر-دی بروین چه کاربردی دارد؟

این دنباله کاربردهای متعددی دارد: تحقیقات نظریه اعداد در کاوش پایه‌های جمعی، کار در ترکیبیات روی مجموعه‌های بدون جمع، آموزش علوم کامپیوتر (به‌ویژه برای آموزش عملیات بیتی و الگوریتم‌های کارآمد)، و تحلیل الگوهای ریاضی. همچنین ابزار آموزشی عالی برای درک ارتباط بین پایه‌های مختلف اعداد است.

چگونه دنباله موسر-دی بروین را تولید می‌کنیم؟

برای هر اندیس n از 0 شروع کنید، آن را به باینری تبدیل کنید، سپس هر بیت "1" را با توان متناظر 4 جایگزین کنید. برای مثال، اندیس 5 نمایش باینری 101 دارد، بنابراین محاسبه می‌کنیم 4² + 4⁰ = 16 + 1 = 17. این پنجمین عبارت (از اندیس 0) است.

چه چیزی دنباله موسر-دی بروین را ویژه می‌کند؟

هر عدد در دنباله خاصیت متمایزی دارد: نمایش پایه 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 را اضافه کنید.

آیا دنباله نامحدود است؟

بله، برای همیشه ادامه دارد. تعداد نامحدودی عبارت در دنباله موسر-دی بروین وجود دارد. با این حال، هر چه بالاتر می‌روید، دنباله متراکم‌تر می‌شود - شما بین اعضای دنباله اعداد صحیح بیشتری را رد می‌کنید.

این با دنباله‌های باینری چه تفاوتی دارد؟

دنباله‌های باینری (مجموع توان‌های 2) می‌توانند هر عدد غیر منفی را نشان دهند - این همان کاری است که نمایش باینری انجام می‌دهد. دنباله موسر-دی بروین از توان‌های 4 استفاده می‌کند که مجموعه‌ای بسیار متراکم‌تر ایجاد می‌کند. اکثر اعداد در دنباله موسر-دی بروین ظاهر نمی‌شوند.

این دنباله را چه کسی کشف کرد؟

لئو موسر (1921-1970)، یک ریاضیدان اتریشی-کانادایی، و نیکولاس گوورت دی بروین (1918-2012)، یک ریاضیدان هلندی، هر دو این دنباله را در دهه 1960 به عنوان بخشی از تحقیقات در نظریه اعداد جمعی به طور عمیق مطالعه کردند. دنباله به نام هر دوی آنها نامگذاری شده است.

آماده به کاوش؟

این تولیدکننده کاملاً در مرورگر شما اجرا می‌شود - بدون نصب، بدون ثبت‌نام، بدون انتظار. چه دانشجویی که در حال یادگیری سیستم‌های عددی هستید، چه محققی که پایه‌های جمعی را بررسی می‌کنید، یا فقط از نظر ریاضی کنجکاو هستید، می‌توانید بلافاصله عبارات را تولید کنید و الگوها را خودتان مشاهده کنید. تلاش کنید با تولید مقادیر مختلف، رشد دنباله را مشاهده کنید و ببینید کدام اعداد صحیح شامل می‌شوند.

تولیدکننده دنباله موسر-دی بروین | ماشین حساب توان‌های 4

دنباله تولید شده

مستندات