Collatz Conjecture: Difference between revisions

{{Infobox software

| name                = Collatz Conjecture

| screenshot          =

| caption              =

'''Collatz Conjecture''' was a volunteer distributed computing project built on the [[wikipedia:Berkeley Open Infrastructure for Network Computing|BOINC]] platform. Based in Wood Dale, Illinois, it is a privately managed project run by administrator Jon Sonntag, dedicated to computationally testing the famous [[wikipedia:Collatz conjecture|Collatz conjecture]] in mathematics, also widely known as the '''3x+1 problem''' or '''HOTPO''' (Half Or Triple Plus One).<ref name="boinc_wiki">{{cite web |url=https://boinc.berkeley.edu/wiki/Collatz_Conjecture |title=Collatz Conjecture |publisher=BOINC Berkeley |date=9 May 2013 |access-date=2026-06-07}}</ref><ref name="project_home">{{cite web |url=https://boinc.thesonntags.com/collatz/ |title=Collatz Conjecture project home |author=Jon Sonntag |access-date=2026-06-07}}</ref> The project continues work begun by the earlier '''3x+1@home''' BOINC project, which ended in 2008.<ref name="bcteam">{{cite web |url=https://wiki.bc-team.org/index.php?title=Collatz_Conjecture/en |title=Collatz Conjecture |publisher=BC-Wiki |access-date=2026-06-07}}</ref>

== The Collatz Conjecture ==

As a striking example, starting from <math>n = 27</math>, the sequence takes 111 steps and climbs as high as 9,232 before descending to 1. Starting from <math>n = 26</math>, by contrast, only 10 steps are needed. There is no obvious pattern to how long a number takes to reach 1 (its '''total stopping time'''), which is part of what makes the problem so difficult.

The problem goes by several other names in the literature: the '''Ulam conjecture''' (after [[wikipedia:Stanislaw Ulam|Stanislaw Ulam]]), '''Kakutani's problem''' (after [[wikipedia:Shizuo Kakutani|Shizuo Kakutani]]), the '''Thwaites conjecture''' (after Sir Bryan Thwaites), and the '''Syracuse problem'''.<ref name="wp_collatz" />

== Computational verification ==

Although no general proof exists, computers have verified the conjecture for enormous ranges of integers. As of the most recent exhaustive computations, the conjecture has been confirmed to hold for all positive integers up to <math>2^{68} \approx 2.95 \times 10^{20}</math> (roughly 295 quintillion), with no counterexample found.<ref name="tao2019">{{cite arXiv |last=Tao |first=Terence |title=Almost all orbits of the Collatz map attain almost bounded values |eprint=1909.03562 |year=2019}}</ref><ref name="springer2025">{{cite journal |title=Computational verification of the Collatz conjecture up to 2^71 |journal=The Journal of Supercomputing |year=2025 |doi=10.1007/s11227-025-07337-0}}</ref>

=== Technical details ===

The project makes use of the '''parity sequence optimization''', a well-known algorithmic shortcut that condenses multiple Collatz steps into a single operation by analyzing the parity (odd/even) pattern of consecutive iterations, allowing the software to skip redundant even-division steps and test more integers per unit time.<ref name="tsbt">{{cite web |url=https://tsbt.co.uk/forum/viewtopic.php?t=9264 |title=Collatz Conjecture New Project Details |publisher=The Scottish BOINC Team |access-date=2026-06-07}}</ref>

== Scientific context ==

=== The 3x+1 problem in the literature ===

The Collatz Conjecture BOINC project is not the only computational effort aimed at the problem. The '''yoyo@home''' BOINC project independently checked all positive integers up to <math>10^{20} \approx 2^{66.4}</math> for convergence in 2017, using CPU-based methods with roughly 1,000 volunteers.<ref name="springer2025" /> A separate standalone computation by Tomas Oliveira e Silva in 2009 verified the conjecture up to approximately <math>5.76 \times 10^{18} \approx 2^{62.3}</math>.<ref name="springer2025" /> Collatz Conjecture BOINC focuses specifically on testing much larger numbers in ranges above what exhaustive sequential verification has covered.

== See also ==