Collatz Computations in Base 2 and 3
Every so often, the Collatz conjecture comes up in discussion forums I read, and I start to think about it again. I did for a bit this past weekend. Here are my thoughts this time around.
The Problem
A Collatz sequence starts with some positive integer x₀ and develops the sequence inductively as xₙ₊₁= xₙ / 2 if xₙ is even, or 3xₙ + 1 if xₙ is odd. For instance, starting with 13, we get:
- x₀ = 13
- x₁ = 3(13) + 1 = 40
- x₂ = 40 / 2 = 20
- x₃ = 20 / 2 = 10
- x₄ = 10 / 2 = 5
- x₅ = 3(5) + 1 = 16
- x₆ = 16 / 2 = 8
- x₇ = 8 / 2 = 4
- x₈ = 4 / 2 = 2
- x₉ = 2 / 2 = 1
- x₁₀ = 3(1) + 1 = 4
- x₁₁ = 4 / 2 = 2
- x₁₂ = 2 / 2 = 1
From there, it’s apparent that the sequence repeats 1, 4, 2, 1, 4, 2, … forever. That is one way for a Collatz sequence to end up. The famous question here, known as the Collatz Conjecture, is whether it’s the only way any such sequence can terminate. Not necessarily! There could be other cycles besides 1, 4, 2. Or there could be a sequence that keeps increasing forever without repeating a number. Or maybe that never happens. No one knows!
We do know a few things. First, if these things happen, they only happen with astronomically large numbers that even powerful computers haven’t been able to check by hand. We know that if even a single number is repeated, then that part of the sequence will repeat forever, since the whole tail of the sequence is determined by any single number in it. And we know that such a sequence cannot decrease forever, since Collatz sequences remain positive integers, so eventually would reach number that we know end up in the 1,4,2 loop. We also know that there are other loops in Collatz sequences that begin with negative integers, so the fact that there have been none found so far in the positive integers is at least a little surprising.
The Collatz Conjecture is famous because it’s probably one of the easiest unsolved math problem to understand the meaning of, for mathematical novices. There’s no Riemann zeta function to define. Just even and odd numbers, division by two, multiplication by three, and adding one. That doesn’t mean it’s easy to solve, though! Many mathematicians and countless novices have spent decades working on the problem, and there’s no promising road to a solution. The mathematician Erdős suggested that it’s not simply that no one has found the solution, but that mathematics is lacking even the basic tools needed to work on this problem.
Collatz and Alternate Bases
There are many, many ways to think about the Collatz conjecture, but one of them is to look at the computation in different bases. We’re not really attempting to find a more efficient way to compute Collatz sequences. If we cared about that, it would be far more efficient to use whatever representation our computing hardware is designed for! Rather, what we’re looking for here is the possibility of some kind of pattern in the computation that reveals something analytical about the problem.
Addition works essentially the same way the same regardless of base, but computations involved in multiplication and division are very dependent on the choice of base! Since the definition of the Collatz sequence two natural choices for computing Collatz sequences are base 2 (binary) and base 3 (ternary).
- In base 2, it’s trivial to decide whether a number is even or odd, and to divide by two. On the other hand, computing 3n+1 is less trivial, requiring a pass over potentially every digit in the number.
- In base 3, the opposite happens. Computing 3n+1 is now trivial. But recognizing that a number is even and dividing by two now require a pass over every digit.
Let’s jump into the details and see what happens.
Base 3 in Detail
Base 3 representations are appealing for the Collatz sequence because it’s trivial to compute 3n+1. It amounts to simply adding a 1 to the end of the representation, shifting everything else left (i.e., multiplying it by 3) to make room. If you have n = 1201 (decimal 46), for example, then 3n+1 = 12011 (demical 139).
The more difficult tasks are:
- Determining whether the number is even or odd. Unlike decimal, we cannot simply look at the last digit. Instead, a number in base 3 is even if and only if it has an even number of 1s in its representation. That’s not hard to count, but it does require looking at the entire sequence of digits.
- Dividing by two. Given a sequence of base 3 digits, we can express the division algorithm on right-to-left numbers as a state machine using the long division algorithm with remainders as states (starting with zero), using the following division table.
Let’s see how this table works with an example. Starting again with 1201 (decimal 46):
- We always start with a remainder of 0. The first digit is 1. That’s the second line of the table. The output digit is, therefore, 0, and the next remainder is 1.
- A remainder of 1 and a digit of 2 is the last line of the table. It tells us to add a 2 to the output, and proceed with a remainder of 1.
- A remainder of 1 and a digit of 0 is the fourth line. We add a 1 to the output, and proceed with a remainder of 1.
- A remainder of 1 and a digit of 1 is the fifth line. We add a 2 to the output and proceed with a remainder of 0.
- We’re now out of digits. The quotient is 0212 (decimal 23, but note that leading zero which we’ll talk about later!) and the remainder is 0.
Naively, we would have to make two passes over the current number: one to determine whether it’s even or odd, and then again, if it’s even, to divide by two. We can avoid this, though, by remembering that if a number is odd, we intend to compute 3n+1, which will always be even (because the product of two odd numbers is odd, so adding one makes it even), so we’ll then divide that by two. A little algebra reveals that (3n+1)/2 = 3(n/2 - 1/2) + 2 = 3⌊n/2⌋ + 2 if n is odd.
What this means is that we can go ahead and halve n regardless of whether it’s even or odd. At the end, we’ll know whether there’s a remainder or not, and if so, we will already be in position to append a 2 (rather than a 1 as discussed earlier) to the halved number and rejoin the original sequence. This skips one step of the Collatz sequence, but that’s okay. If our goal is only to determine whether the sequence eventually reaches 1, it doesn’t change the answer if we take this shortcut.
Appending that 2 to the end of the number changes the meaning of our state transition table a little bit. Instead of automatically quitting when we reach the end of the current number, we’ll need a chance to append another digit at the end. We’ll add rows to the table for what to do after all the digits have been seen, and be explicit about when to terminate (i.e., finish processing).
There’s one more detail we can handle as we go: as we saw earlier, dividing by two can produce a leading zero at the beginning of the result, which is unnecessary. We can arrange to never produce that leading zero at all, so we don’t need to ignore or remove it later. We just need to remember where we’re just starting and therefore don’t need to write leading zeros. In that case, the remainder is always zero, so there’s only one state to add.
We get the following state transition table.
Since there are no leading zeros in the representations, we need not concern ourselves with the case where the first digit encountered is a zero, but if you want to handle it, we can produce no output and remain in the Just Starting state, since it ought to change nothing. I’ve done so in the code below.
We can iterate this state machine on ternary numbers, and get consecutive values from the Collatz sequence, though slightly abbreviated because we combined the 3n+1 step with the following division by 2. The Collatz conjecture is now equivalent to the proposition that this iterated state machine will eventually produce only a single 1 digit.
I’ve implemented this in the Haskell programming language as follows:
import Data.Foldable (traverse_)
import System.Environment (getArgs)
data Ternary = T0 | T1 | T2 deriving (Eq, Read, Show)
step3 :: [Ternary] -> [Ternary]
step3 = si
where
si (T0 : xs) = si xs
si (T1 : xs) = s1 xs
si (T2 : xs) = T1 : s0 xs
si [] = []
s0 (T0 : xs) = T0 : s0 xs
s0 (T1 : xs) = T0 : s1 xs
s0 (T2 : xs) = T1 : s0 xs
s0 [] = []
s1 (T0 : xs) = T1 : s1 xs
s1 (T1 : xs) = T2 : s0 xs
s1 (T2 : xs) = T2 : s1 xs
s1 [] = [T2]
main :: IO ()
main = do
[n] <- fmap read <$> getArgs
traverse_ print (iterate step3 n)And here’s a sample result:
$ cabal run exe:collatz3 ‘[T1, T2, T0, T1]’ | head -15
[T1,T2,T0,T1]
[T2,T1,T2]
[T1,T0,T2,T2]
[T1,T2,T2,T2]
[T2,T2,T2,T2]
[T1,T1,T1,T1]
[T2,T0,T2]
[T1,T0,T1]
[T1,T2]
[T2,T2]
[T1,T1]
[T2]
[T1]
[T2]
[T1]Starting with 1201 (decimal 46), we get 212 (decimal 23), 1022 (decimal 35), 1222 (decimal 53), 2222 (decimal 80), 1111 (decimal 40), 202 (decimal 20), 101 (decimal 10), 12 (decimal 5), 22 (decimal 8), 11 (decimal 4), 2, 1, 2, 1, … As predicted, that’s the Collatz sequence, except for the omission of 3n+1 terms since their computation is merged into the following division by two.
Base 2 in Detail
So what happens in base 2 (binary)? It’s a curiously related but different story!
- Determining whether a number is even or odd is trivial: just look at the last bit and observe whether it is 0 or 1.
- Dividing an even number by two is trivial: once you observe that the last digit is a 0, simple delete it, shifting the remaining bits to the right to fill in.
- However, computing 3n+1 becomes less trivial, now requiring a pass over the entire digit sequence.
Since the hard step is multiplication, and the algorithmically natural direction to perform multiplication is from right to left, we can reverse the order in which we visit the bits, progressing from the least-significant to the most-significant. This is a change from the base 3 case, where division (the inverse of multiplication) was easier to perform in the left-to-right order.
We can start as before, by writing down a simple state transition table for a state machine that multiplies a binary number by 3. The state here is represented by the number carried to the next column.
(You might recognize this as the same table we already wrote down for halving a ternary number! The only differences are the column headers: the role of states and digits are swapped, and that we must traverse the digits in the opposite order.)
There’s one unfortunate subtlety to this table, and it has to do with leading zeros again. In principle, we think of a number in any base as having an infinite number of leading zeros on the left. In order to get correct results from this table, we need to continue consuming more digits until both the remaining digits and the current remainder are all zero. To express this, we’ll again need to convert our transition table to use explicit termination. This is so that we can stop at exactly the right point and not emit any unnecessary trailing zeros.
But what about the rest of the logic of the Collatz sequence?
- We should add one after tripling to compute 3n+1. That would also require a pass over potentially the entire number in the worst case… but we’re in luck. We can combine the two tasks just by starting from the Carry 1 state when following this state transition diagram.
- If the number is even, we should divide by two. Recall how in the ternary case, we merged some of the halving with the 3n+1 computation? This time, we can merge all the halving! Dividing even numbers by two just means dropping trailing zeros from the right side of the representation. Since we’re working right to left, it’s easy to add one more state that ignores trailing zeros at the start of the input.
We need to be a little careful here, because this version of the Collatz sequence never emits a 1, so looking for a 1 in the sequence is doomed! Instead, the numbers displayed are only the ones immediately after a 3n+1 step, so the final behavior (for all numbers computed so far, anyway) is an infinitely repeating sequence of 4s. We know from earlier that 4 is part of the 1,4,2 cycle, so seeing 4s is enough to know that the full Collatz sequence passes through 1.
We can fix this by remembering refusing to emit any of the trailing zeros. Now we’re ignoring trailing zeros, but also never producing them. The blowup in the number of states needed to keep track of whether a zero has been emitted yet is unfortunate, because we may pass through multiple states before emitting the first non-zero digit. Each of those states needs a copy that handles this new case. Here’s our final transition table.
Here’s the implementation in Haskell:
import Data.Foldable (traverse_)
import System.Environment (getArgs)
data Binary = B0 | B1 deriving (Eq, Show, Read)
step2 :: [Binary] -> [Binary]
step2 = si
where
si (B0 : xs) = si xs
si (B1 : xs) = s2i xs
si [] = [B1]
s0 (B0 : xs) = B0 : s0 xs
s0 (B1 : xs) = B1 : s1 xs
s0 [] = []
s1 (B0 : xs) = B1 : s0 xs
s1 (B1 : xs) = B0 : s2 xs
s1 [] = [B1]
s1i (B0 : xs) = B1 : s0 xs
s1i (B1 : xs) = s2i xs
s1i [] = [B1]
s2 (B0 : xs) = B0 : s1 xs
s2 (B1 : xs) = B1 : s2 xs
s2 [] = [B0, B1]
s2i (B0 : xs) = s1i xs
s2i (B1 : xs) = B1 : s2 xs
s2i [] = [B1]
main :: IO ()
main = do
[n] <- fmap read <$> getArgs
traverse_ print (iterate step2 n)And a result:
$ cabal run exe:collatz2 '[B1, B0, B1, B1, B0, B1]' | head -80
[B1,B0,B1,B1,B0,B1]
[B1,B0,B0,B0,B1]
[B1,B0,B1,B1]
[B1,B0,B1]
[B1]
[B1]
[B1]We start with 101101 (45 in decimal). We triple and add one to get 136, then half to get 68, then 34, then 17, which is the next value that appears (10001 = 17 in decimal). We triple and add one to get 52, then half to get 26, then 13, which is 1101 in binary, and the third number in the list. (Remember the bits are listed from right to left!) Now triple and add one to get 40, and half until you reach 5, which is 101 in binary and the fourth number in the list. Finally, triple and add one to get 16, and half until you reach 1, which is where it stays.
Analysis
Is this a promising avenue to attack the Collatz Conjecture? Almost surely not. I’m not sure anyone knows a promising way to solve the problem. Nevertheless, we can ask what it might look like if one were to use this approach to attempt some progress on the conjecture.
One way (in fact, in some sense, the only way) to solve the Collatz Conjecture is to find some kind of quantity that:
- Takes its minimum possible value for the number 1.
- Always decreases from one element of a Collatz sequence to the next, except at 1.
- Cannot decrease forever.
If such a quantity exists, then a Collatz sequence must eventually reach 1, so the Collatz Conjecture must be true — and conversely, in fact, if the Collatz Conjecture is true, then such a quantity must exist, since the number of steps to reach 1 would then be exactly such a quantity. This is equivalent to the original conjecture, which is why I commented that proving this is the only way to solve it! But this way of looking at the conjecture is interesting because it lets you define any quantity you like, as long as it has those three properties.
We know a lot of things that this quantity isn’t. It can’t be just the magnitude of the number, since that can increase with the 3n+1 rule. It also can’t be the number of digits (in any base), since that can increase sometimes, as well. Plenty of people have looked for other quantities that work. It’s useful to me to think of the quantity as a measure of the “entropy” (or rather its opposite, since it’s decreasing). It’s something you lose any time you take a step, and this tells you that eventually you will reach some minimum state, which must be the number 1.
Just guessing a quantity is unlikely to work. But if you can come to some understanding of the behavior of these computations, it’s conceivable there’s a quantity embedded in them somewhere that satisfies these conditions. If this entropy value is calculated digit by digit, you may be able to isolate how it changes in response to each of these state transition rules.
It is, at the very least, one point of view from which one might start thinking. I never claimed to have any answers! This was always just a random train of thought.
