Exploring the Collatz Conjecture
A Tale of Two Sieves
The Collatz Conjecture is famous for its deceptively simple rules: Take any positive integer. If it is even, cut it in half. If it is odd, multiply it by 3 and add 1. Repeat. The conjecture boldly claims that no matter what number you start with, you will always eventually plunge into the inescapable loop of 4 → 2 → 1.
This morning I woke up dreaming about the Collatz conjecture (as I often do these days), but in an interesting new way: As a tale of two sieves. The accelerated or compressed Collatz map known as the Syracuse function
always maps an even number to an odd number and an odd number to an odd number, as the denominator is the largest power of 2 dividing the numerator.1
If 2|n or 3|n, 2 and 3 will never divide S(n) again. That is, iterating S(n) will subsequently always be ±1(mod6). That is, sieving out multiples of 2 and multiples of 3. After the first iteration, every Syracuse sequence bounces around between ±1(mod6), always eventually hitting 1, if the conjecture is true.
Mathematicians have thrown everything from advanced number theory to massive computational brute force at this problem, yet it remains unsolved. As I awoke, the question rattling around in my brain was: what if we stop looking at Collatz as an arithmetic pinball machine, and instead look at it as a tale of two sieves?
To see these sieves at work, we need to speed up the process. Instead of taking the conjecture step-by-step where each division by 2 is a step in itself, we can accelerate, or compress, it using the Syracuse function above. This function groups the “multiply by 3, add 1” step with all the subsequent “divide by 2” steps into a single leap.
We noted above that the denominator of the Syracuse function represents the highest power of 2 that divides 3n + 1. By dividing out all the 2s at once, the Syracuse operator guarantees one thing: its output is always an odd number.
And right there, we have encountered our first sieve.
In the standard formulation of the Collatz conjecture, a number might bounce between odd and even for a long time. But through the lens of the Syracuse function, the even numbers are structurally annihilated.
Once one passes a number through S(n), 2 will never divide the result. The compressed Collatz Syracuse sequence is now restricted entirely to the realm of odd numbers. But the sieving doesn’t stop there.
Let’s take a closer look at the numerator of our function: 3n + 1.
Note that any multiple of 3, when 1 is added to it, is no longer a multiple of 3. Therefore, 3n + 1 can never be divided by 3. And because our denominator only divides out powers of 2, the final output of the operator will also remain completely indivisible by 3.
If 3|n (if 3 divides the starting number, n), after just one iteration of the Syracuse function, 3 can never divide any other number in the resulting sequence again.
So, where does a sequence go when it is perpetually stripped of all multiples of 2 and all multiples of 3? It gets pushed into a very specific mathematical corner.
In modular arithmetic, any number that is neither divisible by 2 nor 3 must leave a remainder of either 1 or 5 when divided by 6.2 In other words, after the very first iteration, every number in the resulting Syracuse sequence is trapped forever bouncing within the congruence classes of:
This is a significant structural limitation. The Syracuse sequence isn’t just wandering randomly through the integers; it is locked in a highly restricted modular channel.
If one is a big fan of prime numbers (as am I and countless others), that channel should look very familiar. Every prime number greater than 3 is precisely of the form 6k + 1 or 6k - 1. The Syracuse sequence is forced to dance exclusively through the exact same modular landscape where the prime numbers reside.
Exploring the Collatz conjecture as a “Tale of Two Sieves” based on the Syracuse function shifts our perspective. It moves us away from asking, “Why does this number bounce so high?” and towards asking, “What happens to a Collatz sequence when the fabric of its divisibility by 2 and 3 is permanently torn away?”
For one thing, if we treat the numbers generated by the Syracuse function probabilistically (which is a very standard and useful heuristic when analyzing Collatz), any given number in a Syracuse sequence is three times more likely to be prime as a number chosen at random. Are there patterns in the occurrence of prime numbers in Syracuse sequences? If so, what are they and why are they there?
Note that Syracuse sequences are strictly deterministic, not truly random. Because of this, we can’t definitively say that every sequence will contain a prime, or that a given sequence will hit primes exactly 3 times more often than a random sequence. For example, a sequence could theoretically get trapped in a long chain of highly composite numbers that are ±1(mod6).
Why not vibe code a Syracuse Sequence Prime Analyzer to explore a bit and see:
For the notorious starting value 27, which converges to 1 after 41 Syracuse function iterations, we find 24 of those landed on prime numbers. That’s significantly more than a third of the time. Interesting. I wonder if there are any starting values that encounter less than a third primes? I haven’t found one yet. More interesting!
Play around with it yourself, see what you can find:3
Syracuse Sequence Prime Analyzer
Be all that as it may, what we do know is that because of the two sieves, Syracuse sequences bounce around in this prime-inhabited space of ±1 (mod6), continually shedding its factors of 2 and avoiding factors of 3, until the structural tension completely resolves itself, and the sequence cascades down to 1.4
Proving why every such sequence always terminates at 1 remains the holy grail. Seeing the sequence not as a random walk, but as a tightly constrained trajectory through a twin-sieved numerical space inhabited by prime numbers greater than 3 may help to bring us a wee bit closer to understanding the seemingly fathomless, profoundly opaque, architecture of the natural numbers.
The denominator is the 2-adic valuation of 3n + 1.
6n+0 is divisible by both 2 and 3; 6n+2=2(3n+1) is divisible by 2; 6n+3=3(2n+1) is divisible by 3; 6n+4=2(3n+2) is divisible by 2. Only 6n+1 and 6n+5 are not divisible by either 2 or 3. But 6n+1≡1(mod6) and 6n+5≡5(mod6)≡-1(mod6). Therefore, the only numbers that are not multiples of 2 or 3, hence, not divisible by either 2 or 3 are ±1(mod6).
You can input large odd numbers (up to 2^53 - 1 = 9,007,199,254,740,991, and the program won’t crash, but your browser page might. And unless the odd starting number converges to 1 within a reasonable amount of steps, you might have to wait a long time for a response. If you encounter a starting number with less that a third of its associated sequence consisting of prime numbers, please leave a comment below.
Again, assuming the Collatz Conjecture is true.
Sure enough, I found a starting value that results in a sequence with fewer than a third primes. Where there is one, there are bound to be an infinite number of others. Finding a sequence with no primes whatsoever might prove to be somewhat more difficult task though.