حدس کولاتز
آیا دنباله کولاتز در نهایت با شروع از هر عدد طبیعی دلخواه به ۱ ختم میگردد؟
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/c2/Collatz-graph-50-no27.svg/220px-Collatz-graph-50-no27.svg.png)
حدس کولاتز (Collatz Conjecture)، حدسی در ریاضیات است که مربوط به دنبالهها بوده و به این صورت مطرح میگردد: از هر عدد طبیعی دلخواهی چون n شروع کنید، سپس هر جمله از جمله قبلی دنباله به این صورت بدست میآید: اگر جمله قبلی زوج بود، جمله بعدی نصف قبلی خواهد بود. اگر جمله قبلی فرد بود، جمله بعدی سه برابر جمله قبلی به علاوه ۱ خواهد شد. این حدس میگوید: مهم نیست که مقدار n چه باشد، در نهایت این دنباله همیشه به ۱ ختم خواهد شد.
این حدس را به نام لوتار کولاتز نامگذاری کردهاند که اولین بار ایده آن را در ۱۹۳۷ میلادی، دو سال پس از دریافت مدرک دکترایش معرفی نمود.[۱] همچنین این مسئله را به نامهای زیر نیز میشناسند: مسئله ، حدس ، حدس اولام (به یاد استنیسواف اولام)، مسئله کاکوتانی (به یاد شیزو کاکوتانی)، حدس توایتس (به یاد برایان توایتس)، الگوریتم هاسه (به یاد هلموت هاسه) یا مسئله سیراکوس.[۲][۴] دنباله اعداد ظاهر شده در این حدس را برخی مواقع دنباله تگرگی یا اعداد تگرگی (به این دلیل که مقادیرش اغلب همچون تگرگ درون یک ابر، چندین نزول و صعود دارند)[۵][۶] یا اعداد شگرف مینامند.[۷]
پاول اردوش در مورد حدس کولاتز گفت: «ممکن است ریاضیات برای چنین مسائلی هنوز آمادگی نداشته باشد.»[۸] همچنین او جایزه ۵۰۰ دلاری را برای جواب آن اعلام نمود.[۹] جفری لاگاریاس در ۲۰۱۰ بیان نمود که حدس کولاتز «مسئلهای است که دشواری عجیباً زیادی داشته و کاملاً از دسترس ریاضیات کنونی خارج است.»[۱۰]
بیان مشکل
[ویرایش]- عملیات زیر را در مجموعه اعداد صحیح مثبت اختیاری در نظر بگیرید
برای مثال، اگر عملیات روی ۳ انجام شود، نتیجه ۱۰ است و اگر روی ۲۴ اجرا شود نتیجه ۱۲ است. اگر بخواهیم این عملیات را به صورت تابعی ریاضی نشان دهیم به صورت زیر خواهد بود:
هم اکنون با اجرا کردن این عملیات بر روی یک دنباله از اعداد بهطور متوالی با هر عدد صحیح مثبت، و گرفتن نتیجه به عنوان ورودی مرحله بعد: در حالی که:
حدس کولاتز به صورت زیر است:
این روند به صورت اتفاقی به عدد ۱ میرسد، صرف نظر از این که چه عددی به عنوان عدد اولیه انتخاب شده.
کوچکترین i که به ازای آن روند فوق ادامه مییابد زمان کلی ایست n نام دارد. این حدس ادعا دارد که هر عدد n یک زمان کلی ایست خوش تعریف دارد. اگر به ازای یک N خاص، عدد i به صورت بیان شده وجود نداشته باشد میگوییم N یک زمان کلی ایست نامحدود دارد و حدس غلط است. اگر حدس غلط باشد میتواند فقط به این دلیل باشد که یک عدد شروعی وجود دارد که به دنباله خاتمهای میدهد که ۱ شامل آن دنباله نیست. یک چنین دنبالهای ممکن است وارد چرخهای شود که از ۱ مستثنی باشد یا این که بدون محدودیت ادامه یابد. تا به حال چنین دنبالهای پیدا نشدهاست.
مثالها
[ویرایش]- برای نمونه، شروع از n=۶، دنباله به صورت:
۶، ۳، ۱۰، ۵، ۱۶، ۸، ۴، ۲، ۱
شروع از n=۱۱، دنباله بیشتر طول میکشد تا به ۱ برسد:
۱۱، ۳۴، ۱۷، ۵۲، ۲۶، ۱۳، ۴۰، ۲۰، ۱۰، ۵، ۱۶، ۸، ۴، ۲، ۱
اگر مقدار عدد شروع n=۲۷ باشد، یک دنباله ۱۱۱ قدمی به وجود میآید که قبل از رسیدن به ۱ از ۹۰۰۰ تجاوز میکند:
{ ۲۷، ۸۲، ۴۱، ۱۲۴، ۶۲، ۳۱، ۹۴، ۴۷، ۱۴۲، ۷۱، ۲۱۴، ۱۰۷، ۳۲۲، ۱۶۱، ۴۸۴، ۲۴۲، ۱۲۱، ۳۶۴، ۱۸۲، ۹۱، ۲۷۴، ۱۳۷، ۴۱۲، ۲۰۶، ۱۰۳، ۳۱۰، ۱۵۵، ۴۶۶، ۲۳۳، ۷۰۰، ۳۵۰، ۱۷۵، ۵۲۶، ۲۶۳، ۷۹۰، ۳۹۵، ۱۱۸۶، ۵۹۳، ۱۷۸۰، ۸۹۰، ۴۴۵، ۱۳۳۶، ۶۶۸، ۳۳۴، ۱۶۷، ۵۰۲، ۲۵۱، ۷۵۴، ۳۷۷، ۱۱۳۲، ۵۶۶، ۲۸۳، ۸۵۰، ۴۲۵، ۱۲۷۶، ۶۳۸، ۳۱۹، ۹۵۸، ۴۷۹، ۱۴۳۸، ۷۱۹، ۲۱۵۸، ۱۰۷۹، ۳۲۳۸، ۱۶۱۹، ۴۸۵۸، ۲۴۲۹، ۷۲۸۸، ۳۶۴۴، ۱۸۲۲، ۹۱۱، ۲۷۳۴، ۱۳۶۷، ۴۱۰۲، ۲۰۵۱، ۶۱۵۴، ۳۰۷۷، ۹۲۳۲، ۴۶۱۶، ۲۳۰۸، ۱۱۵۴، ۵۷۷، ۱۷۳۲، ۸۶۶، ۴۳۳، ۱۳۰۰، ۶۵۰، ۳۲۵، ۹۷۶، ۴۸۸، ۲۴۴، ۱۲۲، ۶۱، ۱۸۴، ۹۲، ۴۶، ۲۳، ۷۰، ۳۵، ۱۰۶، ۵۳، ۱۶۰، ۸۰، ۴۰، ۲۰، ۱۰، ۵، ۱۶، ۸، ۴، ۲، ۱ }
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/96/Collatz5.svg/800px-Collatz5.svg.png)
برنامهای برای محاسبه دنباله کولاتز
[ویرایش]- یک دنبالهٔ معین کولاتز به راحتی محاسبه میشود، همان طور که در شبه کد زیر نمایش داده شده:
while n> 1
show n
if n is odd
set n to 3n + 1
else
set n to n / 2
show n
این برنامه وقتی دنباله به ۱ میرسد، برای جلوگیری از چاپ چرخه بی پایان ۴و۲و۱، متوقف میشود. اگر حدس کولاتز درست باشد، این برنامه صرف نظر از عدد ورودی همیشه متوقف میشود.
اثبات استدلال
[ویرایش]- هرچند که این حدس هنوز اثبات نشدهاست، ولی اکثر ریاضیدانان که این مشکل را بررسی کردهاند، خود به خود اعتقاد دارند که این حدس درست است.
در این قسمت دو دلیل برای این انتظار درستی بیان میکنیم:
- مدارک آزمایشی
با تعجب باید گفته شود که این گونه مقید کردنها توسط رایانه ارزش مدرکی بسیار محدودی دارند. چندین حدس وجود دارند که مثال نقضشان بهطور استثنایی مقداری بسیار بزرگ است.(مانند حدس پولیا، حدس مرتن یا عدد اسکیوویز) همچنین این موضوع که، {۴٬۲٬۱} تنها چرخه با دورهٔ کمتر از ۳۵۴۰۰ است، روشن شدهاست.
مدارک احتمالی
[ویرایش]- اگر کسی تنها اعداد فرد تولید شده در دنبالهٔ کولاتز را در نظر بگیرد، آنگاه کسی میتواند استدلال کند که در حالت میانگین(در حالت خاص میانگین هندسی قسمتها) عدد فرد بعدی باید ¾قبلی باشد، که اظهار میکند این دسته اعداد باید با ترتیبی طولانی کاهش یابند.(اگرچه این مدرکی علیه چرخهها نیست، فقط علیه واگرایی است)
دیدگاههای دیگر دربارهٔ موضوع
[ویرایش]در حالت معکوس
[ویرایش]- دیدگاه دیگری برای اثبات این حدس به کار میرود، که روش رشد از بالا به پایین را در نظر میگیرد که گراف کولاتز نام دارد.
گراف کولاتز گرافی است که با رابطهٔ معکوس زیر تعریف میشود:
بنابراین به جای این که ثابت کنیم همهٔ اعداد طبیعی بهطور اتفاقی به ۱ میرسند، میتوانیم ثابت کنیم که ۱ به تمام اعداد طبیعی سوق داده میشود. برای تمام اعداد صحیح همچنین، رابطهٔ معکوس، به جز حلقهٔ ۱و۲و۴، یک درخت است(وارون حلقه ۱و۴و۲ یک تابع بدون تغییر است که در عبارت مشکل بالا مطرح شدهاست). وقتی رابطهٔ ۳n+۱ در تابع (f(n، با جانشینی رایج «میان بر» با رابطهٔ ۳n + ۱)/۲) جا به جا شود(بهینه سازی زیر را ببینید)، گراف کولاتز با رابطهٔ وارون زیر تعریف میشود:
این رابطهٔ معکوس، به جز حلقهٔ ۱-۲، به شکل یک درخت در میآید (معکوس حلقهٔ ۱-۲در تابع (f(n، همانطور که نشان داده شد، در بالا بازبینی شدهاست)
به عنوان اعداد گویا
[ویرایش]اعداد طبیعی میتوانند با بهکارگیری روشی مشخص، به اعداد گویا تبدیل شوند. براای به دست آوردن مدل گویا، بزرگترین عدد توان ۲ که کمتر مساوی عدد اصلی است پیدا کنیدو آن را به عنوان مخرج در نظر بگیرید. سپس آن را از عدد اصلی کم کنید و به عنوان صورت در نظر بگیرید (۱۵/۵۱۲→۵۲۷). برای به دست آوردن مدل طبیعی عدد صورت و مخرج کسر را با هم جمع کنید (۵۱۱→ ۲۵۵/۲۵۶).
حدس کولاتز میگوید که صورت سرانجام برابر صفر میشود. تابع کولاتز به صورت زیر تغییر میکند:
(n=صورت،d=مخزج)
این روش کار میکند زیرا ۳x + ۱ = ۳(d + n) + ۱ = (۲d) + (۳n + d + ۱) = (۴d) + ۳n - d+۱. کاهش یک عدد گویا قبل از هرگونه عملیات باید صورت گیرد تا بتوانx را فرد دریافت کرد.
به عنوان یک ماشین انتزاعی
[ویرایش]- استفادهٔ مکرر از تابع کولاتز را میتوان به عنوان یک ماشین انتزاعی که با رشتههایی از بیتها سرو کار دارد، بیان کرد.
ماشین دو قدم زیر را تا زمانی که فقط ۱ باقی بماند روی هر عدد فردی انجام میدهد:
۱. عدد اصلی را با عدد اصلی که یک "۱" به انتهای آن اضافه شده جمع کن.(رشته را به عنوان یک عدد دودویی در نظر میگیریم) میدانیم: ۳n + ۱ = (۲n + ۱) + n
۲. تمام ۰های انتهایی را پاک کن.
که برابر مبنای دو در محاسبات است
[ویرایش]- راه دیگر امتحان حدس ۳n+۱ اقدام از طریق اعداد در مبنای دو است. مثال آن به صورت زیر است:
مثال:ما از عدد ۷ استفاده میکنیم پس در مبنای دو به صورت ۱۱۱ است:
راه استفاده شده برای بازگو کردن هر عدد در مبنای دو به صورتی است که ابتدا عدد اولیه را مینویسیم سپس زیر آن همان عدد را با یک "۱" اضافه شده به انتهای سمت راست آن مینویسیم و دو عدد را جمع میکنیم. هر صفری که در انتهای راست حاصل جمع ظاهر شد حذف میکنیم و این روند را تا جایی ادامه میدهیم که به عدد ۱ برسیم.
مقایسهٔ ماشین انتزاعی به برابری حسابی در مبنای ۲:
# # Python # import re # regular expressions import gmpy # base ۲ math library def abstract_machine(s): # define Truth Tables for the Full Adder sum_tt = {'۰۰۰':'۰','۰۰۱':'۱','۰۱۰':'۱','۰۱۱':'۰','۱۰۰':'۱','۱۰۱':'۰','۱۱۰':'۰','۱۱۱':'۱'} carry_tt = {'۰۰۰':'۰','۰۰۱':'۰','۰۱۰':'۰','۰۱۱':'۱','۱۰۰':'۰','۱۰۱':'۱','۱۱۰':'۱','۱۱۱':'۱'} print s while s != '۱': if s[-۱]=='۱': # it's odd s = '۰۰' + s # operands must be same length, so prepend with MS ۰ ss = '۰' + s + '۰' # shift left (append LS ۰) and prepend (MS ۰) to allow carry t = "".join(reversed(s)) # iterating is L->R, so temporarily reverse tt = "".join(reversed(ss)) carry = '۱' # preset carry (the '۱' of '۳n+۱') answer = "" # initialize answer for i,j in enumerate(t): # walk through operands one char at a time the_input = carry + j + tt[i] # assemble input from previous carry & two operands the_sum = sum_tt[the_input] # look up sum out in sum Truth Table carry = carry_tt[the_input] # look up carry out in carry Truth Table answer = answer + the_sum # append sum to answer (carry used on next iteration) final_answer = "".join(reversed(answer)) # un-reverse answer if final_answer[۰]=='۰': # if the last pad caharacter didn't receive a carry, final_answer = final_answer[۱:] # ...get rid of it print final_answer # show result before stripping LS ۰'s else: # it's even final_answer = s m = re.search('(. *۱)(۰*$)',final_answer) # remove all LS ۰'s in one fell swoop s = "".join(m.groups()[۰]) # reassemble answer to do next iteration print s def base_۲(n): while n>۱: f = gmpy.scan۱(n,۰) # find position of LS ۱-bit if f>۰: # it's even print gmpy.digits(n,۲) # print n in base ۲ n = n>> f # remove all LS ۰'s in one fell swoop else: # it's odd print gmpy.digits(n,۲) # print n in base ۲ n = (n <<۱) + n + ۱ # multiply by ۳ and add ۱ print gmpy.digits(n,۲) # print n in base ۲ # main print 'test of abstract machine:' print abstract_machine('۱۱۱') print print print 'test of base ۲:' print base_۲(۷) ## test of abstract machine: ## ## ۱۱۱ ## ۱۰۱۱۰ ## ۱۰۱۱ ## ۱۰۰۰۱۰ ## ۱۰۰۰۱ ## ۱۱۰۱۰۰ ## ۱۱۰۱ ## ۱۰۱۰۰۰ ## ۱۰۱ ## ۱۰۰۰۰ ## ۱ ## ## ## test of base ۲: ## ## ۱۱۱ ## ۱۰۱۱۰ ## ۱۰۱۱ ## ۱۰۰۰۱۰ ## ۱۰۰۰۱ ## ۱۱۰۱۰۰ ## ۱۱۰۱ ## ۱۰۱۰۰۰ ## ۱۰۱ ## ۱۰۰۰۰ ## ۱ ##
به عنوان یک تابع زوج
[ویرایش]- برای این قسمت تابع کولاتز را که اندکی تغییر کرده را در نظر بگیرید:
ما مجوز ایجاد این تغییر را داریم زیرا وقتی n فرد است ۳n+۱ همیشه زوج است. اگر (...)Pزوجیت یک عدد باشد، به صورتی که P(۲n) = ۰ و P(۲n + ۱) = ۱. پس ما میتوانیم دنبالهٔ زوجیت کولاتز را برای یک عدد n به صورت ('pi = P(aiکه a۰ = n و(ai+۱ = f(ai تعریف میکنیم.
استفاده از این شکل (f(n میتواند نشان دهد که دنبالهٔ زوجیت برای دو عدد m,n در k دورهٔ اول مساوی است اگر و تنها اگر m,n به پیمانهٔ k۲برابر باشند. این موضوع به این اشاره دارد که هر عدد بهطور خاص با دنبالهٔ زوجیت خود شناخته میشود و علاوه بر این اگر حلقههای کولاتز متعددی وجود داشت، حلقهٔ زوجیت متناظر با آنها نیز باید متفاوت باشد. اثبات این موضوع بسیار سادهاست، میتوان به صورت شهودی و بسیار ساده مشاهده کرد که اعمال f تابع ،k بار بر عددa ۲k+b عدد a ۳c+d را نتیجه خواهد داد، که d نتیجهٔ اعمال f تابع ،k بار بر عدد b است و c عددی است که نشان میدهد چه تعداد عدد فرد در طی این دنباله به دست آمدهاست بنابراین زوجیت k عدد اول به کلی با b معین میشود و زوجیت عدد k+۱ام، اگر آخرین عدد پرمعنیa تغییر کند، تغییر خواهد کرد. حدس کولاتز را میتوان به این صورت بیان کرد که، زوجیت دنبالهٔ کولاتز برای هر عدد نهایتاً وارد حلقهٔ ۰ → ۱ → ۰ میشود.
مانند یک سیستم برچسب
[ویرایش]- برای تابع کولاتز به فرم:
دنبالههای کولاتز توسط سیستم بسیار ساده ۲-برچسبی که قانون حاصل جمع آن به صورت زیر است محاسبه میشوند:
و به صورتی که عدد صحیح مثبت n یک رشتهٔ nتایی از aها بیان شدهاست، با بیان این موضوع که عملیات برچسب روی هر کلمهای که طولش از ۲ کمتر است میایستد. حدس کولاتز را میتوان به این صورت بیان کرد که، این سیستم برچسب گذاری، با یک رشتهٔ دلخواه کراندار از aها به عنوان عدد اولیه، در پایان میایستد.
بسط در دامنههای بزرگتر
[ویرایش]- تکرار روی تمام اعداد صحیح:
برای هر عدد صحیح، نه فقط اعداد صحیح مثبت، ما آن را روی (f(n مینگاریم که:
*اگر n زوج f(n) = ۳n + ۱; *اگر n فرد f(n) = n/۲.
بهطور جالب توجه مشاهده میشود که در این حالت تنها پنج حلقه داریم، که به نظر میرسد که تمام اعداد نهایتاً مشمول این تکرار میشوند. این ۵ حلقه در پایین نشان داده شدهاست. برای ذخیره گامها، ما فقط اعداد فرد را در حلقه یادداشت میکنیم (به جز حلقه کوچک {۰}). هر عدد فرد n، وقتی تابع f مکرراً اعمال میشود به عدد فرد بعدی خواهد رسید در: (بزرگترین عدد توان دو که۳n+۱ را عاد میکند)/۳n+۱
هر حلقه با اولین عضو کمترین مقدار مطلقش فهرست شده.
ما هر حلقه را با اندازهٔ حلقهٔ کامل دنبال میکنیم (داخل پرانتز):شمارهٔ اعضا، زوج یا فرد، به حلقه متعلق است که بدون تکرار محاسبه شدهاست.
a) ۱ → ۱ (size ۳)
b) ۰ → ۰ (size ۱)
c) -۱ → -۱ (size ۲)
d) -۵ → -۷ → -۵ (size ۵)
e) -۱۷ → -۲۵ → -۳۷ → -۵۵ → -۴۱ → -۶۱ → -۹۱ → -۱۷ (size ۱۸)
در اینجا حدس کولاتز تعمیم یافته را بیان کردیم به این نظر که هر عدد صحیح، در تکرار توسط f، در پایان وارد یکی از حلقههای a,b،c,d،e میشود. تکرار روی اعداد گویا با مخرج زوج: نگاشت استاندارد کولاتز را میتوان به اعداد گویا بسط داد (چه منفی چه مثبت) که مخرج فرد دارند، زمانی که در سادهترین حالت نوشته میشوند. زوج یا فرد بودن عدد با توجه به این تعیین میشود که صورت زوج است یا فرد. دنبالههای زوجیت همانطور که در بالا تعریف شد دیگر برای کسرها منحصربهفرد نیستند، هر چند میتوان نشان داد هر حلقهٔ زوجیت ممکن یک دنبالهٔ زوجیت برای دقیقاً یک کسر است:اگر یک حلقه دارای طول n و شامل اعداد فرد دقیقاً m تا به صورت
k۰, …, km-۱، آنگاه کسر منحصربهفرد که حلقهٔ زوجیت را به وجود میآورد برابر:
.
برای مثال، حلقهٔ زوجیت (۱ ۰ ۱ ۱ ۰ ۰ ۱) دارای طول ۷ و ۴ عدد فرد به صورت ۰٬۲٬۳ است و کسر منحصربهفرد که حلقهٔ زوجیت را تولید میکند برابر:
.
حلقهٔ کامل موجود به صورت: ۱۵۱/۴۷ → ۸۵/۴۷ → ۱۷۰/۴۷ → ۳۴۰/۴۷ → ۲۱۱/۴۷ → ۱۲۵/۴۷ → ۲۵۰/۴۷ → ۱۵۱/۴۷
هرچند جایگشتهای تناوبی دنبالههای زوجیت اصلی کسرهایی منحصربهفرد هستند ولی حلقه منحصربهفرد نیست. هر کسر جایگشت برابر عدد بعدی در دور حلقهاست:
- (۰ ۱ ۱ ۰ ۰ ۱ ۱) →
- (۱ ۱ ۰ ۰ ۱ ۱ ۰) →
- (۱ ۰ ۰ ۱ ۱ ۰ ۱) →
- (۰ ۰ ۱ ۱ ۰ ۱ ۱) →
- (۰ ۱ ۱ ۰ ۱ ۱ ۰) →
- (۱ ۱ ۰ ۱ ۱ ۰ ۰) →
همچنین برای منحصربهفردی، دنبالههای زوجیت باید «اول» باشد. نباید قابل تقسیم به زبر دنبالههای یکسان باشد. برای مثال، دنبالههای زوجیت (۱ ۱ ۰ ۰ ۱ ۱ ۰ ۰) میتواند به دو زیر دنبالهٔ یکسان(۱ ۱ ۰ ۰)(۱ ۱ ۰ ۰) تقسیم شود. محاسبهٔ کسر ۸-عاملی این دنباله نشان میدهد:
- (۱ ۱ ۰ ۰ ۱ ۱ ۰ ۰) →
ولی وقتی کسر را ساده کنیم {۵/۷} مانند همان زیر دنبالهٔ ۴-عاملی است:
- (۱ ۱ ۰ ۰) →
و این به این دلیل است که دنبالهٔ زوجیت ۸-عاملی در واقع دو حلقه از دور حلقهای تعریف شده توسط زیر دنبالهٔ ۴-عاملی است.
در این زمینه، حدس کولاتز برابر با این است که بگوییم(۰،۱) تنها حلقهای است که تمام اعداد مثبت ایجاد میشود.
تکرار روی اعداد حقیقی یا اعداد مختلط
[ویرایش]نگاشت کولاتز را میتوان به عنوان یک محدودیت برای اعداد حقیقی یا اعداد مختلط نشان داد:
- ،
پس از ساده سازی:
.
اگر نگاشت استاندارد کولاتزی که در بالا تعریف شده توسط جایگزینی “۳n+۱”با “۳n+۱)/۲)”بهینه شده باشد، این موضوع میتواند نشان داده شود که یک محدودیت برای اعداد حقیقی یا اعداد مختلط است:
،
پس از ساده سازی:
.
تکرار نگاشت بهینهسازی شدهٔ فوق در صفحهٔ اعداد مختلط فراکتال کولاتز را ایجاد میکند.
بهینه سازیها
[ویرایش]- در قسمت «زوجیت» راهی برای سرعت بخشیدن به شبیه سازی دنباله ارائه شد. برای جلو افتادن k قدم در هر تکرار (با استفاده از تابع f در همان قسمت)، عدد فعلی را به دو قسمت تقسیم میکنیم،b(kتا کم ارزشترین رقمها)، و a (بقیه رقمهای عدد). نتیجه جلو پریدن k+c[b] قدم به صورت زیر خود را نشان میدهد:
- f k+c[b](a ۲k+b) = a ۳c[b]+d[b]
مقادیر c,d برای تمام اعداد K-بیتی ممکن از قبل محاسبه شدهاست که d[a] نتیجه اعمال k بار تابع f روی b است، و c[a]تعداد اعداد فرد در طول مسیر است. برای مثال اگر ،k=۵ باشد، میتوان ۵ قدم در هر تکرار توسط جدا کردن ۵ تا از کم ارزشترین رقمها به جلو پرید و استفاده از:
- c [۰...۳۱] = {۰٬۳٬۲٬۲٬۲٬۲٬۲٬۴٬۱٬۴٬۱٬۳٬۲٬۲٬۳٬۴٬۱٬۲٬۳٬۳٬۱٬۱٬۳٬۳٬۲٬۳٬۲٬۴٬۳٬۳٬۴٬۵}
- d [۰...۳۱] = {۰٬۲٬۱٬۱٬۲٬۲٬۲٬۲۰٬۱٬۲۶٬۱٬۱۰٬۴٬۴٬۱۳٬۴۰٬۲٬۵٬۱۷٬۱۷٬۲٬۲٬۲۰٬۲۰٬۸٬۲۲٬۸٬۷۱٬۲۶٬۲۶٬۸۰٬۲۴۲}
- اگر k یک عدد فرد باشد، آنگاه ۳k+۱ زوج است، پس میتوانیم بنویسیم ۳k + ۱ = ۲ak′، K یک عدد فرد و a ≥ ۱ است. ما تابع f را از روی مجموعهٔ Iاز اعداد فرد به روی خودش تعریف میکنیم، که تابع سیراکوس نام دارد، با فرض این کهf (k) = k′
برخی از خواص تابع سیراکوس:
- برای تمام kها درIf (۴k + ۱) = f (k)
- برای تمام p ≥ ۲ و hهای فرد،f p - ۱(۲ p h - ۱) = ۲ ۳ p - ۱h – ۱
- برای تمام hهای فرد،f (۲h - ۱) ≤ (۳h - ۱)/۲
حدس سیراکوس این است که برای تمام kها در I، وجود دارد عدد صحیح n ≥ ۱ به صورتی که
. بهطور هم ارز، فرض میکنیم E مجموعه اعداد فرد k باشد که عدد صحیح n ≥ ۱ وجود دارد به صورتی که
باشد. مشکل این است که نشان دهیم E=I است. در ادامه تلاشی را برای اثبات از طریق استقرا آغاز میکنیم: میدانیم ۱و۳و۵و۷و۹ در E وجود دارند. فرض میکنیم k عددی فرد بزرگتر از ۹ باشد. فرض میکنیم که k-۲ و تمام اعداد فرد قبل از آن در E هستند و اثبات میکنیم که kدر E است. وقتی k یک عدد فرد است پس میتوان نتیجه گرفت
برای p ≥ ۱ و hهای فرد و
پس حالا داریم:
- اگر p=۱، آنگاه k=۲h-۱. به راحتی میتوان امتحان کرد که f (k) <k، بنابراین f (k) ∈ E از اینرو k ∈ E.
- اگر p ≥ ۲و hمضرب ۳ باشد، میتوانیم بنویسیمh = ۳h′. فرض میکنیمk′ = ۲p + ۱h′ - ۱پس داریم f (k′) = k، و تا زمانی کهk′ <k، k′در E وجود دارد، بنابراین k = f (k′) ∈ E.
- اگر p ≥ ۲و hمضرب ۳ نباشد ولی h ≡ (-۱)p mod ۴ ولی باز هم میتوان نشان داد k ∈ E.
قسمت مشکل ساز آنجاست که p ≥ ۲و hمضرب ۳ نباشد و h ≡ (-۱)p+۱ mod ۴. در اینجا اگر سعی کنیم که نشان دهیم که برای هر عدد صحیح فرد′k،
کار تمام است.
جستارهای وابسته
[ویرایش]ارجاعات
[ویرایش]- ↑ O'Connor, J.J.; Robertson, E.F. (2006). "Lothar Collatz". St Andrews University School of Mathematics and Statistics, Scotland.
- ↑ Maddux, Cleborne D.; Johnson, D. Lamont (1997). Logo: A Retrospective. New York: Haworth Press. p. 160. ISBN 0-7890-0374-0.
The problem is also known by several other names, including: Ulam's conjecture, the Hailstone problem, the Syracuse problem, Kakutani's problem, Hasse's algorithm, and the Collatz problem.
- ↑ Lagarias, Jeffrey C. (1985). "The 3x + 1 problem and its generalizations". The American Mathematical Monthly. 92 (1): 3–23. doi:10.1080/00029890.1985.11971528. JSTOR 2322189.
- ↑ According to Lagarias (1985),[۳] p. 4, the name "Syracuse problem" was proposed by Hasse in the 1950s, during a visit to Syracuse University.
- ↑ Pickover, Clifford A. (2001). Wonders of Numbers. Oxford: Oxford University Press. pp. 116–118. ISBN 0-19-513342-0.
- ↑ "Hailstone Number". MathWorld. Wolfram Research.
- ↑ Hofstadter, Douglas R. (1979). Gödel, Escher, Bach. New York: Basic Books. pp. 400–2. ISBN 0-465-02685-0.
- ↑ Guy, Richard K. (2004). ""E17: Permutation Sequences"". Unsolved problems in number theory (3rd ed.). Springer-Verlag. pp. 336–7. ISBN 0-387-20860-7. Zbl 1058.11001.
- ↑ Guy, R. K. (1983). "Don't try to solve these problems". Amer. Math. Monthly. 90 (1): 35–41. doi:10.2307/2975688. JSTOR 2975688. By this Erdos means that there aren't powerful tools for manipulating such objects.
- ↑ Lagarias, Jeffrey C., ed. (2010). The Ultimate Challenge: the 3x + 1 problem. American Mathematical Society. ISBN 978-0-8218-4940-8. Zbl 1253.11003.
منابع
[ویرایش]- Jeffrey C. Lagarias. The 3x + 1 problem: An annotated bibliography (1963–2000).
- Jeffrey C. Lagarias. The 3x + 1 problem: An annotated bibliography, II (2001–).
- Jeffrey C. Lagarias. The 3x + 1 problem and its generalizations, American Mathematical Monthly Volume 92، 1985، pp. 3–23.
- Jeffrey C. Lagarias (2001) [1994], "Syracuse problem", Encyclopedia of Mathematics, EMS Press
{{citation}}
: Unknown parameter|urlname=
ignored (help) - Günther J. Wirsching. The Dynamical System Generated by the Function. Number 1681 in Lecture Notes in Mathematics. Springer-Verlag, 1998.
- An ongoing distributed computing project by Eric Roosendaal verifies the Collatz conjecture for larger and larger values.
- Another ongoing distributed computing project by Tomás Oliveira e Silva continues to verify the Collatz conjecture (with fewer statistics than Eric Roosendaal's page but with further progress made).
- Weisstein, Eric W. "Collatz Problem". MathWorld.
- Collatz Problem در PlanetMath.
- Hailstone Patterns discusses different resonators along with using important numbers in the problem (like 6 and 3^5) to discover patterns.
- Keith Matthews' 3x+1 page: Review of progress, plus various programs
- Ohira, Reiko & Yamashita, Michinori A generalization of the Collatz problem
- URATA, Toshio Some Holomorphic Functions connected with the Collatz Problem
- Matti K. Sinisalo: On the minimal cycle lengths of the Collatz sequences, Preprint, June 2003، University of Oulu
- Paul Stadfeld: Blueprint for Failure: How to Construct a Counterexample to the Collatz Conjecture
- Liesbeth De Mol: «Tag systems and Collatz-like functions», Preprint (Nr. 314), to appear in Theoretical Computer Science.
- Kawasaki Hiroyuki: [۲] Claimed proof of Collatz conjecture
- Alain Slakmon and Luc Macot: «On the Almost Sure Convergence of Syracuse Sequences» بایگانیشده در ۲۹ سپتامبر ۲۰۰۷ توسط Wayback Machine, Statistics & Probability Letters
76 (15), 2006، 1625-1630.
- Collatz Iterations on the Ulam Spiral grid در یوتیوب
- Collatz Paths by Jesse Nochella, The Wolfram Demonstrations Project.