نمایش مبدأ برای حدس کولاتز

{{حل نشده|ریاضیات|آیا دنباله کولاتز در نهایت با شروع از هر عدد طبیعی دلخواه به ۱ ختم می‌گردد؟}}
[[File:Collatz-graph-50-no27.svg|thumb|upleft=0.6|[[گراف جهت‌دار|گراف جهت‌داری]] که مدارهای اعداد کوچکِ تحت نگاشت کولاتز را به نمایش گذاشته‌است. در این گراف اعداد زوج نادیده انگاشته شده‌اند. حدس کولاتز بیان می‌دارد که تمام مسیرها در نهایت به ۱ ختم می‌گردند.]]
'''حدس کولاتز''' (Collatz Conjecture)، [[حدس|حدسی]] در [[ریاضیات]] است که مربوط به [[دنباله|دنباله‌ها]] بوده و به این صورت مطرح می‌گردد: از هر [[عدد طبیعی]] دلخواهی چون ''n'' شروع کنید، سپس هر جمله از جمله بعدی دنباله به این صورت بدست می‌آید: اگر جمله قبلی [[اعداد زوج و فرد|زوج]] بود، جمله بعدی نصف قبلی خواهد بود. اگر جمله قبلی فرد بود، جمله بعدی سه برابر جمله قبلی به علاوه ۱ خواهد شد. این حدس می‌گوید: مهم نیست که مقدار ''n'' چه باشد، در نهایت این دنباله همیشه به ۱ ختم خواهد شد.

این حدس را به نام لوتار کولاتز نامگذاری کرده‌اند که اولین بار ایده آن را در ۱۹۳۷ میلادی، دو سال پس از دریافت مدرک دکترایش معرفی نمود.<ref>{{cite web|last1= O'Connor|first1=J.J.|last2=Robertson|first2=E.F.|title=Lothar Collatz|year=2006|url=http://www-history.mcs.st-andrews.ac.uk/Biographies/Collatz.html|publisher=St Andrews University School of Mathematics and Statistics, Scotland}}</ref> همچنین این مسئله را به نام‌های زیر نیز می‌شناسند: '''مسئله <math>3n+1</math>'''، '''حدس <math>3n+1</math>'''، '''حدس اولام''' (به یاد [[استنی‌سواف اولام]])، '''مسئله کاکوتانی''' (به یاد شیزو کاکوتانی)، '''حدس توایتس''' (به یاد برایان توایتس)، '''الگوریتم هاسه''' (به یاد [[هلموت هاسه]]) یا '''مسئله سیراکوس'''.<ref>{{cite book |last1=Maddux |first1=Cleborne D. |last2=Johnson |first2=D. Lamont |year=1997 |title=Logo: A Retrospective |publisher=Haworth Press |location=New York |isbn=0-7890-0374-0 |page=160 |quote=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.}}</ref>{{refn|According to {{named ref|name=Lagarias (1985)}} p. 4, the name "Syracuse problem" was proposed by Hasse in the 1950s, during a visit to [[Syracuse University]].}} دنباله اعداد ظاهر شده در این حدس را برخی مواقع '''دنباله تگرگی''' یا '''اعداد تگرگی''' (به این دلیل که مقادیرش اغلب همچون [[تگرگ]] درون یک ابر، چندین نزول و صعود دارند)<ref>{{cite book |last=Pickover |first=Clifford A. |year=2001 |title=Wonders of Numbers |url=https://archive.org/details/wondersnumbersad00pick |url-access=limited |publisher=Oxford University Press |location=Oxford |isbn=0-19-513342-0 |pages=[https://archive.org/details/wondersnumbersad00pick/page/n136 116]–118}}</ref><ref name=hn>{{cite web |title=Hailstone Number |url=http://mathworld.wolfram.com/HailstoneNumber.html |work=MathWorld |publisher=Wolfram Research}}</ref> یا '''اعداد شگرف''' می‌نامند.<ref>{{cite book |last=Hofstadter |first=Douglas R. |author-link=Douglas Hofstadter |year=1979 |title=Gödel, Escher, Bach |publisher=Basic Books |location=New York |isbn=0-465-02685-0 |pages=[https://archive.org/details/godelescherbach00doug/page/400 400–2]|title-link=Gödel, Escher, Bach}}</ref>

[[پاول اردوش]] در مورد حدس کولاتز گفت: «ممکن است ریاضیات برای چنین مسائلی هنوز آمادگی نداشته باشد.»<ref name="Guy (2004)">{{cite book |last=Guy | first=Richard K. | author-link=Richard K. Guy | title=Unsolved problems in number theory | publisher=[[Springer-Verlag]] |edition=3rd | year=2004 |isbn=0-387-20860-7 | zbl=1058.11001 | chapter="E17: Permutation Sequences" |pages=336–7 |chapter-url=https://books.google.com/books?id=1AP2CEGxTkgC&pg=PA337}}</ref> همچنین او جایزه ۵۰۰ دلاری را برای جواب آن اعلام نمود.<ref>{{cite journal |last=Guy |first=R. K. |year=1983 |title=Don't try to solve these problems |url=https://archive.org/details/sim_american-mathematical-monthly_1983-01_90_1/page/35 |journal=Amer. Math. Monthly |volume=90 |issue= 1|pages=35–41 |jstor=2975688 |doi=10.2307/2975688}} By this Erdos means that there aren't powerful tools for manipulating such objects.</ref> جفری لاگاریاس در ۲۰۱۰ بیان نمود که حدس کولاتز «مسئله‌ای است که دشواری عجیباً زیادی داشته و کاملاً از دسترس ریاضیات کنونی خارج است.»<ref name="Lagarias (2010)">{{cite book |editor1-last=Lagarias |editor1-first=Jeffrey C. |editor1-link=Jeffrey Lagarias |year=2010 |title=The Ultimate Challenge: the 3''x'' + 1 problem |url=https://archive.org/details/isbn_9780821849408 |publisher=[[American Mathematical Society]] |isbn=978-0-8218-4940-8 |zbl=1253.11003}}</ref>

== بیان مشکل ==
:عملیات زیر را در مجموعه [[اعداد صحیح مثبت]] اختیاری در نظر بگیرید
* اگر عدد [[اعداد زوج و فرد|زوج]] بود، آن را بر ۲ تقسیم کن.
* اگر عدد [[فرد]] بود، آن را سه برابر کن و با ۱ جمع کن.
برای مثال، اگر عملیات روی ۳ انجام شود، نتیجه ۱۰ است و اگر روی ۲۴ اجرا شود نتیجه ۱۲ است.
اگر بخواهیم این عملیات را به صورت تابعی [[ریاضی]] نشان دهیم به صورت زیر خواهد بود:
{{چپ‌چین}}
 <math> f(n) = \begin{cases} n/2 &\mbox{if } n \equiv 0 \pmod{2}\\ 3n+1 & \mbox{if } n\equiv 1 \pmod{2}. \end{cases} </math>
{{پایان چپ‌چین}}

هم اکنون با اجرا کردن این عملیات بر روی یک [[دنباله]] از اعداد به‌طور متوالی با هر [[عدد صحیح]] مثبت، و گرفتن نتیجه به عنوان ورودی مرحله بعد:
در حالی که:
{{چپ‌چین}}
: <math> a_i = \begin{cases}n & \mbox{for } i = 0 \\ f(a_{i-1}) & \mbox{for } i> 0. \end{cases}</math>
{{پایان چپ‌چین}}
حدس کولاتز به صورت زیر است:

'''این روند به صورت اتفاقی به عدد ۱ می‌رسد، صرف نظر از این که چه عددی به عنوان عدد اولیه انتخاب شده'''.

کوچکترین i که به ازای آن روند فوق ادامه می‌یابد '''زمان کلی ایست n''' نام دارد. این حدس ادعا دارد که هر عدد n یک زمان کلی ایست خوش تعریف دارد. اگر به ازای یک N خاص، عدد i به صورت بیان شده وجود نداشته باشد می‌گوییم N یک زمان کلی ایست نامحدود دارد و حدس غلط است.
اگر حدس غلط باشد می‌تواند فقط به این دلیل باشد که یک عدد شروعی وجود دارد که به دنباله خاتمه‌ای می‌دهد که ۱ شامل آن دنباله نیست. یک چنین دنباله‌ای ممکن است وارد چرخه‌ای شود که از ۱ مستثنی باشد یا این که بدون محدودیت ادامه یابد. تا به حال چنین دنباله‌ای پیدا نشده‌است.

== مثال‌ها ==
:برای نمونه، شروع از n=۶، دنباله به صورت:
{{چپ‌چین}}
۶، ۳، ۱۰، ۵، ۱۶، ۸، ۴، ۲، ۱
{{پایان چپ‌چین}}
شروع از n=۱۱، دنباله بیشتر طول می‌کشد تا به ۱ برسد:
{{چپ‌چین}}
۱۱، ۳۴، ۱۷، ۵۲، ۲۶، ۱۳، ۴۰، ۲۰، ۱۰، ۵، ۱۶، ۸، ۴، ۲، ۱
{{پایان چپ‌چین}}
اگر مقدار عدد شروع n=۲۷ باشد، یک دنباله ۱۱۱ قدمی به وجود می‌آید که قبل از رسیدن به ۱ از ۹۰۰۰ تجاوز می‌کند:
{{چپ‌چین}}
{ ۲۷، ۸۲، ۴۱، ۱۲۴، ۶۲، ۳۱، ۹۴، ۴۷، ۱۴۲، ۷۱، ۲۱۴، ۱۰۷، ۳۲۲، ۱۶۱، ۴۸۴، ۲۴۲، ۱۲۱، ۳۶۴، ۱۸۲، ۹۱، ۲۷۴، ۱۳۷، ۴۱۲، ۲۰۶، ۱۰۳، ۳۱۰، ۱۵۵، ۴۶۶، ۲۳۳، ۷۰۰، ۳۵۰، ۱۷۵، ۵۲۶، ۲۶۳، ۷۹۰، ۳۹۵، ۱۱۸۶، ۵۹۳، ۱۷۸۰، ۸۹۰، ۴۴۵، ۱۳۳۶، ۶۶۸، ۳۳۴، ۱۶۷، ۵۰۲، ۲۵۱، ۷۵۴، ۳۷۷، ۱۱۳۲، ۵۶۶، ۲۸۳، ۸۵۰، ۴۲۵، ۱۲۷۶، ۶۳۸، ۳۱۹، ۹۵۸، ۴۷۹، ۱۴۳۸، ۷۱۹، ۲۱۵۸، ۱۰۷۹، ۳۲۳۸، ۱۶۱۹، ۴۸۵۸، ۲۴۲۹، ۷۲۸۸، ۳۶۴۴، ۱۸۲۲، ۹۱۱، ۲۷۳۴، ۱۳۶۷، ۴۱۰۲، ۲۰۵۱، ۶۱۵۴، ۳۰۷۷، ۹۲۳۲، ۴۶۱۶، ۲۳۰۸، ۱۱۵۴، ۵۷۷، ۱۷۳۲، ۸۶۶، ۴۳۳، ۱۳۰۰، ۶۵۰، ۳۲۵، ۹۷۶، ۴۸۸، ۲۴۴، ۱۲۲، ۶۱، ۱۸۴، ۹۲، ۴۶، ۲۳، ۷۰، ۳۵، ۱۰۶، ۵۳، ۱۶۰، ۸۰، ۴۰، ۲۰، ۱۰، ۵، ۱۶، ۸، ۴، ۲، ۱ }
{{پایان چپ‌چین}}
[[پرونده:Collatz5.svg|800px|وسط]]

== برنامه‌ای برای محاسبه دنباله کولاتز ==
:یک دنبالهٔ معین کولاتز به راحتی محاسبه می‌شود، همان طور که در [[شبه کد]] زیر نمایش داده شده:
<syntaxhighlight lang="python">
   while n> 1
     show n
     if n is odd
       set n to 3n + 1
     else
       set n to n / 2
   show n
</syntaxhighlight>
این [[برنامه]] وقتی دنباله به ۱ می‌رسد، برای جلوگیری از چاپ [[چرخه بی پایان]] ۴و۲و۱، متوقف می‌شود.
اگر حدس کولاتز درست باشد، این برنامه صرف نظر از عدد ورودی همیشه متوقف می‌شود.

== اثبات استدلال ==
:هرچند که این حدس هنوز اثبات نشده‌است، ولی اکثر ریاضیدانان که این مشکل را بررسی کرده‌اند، خود به خود اعتقاد دارند که این حدس درست است.
در این قسمت دو دلیل برای این انتظار درستی بیان می‌کنیم:
:
:<big>'''مدارک آزمایشی'''</big>

:این حدس توسط [[رایانه]] برای تمام صحیح مثبت تا ۱۰ × ۲<sup>۵۸</sup>&nbsp;≈&nbsp;۲٫۸۸{{e|۱۸}}[http://www.ieeta.pt/~tos/3x+1.html] امتحان شده‌است.
با تعجب باید گفته شود که این گونه مقید کردن‌ها توسط رایانه ارزش مدرکی بسیار محدودی دارند. چندین حدس وجود دارند که مثال نقضشان به‌طور استثنایی مقداری بسیار بزرگ است.(مانند [[حدس پولیا]]، [[حدس مرتن]] یا [[عدد اسکیوویز]])
همچنین این موضوع که، {۴٬۲٬۱} تنها [[چرخه]] با دورهٔ کمتر از ۳۵۴۰۰ است، روشن شده‌است.

=== مدارک احتمالی ===
:اگر کسی تنها [[اعداد فرد]] تولید شده در دنبالهٔ کولاتز را در نظر بگیرد، آنگاه کسی می‌تواند استدلال کند که در حالت [[میانگین]](در حالت خاص [[میانگین هندسی]] قسمتها) عدد فرد بعدی باید ¾قبلی باشد، که اظهار می‌کند این دسته اعداد باید با ترتیبی طولانی کاهش یابند.(اگرچه این مدرکی علیه چرخه‌ها نیست، فقط علیه [[واگرایی]] است)

== دیدگاه‌های دیگر دربارهٔ موضوع ==
=== در حالت معکوس ===
:دیدگاه دیگری برای اثبات این حدس به کار می‌رود، که روش رشد از بالا به پایین را در نظر می‌گیرد که [[گراف کولاتز]] نام دارد.
[[گراف]] کولاتز گرافی است که با رابطهٔ [[معکوس]] زیر تعریف می‌شود:
{{چپ‌چین}}
<math> R(n) = \begin{cases} 2n & \mbox{if } n\equiv 0,1,2,3,5 \\ 2n, (n-1)/3 & \mbox{if } n\equiv 4 \end{cases} \pmod{6}. </math>
{{پایان چپ‌چین}}
بنابراین به جای این که ثابت کنیم همهٔ [[اعداد طبیعی]] به‌طور اتفاقی به ۱ می‌رسند، می‌توانیم ثابت کنیم که ۱ به تمام اعداد طبیعی سوق داده می‌شود. برای تمام اعداد صحیح
همچنین، رابطهٔ معکوس، به جز حلقهٔ ۱و۲و۴، یک درخت است([[وارون]] حلقه ۱و۴و۲ یک تابع بدون تغییر است که در عبارت مشکل بالا مطرح شده‌است). وقتی رابطهٔ ۳n+۱ در تابع (f(n، با جانشینی رایج «میان بر» با رابطهٔ ۳n + ۱)/۲) جا به جا شود([[بهینه سازی]] زیر را ببینید)، گراف کولاتز با رابطهٔ وارون زیر تعریف می‌شود:
{{چپ‌چین}}
<math> R(n) = \begin{cases} 2n & \mbox{if } n\equiv 0,1 \\ 2n, (2n-1)/3 & \mbox{if } n\equiv 2 \end{cases} \pmod{3}. </math>
{{پایان چپ‌چین}}
این رابطهٔ معکوس، به جز حلقهٔ ۱-۲، به شکل یک درخت در می‌آید (معکوس حلقهٔ ۱-۲در تابع (f(n، همانطور که نشان داده شد، در بالا بازبینی شده‌است)

=== به عنوان اعداد گویا ===
[[اعداد طبیعی]] می‌توانند با به‌کارگیری روشی مشخص، به [[اعداد گویا]] تبدیل شوند. براای به دست آوردن مدل گویا، بزرگترین عدد توان ۲ که کمتر مساوی [[عدد اصلی]] است پیدا کنیدو آن را به عنوان مخرج در نظر بگیرید. سپس آن را از عدد اصلی کم کنید و به عنوان صورت در نظر بگیرید (۱۵/۵۱۲→۵۲۷). برای به دست آوردن مدل طبیعی عدد صورت و مخرج کسر را با هم جمع کنید (۵۱۱→ ۲۵۵/۲۵۶).

حدس کولاتز می‌گوید که صورت سرانجام برابر صفر می‌شود. تابع کولاتز به صورت زیر تغییر می‌کند:
{{چپ‌چین}}
: <math> f(n, d) = \begin{cases} (3n + d + 1)/2d  & \mbox{if } 3n + d + 1 <2d \\
(3n - d + 1)/4d & \mbox{if } 3n + d + 1 \ge 2d \end{cases} </math>
(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 ۲:
  ##
  ##  ۱۱۱
  ##  ۱۰۱۱۰
  ##  ۱۰۱۱
  ##  ۱۰۰۰۱۰
  ##  ۱۰۰۰۱
  ##  ۱۱۰۱۰۰
  ##  ۱۱۰۱
  ##  ۱۰۱۰۰۰
  ##  ۱۰۱
  ##  ۱۰۰۰۰
  ##  ۱
  ##
{{پایان چپ‌چین}}

=== به عنوان یک تابع زوج ===
:برای این قسمت تابع کولاتز را که اندکی تغییر کرده را در نظر بگیرید:
{{چپ‌چین}}
: <math> f(n) = \begin{cases} n/2 &\mbox{if } n \equiv 0 \\ (3n +1)/2 & \mbox{if } n \equiv 1 \end{cases} \pmod{2}.</math>
{{پایان چپ‌چین}}
ما مجوز ایجاد این تغییر را داریم زیرا وقتی n فرد است ۳n+۱ همیشه زوج است. اگر (...)Pزوجیت یک عدد باشد، به صورتی که P(۲n) = ۰ و P(۲n + ۱) = ۱. پس ما می‌توانیم دنبالهٔ زوجیت کولاتز را برای یک عدد n به صورت ('p<sub>i</sub>'' = P(''a<sub>i</sub>''که ''a''<sub>۰</sub> = ''n'' و(''a''<sub>''i''+۱</sub> = ''f''(''a''<sub>''i''</sub> تعریف می‌کنیم.

استفاده از این شکل (f(n می‌تواند نشان دهد که [[دنباله زوجیت|دنبالهٔ زوجیت]] برای دو عدد m,n در k دورهٔ اول مساوی است اگر و تنها اگر m,n به پیمانهٔ <sup>''k''</sup>۲برابر باشند. این موضوع به این اشاره دارد که هر عدد به‌طور خاص با دنبالهٔ زوجیت خود شناخته می‌شود و علاوه بر این اگر حلقه‌های کولاتز متعددی وجود داشت، حلقهٔ زوجیت متناظر با آن‌ها نیز باید متفاوت باشد.
اثبات این موضوع بسیار ساده‌است، می‌توان به صورت [[شهودی]] و بسیار ساده مشاهده کرد که اعمال f تابع ،k بار بر عدد''a'' ۲<sup>''k''</sup>+''b عدد ''a'' ۳<sup>''c''</sup>+''d'' را نتیجه خواهد داد، که d نتیجهٔ اعمال f تابع ،k بار بر عدد b است و c عددی است که نشان می‌دهد چه تعداد عدد فرد در طی این دنباله به دست آمده‌است بنابراین زوجیت k عدد اول به کلی با b معین می‌شود و زوجیت عدد k+۱ام، اگر آخرین عدد پرمعنیa تغییر کند، تغییر خواهد کرد.
حدس کولاتز را می‌توان به این صورت بیان کرد که، زوجیت دنبالهٔ کولاتز برای هر عدد نهایتاً وارد حلقهٔ ۰ → ۱ → ۰ می‌شود.

=== مانند یک سیستم برچسب ===
:برای تابع کولاتز به فرم:
{{چپ‌چین}}
: <math> f(n) = \begin{cases} n/2 &\mbox{if } n \equiv 0 \\ (3n +1)/2 & \mbox{if } n \equiv 1 \end{cases} \pmod{2}</math>
{{پایان چپ‌چین}}
دنباله‌های کولاتز توسط [[سیستم]] بسیار ساده ۲-برچسبی که قانون حاصل جمع آن به صورت زیر است محاسبه می‌شوند:
{{چپ‌چین}}
: <math> \begin{cases} a \rarr bc \\ b \rarr a \\ c \rarr aaa \end{cases}</math>
{{پایان چپ‌چین}}
و به صورتی که عدد صحیح مثبت 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''<sub>۰</sub>, …, ''k''<sub>''m''-۱</sub>، آنگاه کسر منحصربه‌فرد که حلقهٔ زوجیت را به وجود می‌آورد برابر:
{{چپ‌چین}}
:<math>\frac{3^{m-1} 2^{k_0} + ... + 3^0 2^{k_{m-1}}}{2^n - 3^m}</math>
{{پایان چپ‌چین}}.
برای مثال، حلقهٔ زوجیت (۱ ۰ ۱ ۱ ۰ ۰ ۱) دارای طول ۷ و ۴ عدد فرد به صورت ۰٬۲٬۳ است و کسر منحصربه‌فرد که حلقهٔ زوجیت را تولید می‌کند برابر:
{{چپ‌چین}}
:<math>\frac{3^3 2^0 + 3^2 2^2 + 3^1 2^3 + 3^0 2^6}{2^7 - 3^4} = \frac{151}{47}</math>
{{پایان چپ‌چین}}.
حلقهٔ کامل موجود به صورت:
۱۵۱/۴۷ → ۸۵/۴۷ → ۱۷۰/۴۷ → ۳۴۰/۴۷ → ۲۱۱/۴۷ → ۱۲۵/۴۷ → ۲۵۰/۴۷ →
۱۵۱/۴۷

هرچند [[جایگشت]]‌های تناوبی دنباله‌های زوجیت اصلی کسرهایی منحصربه‌فرد هستند ولی حلقه منحصربه‌فرد نیست. هر کسر جایگشت برابر عدد بعدی در دور حلقه‌است:
{{چپ‌چین}}
:(۰ ۱ ۱ ۰ ۰ ۱ ۱) → <math>\frac{3^3 2^1 + 3^2 2^2 + 3^1 2^5 + 3^0 2^6}{2^7 - 3^4} = \frac{250}{47}</math>
{{سخ}}
:(۱ ۱ ۰ ۰ ۱ ۱ ۰) → <math>\frac{3^3 2^0 + 3^2 2^1 + 3^1 2^4 + 3^0 2^5}{2^7 - 3^4} = \frac{125}{47}</math>
{{سخ}}
:(۱ ۰ ۰ ۱ ۱ ۰ ۱) → <math>\frac{3^3 2^0 + 3^2 2^3 + 3^1 2^4 + 3^0 2^6}{2^7 - 3^4} = \frac{211}{47}</math>
{{سخ}}
:(۰ ۰ ۱ ۱ ۰ ۱ ۱) → <math>\frac{3^3 2^2 + 3^2 2^3 + 3^1 2^5 + 3^0 2^6}{2^7 - 3^4} = \frac{340}{47}</math>
{{سخ}}
:(۰ ۱ ۱ ۰ ۱ ۱ ۰) → <math>\frac{3^3 2^1 + 3^2 2^2 + 3^1 2^4 + 3^0 2^5}{2^7 - 3^4} = \frac{170}{47}</math>
{{سخ}}
:(۱ ۱ ۰ ۱ ۱ ۰ ۰) → <math>\frac{3^3 2^0 + 3^2 2^1 + 3^1 2^3 + 3^0 2^4}{2^7 - 3^4} = \frac{85}{47}</math>
{{پایان چپ‌چین}}
همچنین برای منحصربه‌فردی، دنباله‌های زوجیت باید «[[اول]]» باشد. نباید قابل تقسیم به زبر دنباله‌های یکسان باشد. برای مثال، دنباله‌های زوجیت (۱ ۱ ۰ ۰ ۱ ۱ ۰ ۰) می‌تواند به دو زیر دنبالهٔ یکسان(۱ ۱ ۰ ۰)(۱ ۱ ۰ ۰) تقسیم شود. محاسبهٔ کسر ۸-عاملی این دنباله نشان می‌دهد:
{{چپ‌چین}}
:(۱ ۱ ۰ ۰ ۱ ۱ ۰ ۰) → <math>\frac{3^3 2^0 + 3^2 2^1 + 3^1 2^4 + 3^0 2^5}{2^8 - 3^4} = \frac{125}{175}</math>
{{پایان چپ‌چین}}
ولی وقتی کسر را ساده کنیم {۵/۷} مانند همان زیر دنبالهٔ ۴-عاملی است:
{{چپ‌چین}}
:(۱ ۱ ۰ ۰) → <math>\frac{3^1 2^0 + 3^0 2^1}{2^4 - 3^2} = \frac{5}{7}</math>
{{پایان چپ‌چین}}
و این به این دلیل است که دنبالهٔ زوجیت ۸-عاملی در واقع دو حلقه از دور حلقه‌ای تعریف شده توسط زیر دنبالهٔ ۴-عاملی است.

در این زمینه، حدس کولاتز برابر با این است که بگوییم(۰،۱) تنها حلقه‌ای است که تمام اعداد مثبت ایجاد می‌شود.

=== تکرار روی [[اعداد حقیقی]] یا اعداد مختلط ===
[[پرونده:CobwebCollatz2.PNG|بندانگشتی|۳۰۰px|نمودار تار عنکبوت در دور ۱۰-۵-۸-۴-۲-۱-۲-۱-۲-۱-… در بسط حقیقی نگاشت کولاتز
(توسط جایگزینی “۳n+۱”با “۳n+۱)/۲)”بهینه شده‌است)
")]]
[[نگاشت]] کولاتز را می‌توان به عنوان یک محدودیت برای اعداد حقیقی یا اعداد مختلط نشان داد:
{{چپ‌چین}}
:<math>f(z):=\frac 1 2 z \cos^2\left(\frac \pi 2 z\right)+(3z+1)\sin^2\left(\frac \pi 2 z\right)</math>،
{{پایان چپ‌چین}}
پس از [[ساده سازی]]:
{{چپ‌چین}}
<math>\frac{1}{4}(2 + 7z - (2 + 5z)\cos(\pi z))</math>.
{{پایان چپ‌چین}}
اگر نگاشت [[استاندارد]] کولاتزی که در بالا تعریف شده توسط جایگزینی “۳n+۱”با “۳n+۱)/۲)”بهینه شده باشد، این موضوع می‌تواند نشان داده شود که یک محدودیت برای اعداد حقیقی یا اعداد مختلط است:
{{چپ‌چین}}
:<math>f(z):=\frac 1 2 z \cos^2\left(\frac \pi 2 z\right)+\frac 1 2 (3z+1)\sin^2\left(\frac \pi 2 z\right)</math>
{{پایان چپ‌چین}}،
پس از ساده سازی:
{{چپ‌چین}}
<math>\frac{1}{4}(1 + 4z - (1 + 2z)\cos(\pi z))</math>
{{پایان چپ‌چین}}.
تکرار نگاشت بهینه‌سازی شدهٔ فوق در صفحهٔ [[اعداد مختلط]] [[فراکتال]] کولاتز را ایجاد می‌کند.
<div style="clear:both;"></div>

== بهینه سازیها ==
:در قسمت «زوجیت» راهی برای سرعت بخشیدن به [[شبیه سازی]] دنباله ارائه شد. برای جلو افتادن k قدم در هر تکرار (با استفاده از تابع f در همان قسمت)، عدد فعلی را به دو قسمت تقسیم می‌کنیم،b(kتا کم ارزشترین رقم‌ها)، و a (بقیه رقم‌های عدد). نتیجه جلو پریدن k+c[b] قدم به صورت زیر خود را نشان می‌دهد:
:''f'' <sup>''k''+''c''[b]</sup>(''a'' ۲<sup>''k''</sup>+''b'') = ''a'' ۳<sup>''c''[b]</sup>+''d''[b]
مقادیر c,d برای تمام اعداد K-بیتی ممکن از قبل محاسبه شده‌است که d[a] نتیجه اعمال k بار تابع f روی b است، و c[a]تعداد اعداد فرد در طول مسیر است.
برای مثال اگر ،k=۵ باشد، می‌توان ۵ قدم در هر تکرار توسط جدا کردن ۵ تا از [[کم ارزشترین رقم]]‌ها به جلو پرید و استفاده از:
{{چپ‌چین}}
: ''c'' [۰...۳۱] = {۰٬۳٬۲٬۲٬۲٬۲٬۲٬۴٬۱٬۴٬۱٬۳٬۲٬۲٬۳٬۴٬۱٬۲٬۳٬۳٬۱٬۱٬۳٬۳٬۲٬۳٬۲٬۴٬۳٬۳٬۴٬۵}
: ''d'' [۰...۳۱] = {۰٬۲٬۱٬۱٬۲٬۲٬۲٬۲۰٬۱٬۲۶٬۱٬۱۰٬۴٬۴٬۱۳٬۴۰٬۲٬۵٬۱۷٬۱۷٬۲٬۲٬۲۰٬۲۰٬۸٬۲۲٬۸٬۷۱٬۲۶٬۲۶٬۸۰٬۲۴۲}
{{پایان چپ‌چین}}

== تابع [[سیراکوس]] ==
:اگر k یک عدد فرد باشد، آنگاه ۳k+۱ زوج است، پس می‌توانیم بنویسیم ۳''k'' + ۱ = ۲<sup>a</sup>''k′''، K یک عدد فرد و a ≥ ۱ است. ما تابع f را از روی مجموعهٔ Iاز اعداد فرد به روی خودش تعریف می‌کنیم، که تابع سیراکوس نام دارد، با فرض این که{{چپ‌چین}} f (k) = k′{{پایان چپ‌چین}}
برخی از خواص تابع سیراکوس:
*	برای تمام kها درI{{چپ‌چین}} f (۴k + ۱) = f (k){{پایان چپ‌چین}}
*	برای تمام p ≥ ۲ و hهای فرد،{{چپ‌چین}}f p - ۱(۲ p h - ۱) = ۲ ۳ p - ۱h – ۱{{پایان چپ‌چین}}
*	برای تمام hهای فرد،{{چپ‌چین}}f (۲h - ۱) ≤ (۳h - ۱)/۲{{پایان چپ‌چین}}
حدس سیراکوس این است که برای تمام kها در I، وجود دارد عدد صحیح n ≥ ۱ به صورتی که{{چپ‌چین}}''f'' <sup>''n''</sup>(''k'') = ۱{{پایان چپ‌چین}}. به‌طور هم ارز، فرض می‌کنیم E مجموعه اعداد فرد k باشد که عدد صحیح n ≥ ۱ وجود دارد به صورتی که{{چپ‌چین}}''f'' <sup>''n''</sup>(''k'') = ۱{{پایان چپ‌چین}}باشد. مشکل این است که نشان دهیم E=I است. در ادامه تلاشی را برای اثبات از طریق استقرا آغاز می‌کنیم:
میدانیم ۱و۳و۵و۷و۹ در E وجود دارند. فرض می‌کنیم k عددی فرد بزرگتر از ۹ باشد. فرض می‌کنیم که k-۲ و تمام اعداد فرد قبل از آن در E هستند و اثبات می‌کنیم که kدر E است. وقتی k یک عدد فرد است پس می‌توان نتیجه گرفت {{چپ‌چین}}''k'' + ۱ = ۲<sup>''p''</sup>''h''{{پایان چپ‌چین}} برای p ≥ ۱ و hهای فرد و{{چپ‌چین}} ''k'' = ۲<sup>''p''</sup>''h''-۱{{پایان چپ‌چین}}پس حالا داریم:
*	اگر p=۱، آنگاه k=۲h-۱. به راحتی می‌توان امتحان کرد که f (k) <k، بنابراین f (k) ∈ E از اینرو k ∈ E.
*	اگر p ≥ ۲و hمضرب ۳ باشد، می‌توانیم بنویسیم{{چپ‌چین}}h = ۳h′{{پایان چپ‌چین}}. فرض می‌کنیم{{چپ‌چین}} ''k′'' = ۲<sup>''p'' + ۱</sup>''h′'' - ۱{{پایان چپ‌چین}}پس داریم f (k′) = k، و تا زمانی که{{چپ‌چین}}k′ <k، k′{{پایان چپ‌چین}}در E وجود دارد، بنابراین k = f (k′) ∈ E.
*	اگر p ≥ ۲و hمضرب ۳ نباشد ولی h ≡ (-۱)<sup>p</sup> mod ۴ ولی باز هم می‌توان نشان داد k ∈ E.
قسمت مشکل ساز آنجاست که p ≥ ۲و hمضرب ۳ نباشد و h ≡ (-۱)<sup>p+۱</sup> mod ۴. در اینجا اگر سعی کنیم که نشان دهیم که برای هر عدد صحیح فرد′k،

{{چپ‌چین}}۱ ≤k′≤ k-۲ ; ۳k′ ∈ E{{پایان چپ‌چین}}
کار تمام است.

== جستارهای وابسته ==
* [[نظریه اعداد]]

== ارجاعات ==
{{پانویس|چپ‌چین=بله|2|
refs=

===مقالات===
<ref name="Lagarias (1985)">{{cite journal |first=Jeffrey C. |last=Lagarias |title=The 3''x'' + 1 problem and its generalizations |url=https://archive.org/details/sim_american-mathematical-monthly_1985-01_92_1/page/3 |journal=[[The American Mathematical Monthly]] |volume=92 |issue=1 |pages=3–23 |year=1985 |jstor=2322189|doi=10.1080/00029890.1985.11971528 }}</ref>

}}

== منابع ==
{{چپ‌چین}}
{{آغاز پانویس|2}}
* [[Jeffrey Lagarias|Jeffrey C. Lagarias]]. [http://arxiv.org/abs/math.NT/0309224 ''The 3x + 1 problem: An annotated bibliography (1963–2000)''].
* Jeffrey C. Lagarias. [http://arxiv.org/abs/math.NT/0608208 ''The 3x + 1 problem: An annotated bibliography, II (2001–)''].
* Jeffrey C. Lagarias. [http://www.cecm.sfu.ca/organics/papers/lagarias/ ''The 3x + 1 problem and its generalizations''], American Mathematical Monthly Volume 92، 1985، pp. 3–23.
* {{SpringerEOM | urlname=S/s110330 | title=Syracuse problem | author=Jeffrey C. Lagarias}}
* Günther J. Wirsching. The Dynamical System Generated by the <math>3n+1</math> Function. Number 1681 in Lecture Notes in Mathematics. Springer-Verlag, 1998.
* An ongoing [[رایانش توزیع‌شده|distributed computing]] [http://www.ericr.nl/wondrous/index.html project] by Eric Roosendaal verifies the Collatz conjecture for larger and larger values.
* Another ongoing [[رایانش توزیع‌شده|distributed computing]] [http://www.ieeta.pt/~tos/3x+1.html 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).
* {{MathWorld | urlname=CollatzProblem | title=Collatz Problem}}
* {{PlanetMath | urlname=CollatzProblem | title=Collatz Problem}}
* [https://web.archive.org/web/20040925215956/http://members.aol.com/mensanator666/collatz/hailstone.htm Hailstone Patterns] discusses different resonators along with using important numbers in the problem (like 6 and 3^5) to discover patterns.
* [http://www.numbertheory.org/3x+1/ Keith Matthews' 3x+1 page: Review of progress, plus various programs]
* Ohira, Reiko & Yamashita, Michinori [https://web.archive.org/web/20080406061036/http://www.ris.ac.jp/yamasita/open/p-col.pdf A generalization of the Collatz problem]
* URATA, Toshio [https://web.archive.org/web/20080406061036/http://auemath.aichi-edu.ac.jp/~turata/Fall.files/CTZVI.pdf Some Holomorphic Functions connected with the Collatz Problem]
* Matti K. Sinisalo: [https://web.archive.org/web/20080307175738/http://www.geocities.com/mattiksinisalo/collatz.doc On the minimal cycle lengths of the Collatz sequences], Preprint, June 2003، University of Oulu
* Paul Stadfeld: [https://web.archive.org/web/20070926231400/http://home.versatel.nl/galien8/blueprint/blueprint.html Blueprint for Failure: How to Construct a Counterexample to the Collatz Conjecture]
* Liesbeth De Mol: [http://logica.ugent.be/liesbeth/TagColOK.pdf «Tag systems and Collatz-like functions»], Preprint (Nr. 314), to appear in ''Theoretical Computer Science''.
* Kawasaki Hiroyuki: [https://web.archive.org/web/20080420065803/http://www.crt.or.jp/~kokochi/kaknodK/kaknodKe.htm] Claimed proof of Collatz conjecture
* Alain Slakmon and Luc Macot: [http://www.colvir.net/prof/luc.macot/On%20the%20almost%20sure%20convergence%20of%20Syracuse%20sequences.pdf «On the Almost Sure Convergence of Syracuse Sequences»] {{Webarchive|url=https://web.archive.org/web/20070929070546/http://www.colvir.net/prof/luc.macot/On%20the%20almost%20sure%20convergence%20of%20Syracuse%20sequences.pdf |date=۲۹ سپتامبر ۲۰۰۷ }}, Statistics & Probability Letters
76 (15), 2006، 1625-1630.
* {{youtube|id=BhR-iIjhTNM|title=Collatz Iterations on the Ulam Spiral grid}}
* [http://demonstrations.wolfram.com/CollatzPaths/ Collatz Paths] by Jesse Nochella, [[The Wolfram Demonstrations Project]].
{{پایان پانویس}}
{{پایان چپ‌چین}}

[[رده:حدس‌ها]]
[[رده:حساب]]
[[رده:دنباله اعداد صحیح]]
[[رده:دینامیک حسابی]]
[[رده:مسئله‌های حل‌نشده در ریاضیات]]
[[رده:نظریه اعداد]]
[[رده:مسائل حل‌نشده در نظریه اعداد]]