Collatz Conjecture: Unveiling Fractal Patterns
Beyond Chaos: Signals of Self-Affinity in a Simple Rule
Overview
The Collatz sequence, also known as the 3n + 1 problem or hailstone numbers, is named after the German mathematician Lothar Collatz, who first introduced it in 1937. This deceptively simple process leads to what is known as the Collatz Conjecture, one of the most intriguing unsolved problems in mathematics.
Despite its straightforward formulation, the sequence’s unpredictable behavior and the absence of a general proof for all positive integers have fascinated mathematicians for decades.
How the Collatz Sequence Works
Let a0=n be any positive integer. Define the Collatz sequence {ak} recursively by:
The Collatz Conjecture asserts that for all starting values n∈N+, the sequence eventually reaches 1. Once the sequence reaches 1, it enters the cycle 1→4→2→1.
In most computational implementations and visualisations, the sequence is conventionally considered to stop at the first occurrence of 1.
https://github.com/ratwolfzero/Collatz
Why Is It Challenging?
Despite the extremely simple rules, the Collatz Conjecture remains unsolved. The conjecture claims:
No matter what positive integer you start with,
the sequence will eventually reach 1
So far, no counterexamples have been found, and the conjecture has been verified for vast ranges of integers, yet no general proof (or disproof) exists. Its deceptive simplicity masks a deep mathematical complexity — small changes in input can result in long, chaotic trajectories, making it notoriously resistant to analysis.
This puzzle sits at the crossroads of number theory, recursion, and computational chaos.
Stopping Time: The Hidden Rhythm
The stopping time of a number in the Collatz sequence is the smallest number of steps required to reach 1. While seemingly simple, this metric reveals fractal-like patterns when analyzed statistically. Below are key insights from computational experiments:
Each point represents a starting number n and its stopping time. The cloud-like distribution shows no obvious formula, but clusters suggest modular dependencies (e.g., numbers ≡3 (mod 4) often have higher stopping times).
The right-skewed distribution indicates most numbers collapse to 1 quickly, while a few outliers (like n = 27) require disproportionately many steps. This aligns with Terras’ theorem that almost all numbers have finite stopping times.
The rolling average (window=100) reveals a logarithmic growth trend, consistent with Lagarias’ bound k ≈ 3.476 log n. Deviations suggest “resonance” effects from arithmetic progressions.
New Perspectives: Fractal Analogies and Empirical Evidence
Beyond its general logarithmic growth, a closer look at the deviations and irregularities in the rolling average diagram of Collatz stopping times reveals a striking visual resemblance to the Weierstrass function. This mathematical construct is famous for being continuous everywhere but differentiable nowhere, creating a curve that exhibits intricate detail and “wiggles” at every level of magnification — a classic example of a fractal.
This visual similarity prompts intriguing questions and leads to two compelling conjectures, now supported by empirical evidence:
Conjecture on Statistical Self-Affinity:
It is conjectured that the curve generated by the rolling average of the Collatz sequence step counts exhibits statistical self-affinity over multiple scales. This implies an underlying fractal-like structure, where patterns of irregularity are repeated, though not identically, across different ranges of numbers, reflecting the deep complexity of the Collatz map.
Conjecture on Weierstrass-like Irregularity:
The “nowhere differentiability” or extreme irregularity seen in the Weierstrass function may serve as a powerful analogy for understanding the inherent local unpredictability and complexity within the Collatz sequence’s step counts. This suggests that the erratic deviations from the smooth logarithmic trend are not merely noise, but a fundamental characteristic pointing to a profound connection between number theory and the properties of continuous, fractal functions.
Get Ralf Becker’s stories in your inbox
Join Medium for free to get updates from this writer.
These conjectures suggest that the visual characteristics of the Collatz rolling average might not be mere coincidence but could point towards deeper mathematical structures that could offer new avenues for understanding this enduring problem.
📉 Patterns in the Chaos: Derivatives and Frequencies
To probe deeper into the structure of Collatz stopping times and rigorously test these conjectures, I computed the rolling average over a large range of ’n’, then analyzed its numerical derivative and frequency spectrum.
🔍 Derivative: Persistent Local Irregularity
The numerical derivative of the rolling average reveals persistent local fluctuations — the curve never truly settles to a smooth, flat line. This continuous irregularity echoes properties of fractal functions like the Weierstrass function, which are continuous but nowhere differentiable.
This observation strongly suggests non-random, structured oscillations at all scales, indicating that the local unpredictability is an intrinsic feature, not just noise.
⚡ FFT: Robust Power-Law Decay Indicating Fractal Behavior
Next, I applied a Fast Fourier Transform (FFT) to the rolling average. The resulting power spectrum, plotted on a log-log scale, shows a clear power-law decay with a spectral exponent β.
Through systematic testing with various FFT window types (Hann, Hamming, Blackman) and different rolling average window sizes (50, 100, 200, 500), the spectral exponent consistently fell within the range of β≈2.20−2.30. This consistency is crucial, as it indicates a reliable measurement of the underlying spectral properties.
Examples (window size=200)
Power-law exponent (beta): 2.00 with rectangular window
Power-law exponent (beta): 2.29 with hann window
Power-law exponent (beta): 2.24 with hamming window
Power-law exponent (beta): 2.29 with blackman window
This kind of spectral behavior, characterized by a β value significantly greater than 1 (pink noise) or 0 (white noise), is a definitive hallmark of long-range correlations and scale-invariant (fractal-like) systems.
- A spectral exponent of β≈2.2−2.3 corresponds to a Hurst exponent (H) of approximately 0.60−0.65. Since H>0.5, this confirms that the Collatz stopping times exhibit strong persistence. This means that if the stopping times have been trending upwards (or downwards) over a range of starting numbers, they are more likely to continue that trend.
- This also implies a fractal dimension (D) of roughly 1.35−1.40 for the graph of the smoothed stopping times (where D=(5−β)/2). This value, greater than the topological dimension of 1, reinforces the notion of a fractal curve that is rough, yet exhibits structured irregularity, consistent with its persistent nature.
⚠️ Why This Matters — and Why It Might Not
These results are not a mathematical proof of the Collatz conjecture itself. However, they provide compelling empirical evidence that:
- The stopping time function is not just chaotic noise; it possesses a quantifiable, non-random structure.
- There is hidden structure and statistical self-affinity in how Collatz stopping times evolve, characteristic of a fractal process with long-range memory.
While visual resemblance and robust spectral regularity are powerful indicators, to go further, future work would ideally involve:
- More extensive statistical validation across even larger scales and ranges.
- Rigorous comparisons with randomized or surrogate data to confirm the uniqueness of these patterns.
- Development of a theoretical framework linking these observed fractal properties to the iterative dynamics of the Collatz map.
Still, this empirical approach opens an intriguing new angle — one where number theory meets signal analysis, and the profound complexity of the Collatz problem might be revealed through its emergent fractal structure rather than just its elusive solution.
🔍 Current State of Research
The Enduring Mystery of the Collatz Conjecture
Despite extensive efforts spanning decades, a general proof for the Collatz Conjecture remains elusive. This deceptively simple problem — which asserts that all positive integers eventually reach 1 when repeatedly subjected to a specific set of rules — has stubbornly resisted resolution.
Numerical Verification and Its Limits
Mathematically, the conjecture has been numerically verified to an astonishing degree. Distributed computing projects have exhaustively checked all starting numbers up to 2^68, covering values deep into the quintillions. While shortcut methods allow for partial verification beyond this range, and extremely large individual numbers — such as 2^100000−1 or those with millions of digits — have been tested without producing a counterexample, these checks come with inherent limitations. Computational verification confirms only specific cases, and the exponential growth of the search space makes verifying all numbers within large ranges practically impossible.
Theoretical Progress and Persistent Challenges
In 2019, Fields Medalist Terence Tao made a major theoretical breakthrough by showing that almost all Collatz orbits reach 1 when analyzed through a probabilistic lens. Although this represents significant progress, it still falls short of a complete proof. More speculative lines of inquiry suggest the conjecture may touch on undecidable logic or exhibit computational irreducibility — concepts implying that a solution might lie beyond the reach of current mathematical tools. If true, the Collatz Conjecture may not just be unsolved, but unprovable within existing formal systems.
🧩 What the Experts Say
Even though the Collatz Conjecture is easy to state, it has resisted proof for over 85 years. Many brilliant mathematicians have commented on its strange mix of simplicity and complexity:
🧠 Paul Erdős, legendary mathematician, once said:
“Mathematics is not yet ready for such problems.”
— on the Collatz Conjecture📘 Jeffrey Lagarias, a leading expert, called it:
“The simplest unsolved problem in mathematics.”
He also remarked:
“If this is true, then it’s a fantastic result. If it’s false, it’s even more fantastic.”🔄 John Conway, creator of the Game of Life, once said:
“The Collatz problem is like a weed: it grows on its own and is impossible to kill.”
Conway believed the problem may even encode undecidable logic — hinting at its profound depth.🧮 Terence Tao, Fields Medalist, commented in a 2019 paper:
“The trajectory of the Collatz iteration behaves more like a random process than a deterministic one.”
Tao showed that “almost all” numbers reach 1, but the full conjecture remains unproven.
