Collatz Conjecture

Collatz Conjecture
Collatz Conjecture logo
Project
Status	Inactive
Category	Mathematics
Compute	CPU & GPU
Requires	OpenCL driver (GPU); Microsoft Visual C++ Redistributable (CPU)
Development
Developer	Jon Sonntag
Author	Jon Sonntag
Sponsor	Self-funded (private)
Maintainer	Jon Sonntag
Initial release	January 6, 2009  (17 years ago)
Software
Written in	C, C++ (CPU); OpenCL (GPU)
Operating system	Windows, Linux, macOS, Android
BOINC statistics
Stats as of	January 19, 2022  (4 years ago)
Performance	13254678.71 GigaFLOPS
Active users	1,949
Total users	67,352
Active hosts	4,887
Total hosts	433,270
Metadata
Website	https://boinc.thesonntags.com/collatz/
License	Proprietary (closed source)

Collatz Conjecture was a volunteer distributed computing project built on the BOINC platform. Based in Wood Dale, Illinois, it is a privately managed project run by administrator Jon Sonntag, dedicated to computationally testing the famous Collatz conjecture in mathematics, also widely known as the 3x+1 problem or HOTPO (Half Or Triple Plus One). The project continues work begun by the earlier 3x+1@home BOINC project, which ended in 2008.

The Collatz Conjecture

The Collatz conjecture is one of the most famous and enduring unsolved problems in mathematics. It was first proposed by German mathematician Lothar Collatz (6 July 1910 – 26 September 1990) in 1937, two years after receiving his doctorate from the University of Berlin under Alfred Klose. Despite its deceptively elementary statement, the conjecture has resisted all attempts at a general proof for nearly ninety years.

Statement of the conjecture

Define the Collatz function $f$ on the positive integers as follows:

$f(n)=\{\begin{array}{ll}n/2& \text{if }n\equiv 0(\mathrm{mod}2)\\ 3n+1& \text{if }n\equiv 1(\mathrm{mod}2)\end{array}$

Given any starting positive integer $n$, one forms a sequence by repeatedly applying $f$:

$n,f(n),f^2(n),f^3(n),\dots$

The Collatz conjecture asserts that no matter which positive integer $n$ is chosen, this sequence will eventually reach the number 1.

A common shortcut collapses the two steps applied to an odd number into one, giving the equivalent Syracuse map:

$T(n)=\frac{3n+1}{2^{v_2(3n+1)}}$

where $v_2$ denotes the 2-adic valuation (the largest power of 2 dividing the argument). This form is used in several efficient computational implementations.

Hailstone sequences

Because the values in a Collatz sequence rise and fall unpredictably before eventually reaching 1, they are often called hailstone sequences or hailstone numbers, a name that evokes the way real hailstones tumble up and down inside a thundercloud before finally falling to the ground. They are also sometimes called wondrous numbers.

As a striking example, starting from $n=27$, the sequence takes 111 steps and climbs as high as 9,232 before descending to 1. Starting from $n=26$, 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 Stanislaw Ulam), Kakutani's problem (after Shizuo Kakutani), the Thwaites conjecture (after Sir Bryan Thwaites), and the Syracuse problem.

Reactions from mathematicians

The difficulty of the conjecture is legendary. Paul Erdős, one of the most prolific mathematicians of the twentieth century, is reported to have said: Mathematics may not be ready for such problems. Jeffrey Lagarias, who has compiled the definitive research bibliography on the problem, wrote in 2010 that the conjecture is an extraordinarily difficult problem, completely out of reach of present day mathematics.

Computational verification

All Collatz sequences of a length inferior to 20

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 $2^{68}\approx 2.95\times 10^{20}$ (roughly 295 quintillion), with no counterexample found.

A notable milestone is Terence Tao's 2019 paper "Almost all orbits of the Collatz map attain almost bounded values," which proved that for any function $f:\mathbb{\mathbb{N}}\to \mathbb{ℝ}$ with $\underset{N\to \mathrm{\infty }}{\lim }f(N)=+\mathrm{\infty }$, the minimum element of the Collatz orbit of $N$ satisfies ${\mathrm{C}\mathrm{o}\mathrm{l}}_{\min }(N)\le f(N)$ for almost all $N$ in the sense of logarithmic density. While not a full proof, this was widely regarded as the most significant theoretical advance on the problem in decades.

A more recent effort, published in The Journal of Supercomputing (2025), pushed the verified limit to $2^{71}$ using GPU-accelerated algorithms distributed across several European supercomputers, with a total acceleration of $1,335\times$ compared to baseline CPU implementations and the discovery of four new path records along the way.

About the BOINC project

Origins

The Collatz Conjecture BOINC project was launched in 2009 by Jon Sonntag of Wood Dale, Illinois, continuing work left off by the earlier 3x+1@home BOINC project, which had ended in 2008. The project is self-funded and privately operated, without university or government backing — something its administrator has cited as a point of pride, demonstrating that a single motivated individual working part-time can run a competitive BOINC project.

The project's stated goal is to search for a counterexample to the Collatz conjecture — a starting number whose sequence never reaches 1. Since all numbers below a given threshold have been verified elsewhere, the project focuses on progressively larger ranges, having started from around $2^{71}$. As Sonntag put it in a 2011 interview, at peak activity volunteers were collectively testing roughly 40 quadrillion numbers per day, far exceeding initial expectations.

GPU computing and early milestones

Collatz Conjecture holds a notable place in BOINC history as one of the first projects to support AMD/ATI graphics cards without requiring volunteers to supply a custom app_info.xml file. This was made possible by collaborations with BOINC community developers "Crunch3r" (who contributed BOINC client work) and "Gipsel" (who wrote hand-optimized GPU assembly code for ATI hardware). These contributions, and Gipsel's hand-written GPU assembly in particular, demonstrated how much faster GPU-based computation could be compared to CPU-only methods.

At the time the project launched in 2009, MilkyWay@home was essentially the only other BOINC project supporting ATI GPU computing, and it suffered from frequent outages. Sonntag explicitly wanted to give GPU volunteers an alternative, and also to push the frontier of GPU support within BOINC.

Technical details

Collatz Fractal

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.

The application is available for multiple platforms and computing devices:

Platform	Supported devices
Windows	CPU, NVIDIA GPU (CUDA), AMD GPU (OpenCL), Intel GPU (OpenCL)
Linux	CPU, NVIDIA GPU, AMD GPU, Intel GPU
macOS	CPU, GPU (OpenCL)
Android	CPU

For GPU computing, minimum requirements include an AMD Radeon HD 5000 or later with OpenCL 1.1 support, an NVIDIA GeForce 8400 GS or later with a recent NVIDIA driver, or an Intel HD 2500 or later with Intel's OpenCL runtime.

Because spammers created large numbers of bogus accounts in the project's early years, invite codes are required to register. The code changes periodically and is available from the project administrator.

2018 hardware failure

In early 2018 the project suffered a complete hardware failure, and nearly all data was lost. Credit totals were eventually recovered and restored to participants. Shortly after recovering, new achievement badges were introduced for the project.

Reliability and downtime

As a privately hosted project, Collatz Conjecture has experienced periodic outages over the years, typically related to server hardware, dynamic DNS configuration, or code-signing key renewal. The project's forum and server share the same infrastructure, which can complicate communication during outages. When such events occur, the administrator has generally addressed them promptly via BOINC community forums.

Credit and performance

Collatz Conjecture is well known within the BOINC community for issuing substantial amounts of BOINC credit relative to computation time, particularly for GPU tasks. Community benchmarks have indicated that a high-end GPU can generate on the order of millions of BOINC cobblestones per day on this project. This generosity in credit issuance has attracted both enthusiastic participants and some controversy in BOINC forums.

Scientific context

Lothar Collatz (1910–1990), the German mathematician who proposed the 3x+1 conjecture in 1937.

The 3x+1 problem in the literature

The Collatz conjecture sits at the intersection of elementary number theory and computational mathematics. The authoritative research compilation is Jeffrey Lagarias's annotated bibliography, The 3x+1 Problem: An Annotated Bibliography (2006, updated), which lists hundreds of papers touching on the problem from every angle.

Key theoretical results prior to Tao's 2019 paper include Krasikov and Lagarias (2003), who proved that the count of integers in $[1,x]$ satisfying the conjecture grows at least as fast as $x^{0.84}$ for sufficiently large $x$. Conway (1972) showed that a slight variant of the $qn+1$ problem is undecidable, suggesting the original problem sits at the very edge of the decidability threshold.

Related volunteer computing efforts

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 $10^{20}\approx 2^{66.4}$ for convergence in 2017, using CPU-based methods with roughly 1,000 volunteers. A separate standalone computation by Tomas Oliveira e Silva in 2009 verified the conjecture up to approximately $5.76\times 10^{18}\approx 2^{62.3}$. Collatz Conjecture BOINC focuses specifically on testing much larger numbers in ranges above what exhaustive sequential verification has covered.

See also

• BOINC
• Collatz conjecture
• Volunteer computing
• MilkyWay@home
• yoyo@home
• PrimeGrid

External links

• https://web.archive.org/web/20220216091746/https://boinc.thesonntags.com/collatz/ – Web Archive of the project
• https://en.wikipedia.org/wiki/Collatz_conjecture – Wikipedia: Collatz conjecture
• https://arxiv.org/abs/1909.03562 – Terence Tao (2019): "Almost all orbits of the Collatz map attain almost bounded values"
• https://boinc.berkeley.edu/wiki/Collatz_Conjecture – BOINC project listing