دنباله موزر- دی بروژن

توسط علی رضا نقش نیلچی | جمعه سی ام خرداد ۱۳۹۹ | 19:10

از ویکیپدیا، دانشنامه آزاد

جدول اضافی برای ${\ نمایشگر x + 2y$ جایی که $ایکس$ و $ی$ هر دو متعلق به دنباله Moser – de Bruijn هستند و منحنی Z- مرتبه ای که مبالغ را به ترتیب عددی به هم وصل می کند

در نظریه اعداد ، توالی Moser – de Bruijn یک دنباله عدد صحیح است که به نامهای Leo Moser و Nicolaas Govert de Bruijn نامگذاری شده و از مجموع قدرتهای مشخص 4 تشکیل شده است.

0 ، 1 ، 4 ، 5 ، 16 ، 17 ، 20 ، 21 ، 64 ، 65 ، 68 ، 69 ، 80 ، 81 ، 84 ، 85 ، 256 ، ... (دنباله A000695 در OEIS )

به عنوان مثال ، 69 به این دنباله تعلق دارند زیرا این برابر با 64 + 4 + 1 است ، این مجموع سه قدرت مجزا از 4 است.

فهرست

نمایش های دودویی و مرتبط [ ویرایش ]

تعریف دیگر از توالی Moser-de Bruijn این است که این دنباله مرتب شده از اعدادی است که نمایش دودویی دارای ارقام nonzero فقط در موقعیتهای مساوی است. به عنوان مثال ، 69 متعلق به دنباله است ، زیرا نمایش دودویی آن 1000101 2 دارای ارقام غیرزرو در موقعیت هایی برای 2 6 ، 2 2 و 2 0 است که همه آنها حتی دارای منعکس کننده هستند. اعداد موجود در دنباله را می توان به عنوان عددی توصیف کرد که بازنمایش پایه 4 آنها فقط از ارقام 0 یا 1 استفاده می کند. [1]برای تعدادی در این دنباله ، نمایانگر پایه -4 را می توان با جستجوی رقم های باینری در موقعیت های عجیب و غریب ، که همه باید صفر باشد ، از نمایه دودویی پیدا کرد. روش دیگر برای دیدن آن این است که این ها اعدادی هستند که نمایش شش ضلعی آنها فقط شامل ارقام 0 ، 1 ، 4 ، 5 است. به عنوان مثال ، 69 = 1011 4 = 45 16 .

به طور برابر ، آنها اعدادی هستند که نمایشهای باینری و منفی آنها برابر است. [1] [2]

طرح تعداد عناصر دنباله تا $ن$ تقسیم شده توسط $\ sqrt {n$ ، در مقیاس افقی لگاریتمی

از تعاریف باینری یا پایه 4 این عدد بدست می آید که تقریباً متناسب با اعداد مربع رشد می کنند . تعداد عناصر در توالی Moser-de Bruijn که زیر هر آستانه مشخص هستند $ن$ متناسب است $\ sqrt {n$ ، [3] واقعیتی که در مورد اعداد مربع نیز صادق است. در واقع اعداد در موزر-د برویجن توالی مربع برای یک نسخه از حساب بدون هستند حمل در اعداد دودویی، که در آن جمع و ضرب تک بیت به ترتیب منحصر به فرد و یا و رابطه منطقی عملیات. [4]

در رابطه با قضیه Furstenberg-Sárközy در توالی اعداد و تفاوت در مربع ، Imre Z. Ruzsa ساختاری برای مجموعه های بزرگ بدون اختلاف مربع پیدا کرد که مانند تعریف باینری توالی Moser-de Bruijn ، رقم ها را در محدود می کند. موقعیت های متناوب در پایه- $ب$ شماره. [5] هنگامی که به پایه اعمال می شود $b = 2$ ، ساخت و ساز Ruzsa دنباله Moser – de Bruijn را دو برابر می کند ، مجموعه ای که مجدداً بدون اختلاف مربع است. با این حال ، این مجموعه برای فراهم کردن مرزهای پایین تر برای قضیه Furstenberg-Sárközy بسیار پراکنده است.

بازنمایی منحصر به فرد به عنوان مبالغ [ ویرایش ]

توالی Moser – de Bruijn از خاصیتی شبیه به دنباله Sidon پیروی می کند : مبالغ ${\ نمایشگر x + 2y$ ، جایی که $ایکس$ و $ی$ هر دو متعلق به دنباله Moser-de Bruijn هستند ، همه بی نظیر هستند. هیچ دو مورد از این مبلغ ارزش یکسانی ندارند. علاوه بر این ، هر عدد صحیح است $ن$ می تواند به عنوان یک مبلغ ارائه شود x + 2y ${\ نمایشگر x + 2y$ ، جایی که $ایکس$ و $ی$ هر دو متعلق به دنباله Moser – de Bruijn هستند. برای یافتن مبلغی که بیانگر آن است $ن$ محاسبه $\ displaystyle x = n \ \ & \ \ mathrm {0x55555555}}$ ، بولی بیتی و از $ن$ با یک مقدار باینری (بیان شده در اینجا در شش ضلعی ) که در همه موقعیتهای یکسان و خاص خود دارد\ $\ displaystyle y = (nx) / 2$ . [1] [6]

دنباله Moser – de Bruijn تنها دنباله ای با این خاصیت است ، که تمام اعداد صحیح یک عبارت منحصر به فرد دارند {\ نمایشگر x + 2y ${\ نمایشگر x + 2y$ . به همین دلیل این توالی در ابتدا توسط موسر (1962) مورد مطالعه قرار گرفت . [7] گسترش اموال ، د Bruijn (1964) بی نهایت بسیاری از عبارات خطی دیگر مانند{\ نمایشگر x + 2y ${\ نمایشگر x + 2y$ که ، هنگامی که $ایکس$ و $ی$ هر دو متعلق به دنباله Moser-de Bruijn هستند ، بطور خاص همه عدد صحیح را نمایندگی می کنند. [8] [9]

منحنی Z و فرمول جانشین [ ویرایش ]

تجزیه یک شماره $ن$ به $\ displaystyle n = x + 2y$ ، و سپس به درخواست $ایکس$ و $ی$ نقشه حفظ سفارش از توالی Moser-de Bruijn به اعداد صحیح (با جایگزین کردن قدرتهای چهار در هر عدد توسط قدرتهای مربوطه از دو) به یک جفت ارز از اعداد صحیح غیر منفی به جفتهای مرتباً غیر منفی سفارش می دهد . وارون این بی نظم ترتیب خطی در نقاط موجود در هواپیما با مختصات عدد صحیح غیر منفی می دهد ، که ممکن است برای تعریف منحنی Z- مرتبه استفاده شود . [1] [10]

در ارتباط با این برنامه ، راحت است که یک فرمول برای تولید هر عنصر پی در پی از Moser-de Bruijn از سلف خود داشته باشد. این میتواند بصورت زیر انجام شود. اگر{\ نمایشگر x} $ایکس$ یک عنصر دنباله است ، سپس عضو بعدی پس از آن {\ نمایشگر x} $ایکس$ را می توان با پر کردن بیت در موقعیت های عجیب و غریب از نمایش باینری بدست آورد {\ نمایشگر x} $ایکس$ توسط آنهایی که می شوند ، یکی را به نتیجه اضافه می کنند ، و سپس ماسک های تکمیل شده را می پوشانند. پر کردن بیت ها و اضافه کردن آنها را می توان در یک عملیات اضافی تک ترکیب کرد. یعنی عضو بعدی عدد داده شده توسط فرمول است

$\ displaystyle (x + {\ textrm {0xaaaaaaab}}) \ \ & \ {\ textrm {0x55555555}}$ . [1] [6] [10]

دو ثابت شش ضلعی که در این فرمول ظاهر می شوند را می توان به عنوان اعداد 2 عددی تعبیر کرد $1/3$ و $-1/3$ ، به ترتیب. [1]

بازی تفریق [ ویرایش ]

Golomb (1966) براساس این سکانس ، یک بازی ، مشابه برای تفریق یک مربع را بررسی کرد. در بازی گلومب ، دو بازیکن نوبت گرفتن سکه ها از روی یک گلدان را می گیرند\ displaystyle n $ن$ سکه در هر حرکت ، بازیکن می تواند هر تعداد سکه متعلق به دنباله Moser – de Bruijn را حذف کند. حذف هر تعداد سکه دیگر مجاز نیست. برنده بازیکنی است که آخرین سکه را حذف می کند. همانطور که Golomb مشاهده می کند ، موقعیت های "سرد" این بازی (آنهایی که بازیکنی که قرار است حرکت کند از دست می رود) دقیقاً موقعیت های فرم هستند ${\ displaystyle 2y$ جایی که $ی$ متعلق به توالی Moser – de Bruijn است. یک استراتژی برنده برای بازی در این بازی تجزیه تعداد فعلی سکه ها است ، $ن$ ، به {\ نمایشگر x + 2y ${\ نمایشگر x + 2y$ جایی که {\ نمایشگر x} $ایکس$ و {\ displaystyle y $ی$ هر دو متعلق به دنباله Moser – de Bruijn است ، و سپس (اگر $ایکس$ nonzero) برای حذف است $ایکس$ سکه ، موقعیت سرد را به بازیکن دیگر واگذار می کند. اگر $ایکس$ صفر است ، این استراتژی امکان پذیر نیست ، و هیچ حرکت برنده ای وجود ندارد. [3]

معکوس اعشار [ ویرایش ]

توالی Moser – de Bruijn اساس نمونه ای از یک عدد غیر منطقی را تشکیل می دهد $ایکس$ با خاصیت غیرمعمول که نمایش اعشاری از آن است $ایکس$ و $1 / x$ می توان هر دو را به سادگی و صریح نوشت. اجازه دهید $ه$ توالی Moser-de Bruijn را خود نشان دهید. سپس برای

${\ displaystyle x = 3 \ sum _ {n \ in E} 10 ^ {- n} = 3.300330000000000330033 \ نقطه ،$

عدد اعشاری که رقمهای غیرزرو آن در موقعیت هایی است که توسط دنباله Moser – de Bruijn داده شده است ، بدین ترتیب است که ارقام غیرزوای متقابل آن در موقعیت هایی قرار دارند که با دو برابر کردن اعداد در $ه$ و اضافه کردن یکی به همه آنها: ${\ نمایشگر صفحه \ 1،3،9،11 \ ، \ نقطه \}$ :

$\ displaystyle {\ frac {1} {x}} = 3 \ sum _ {n \ in E} 10 ^ {- 2n-1} = 0.30300000303 \ dots \.}$ [11] [12]

از طرف دیگر ، می توان نوشت:

$left \ displaystyle \ displaystyle \ left (\ sum _ {n \ in E} 10 ^ {- n} \ Right) \ left (\ sum _ {n \ in E} 10 ^ - 2n} \ Right) = {\ frac} 10} {9}}.$

نمونه های مشابه در پایه های دیگر نیز کار می کنند. به عنوان مثال ، دو عدد باینری که بیتهای غیرzero آنها در همان موقعیت هایی هستند که رقم های غیرزوای دو عدد اعشاری در بالا هستند نیز متقابل غیر منطقی هستند. [13] این اعداد باینری و اعشاری ، و اعداد تعریف شده به همان روش برای هر پایه دیگر با تکرار یک رقم nonzero واحد در موقعیت های داده شده توسط توالی Moser-de Bruijn ، اعداد متعالی هستند . فراتر بودن آنها را می توان از این واقعیت اثبات کرد که رشته های طولانی صفر در رقم آنها به آنها اجازه می دهد تا با اعداد منطقی با دقت بیشتری تقریب پیدا کنند تا در صورت وجود اعداد جبری ، با قضیه روث مجاز باشند .[12]

تولید عملکرد [ ویرایش ]

تابع مولد

$\ displaystyle F (x) = \ prod _ {i = 0} ^ {\ infty} (1 + x ^ {4 ^ {i} =) = 1 + x + x ^ {4} + x ^ {5 + x ^ {16} + x ^ {17} + \ cdots،$

نمایانگرانی که به شکل گسترده توسط دنباله موزر دی بروژن ارائه شده اند ، از معادلات عملکردی پیروی می کنند

$\ displaystyle F (x) F (x ^ {2}) = {\ frac {1} {1-x}}}$ [1] [2]

${\ displaystyle F (x) = (1 + x) F (x ^ {4}).$ [14]

به عنوان مثال ، می توان از این تابع برای توصیف دو بازده اعشاری آورده شده در بالا استفاده کرد: یکی است ${\ نمایشگر 3F (1/10)$ و دیگری این است ${\ displaystyle {\ tfrac {3} {10}} F (1/100)$ . این واقعیت که آنها متقابل هستند نمونه ای از اولین دو معادله کاربردی است. محصولات جزئی از فرم محصول از تابع مولد را می توان مورد استفاده برای تولید convergents از کسر ادامه گسترش این اعداد خود را، و همچنین تقسیم عددی بر مضرب از آنها. [11]

عود و منظم [ ویرایش ]

توالی Moser – de Bruijn از یک رابطه عود پیروی می کند که اجازه می دهد تا مقدار n دنباله ، $S (n)$ (شروع از} $\ displaystyle S (0) = 0}$ ) از مقدار موجود در موقعیت تعیین می شود $\ lfloor n / 2 \ rfloor$ :

${\ displaystyle S (2n) = 4S (n)$

${\ displaystyle S (2n + 1) = 4S (n) +1$

تکرار این عود امکان تبعات فرم را فراهم می آورد $\ displaystyle S (2 ^ {i} n + j)$ به عنوان یک تابع خطی از دنباله اصلی بیان شود ، به این معنی که توالی Moser-de Bruijn یک دنباله 2 عادی است . [15]

منبع

https://en.wikipedia.org/wiki/Moser%E2%80%93de_Bruijn_sequence

مشخصات وب

در این وبلاگ به ریاضیات و کاربردهای آن و تحقیقات در آنها پرداخته می شود. مطالب در این وبلاگ ترجمه سطحی و اولیه است و کامل نیست.در صورتی سوال یا نظری در زمینه ریاضیات دارید مطرح نمایید .در صورت امکان به آن می پردازم. من دوست دارم برای یافتن پاسخ به سوالات و حل پروژه های علمی با دیگران همکاری نمایم.در صورتی که شما هم بامن هم عقیده هستید با من تماس بگیرید.
09132003030

ریاضیات

آموزش ریاضی