If you haven’t heard of Collatz sequences or Goodstein sequences, I’ll introduce them shortly. The point I’m trying to get across in this post is to convey the remarkable properties of both sequences, while comparing the two, since the Collatz sequences can be redefined into ‘partial’ base bumping part and iterated division by 2, and Goodstein sequences, if you haven’t already seen them, combine a ‘complete’ base bump with a subtraction by 1.

Let’s start with Collatz sequences since they are easier to describe [harder to prove, opposite of Goodstein sequences :-)].

If one had a good calculator that could handle really large numbers, and say I gave you any positive integer(> 0) and then told you if the number is odd, you multiply it by 3 and add 1 to get a new number, if it is even, you divide it by 2. Then do the same to the new number, if odd again, multiply by 3 and add 1, if even again, divide by 2. To each new number, do this forever. This is a Collatz sequence, or a sequence of hailstone numbers.

Mathematically, the Collatz function is a piece-wise function:

   

and is used to define the sequence of hailstone numbers recursively:



If you play enough with different initial values for you’ll notice that hailstone numbers can’t be tamed to your whims, they are volatile, chaotic, intractable, not followable. Despite the chaos though, it looks like the Collatz sequences for any initial value eventually reach 1, and if you try initial value 1 you’ll see that you get a cycle 1,4,2,1, therefore 1 cycles with itself, so once arrived at 1 the future behavior of the sequence is known. It has been verified computationally that all the Collatz sequences with initial value eventually reach 1, this record being held as of late by David Bařina (thank you David). What about past ? It is still an open question if all positive integers get to 1 starting as an initial value in the Collatz sequence. In fact, this is the notorious Collatz Conjecture, which I’m probably supposed to warn you about not working on naively thinking it has a simple solution, it’s fun to play in the sandbox and try to gain a unique intuition about the problem, but as far as tools, there aren’t any great tools at the moment to tackle the problem. Most likely some new tools are going to have to be invented, or maybe a computer scientist will solve it without even knowing they did. 



Does every Collatz sequence eventually reach 1, for any positive integer as initial value?

The usual example you’ll most likely see to demonstrate the complexity of Collatz sequences is initial value 27, in fact, this is the example on Wikipedia:







which requires 111 steps before first arriving at . Starting with 27, which is odd, thus we multiply it by 3 and add 1 to it to get , and then because 82 is even we divide by 2 to get 41, and the sequence continues as such. 27 is an interesting example, because it take a ‘really’ long time to get to 1 relative to the positive integers less than 27:

1 or , 1 is already at 1 so zero steps are needed to get to 1

as you can see, positive integers less than 27 require at most one line of text to get to 1, not .

Is it necessary that every number in these sequences be noted? For example, was it necessary to note 82 in between 27 and 41? For any odd initial value, because 3 and 1 are odd, thus we could divide by 2 after multiplying our odd input by 3 and adding 1. This describes Collatz sequences using the function, a function well known in the literature on Collatz, in fact some define the Collatz Conjecture using :

   

the sequence of hailstone numbers defined on  



with initial value requires 70 steps before getting to 1:





70 steps is less than 111, but still a lot, and is not the only acceleration out there. Another acceleration commonly used in the literature is the Syracuse iterates, only considering the odd elements of the sequence. Once an even number is reached, all of the factors of 2 are removed to get an odd number. The Syracuse function is defined only on the odd positive integers . The definition of the Syracuse iterates trades the ‘ugliness’ of a piece-wise function, for the ‘ugliness’ of having a variable number of divisions by 2 at each step:



where is the 2-adic valuation of the numerator , and 27 need 42 steps to get to 1:




I really liked how clean the Syracuse iterates worked, because if you somehow were able to figure out how many powers of 2 were in an even number you arrived at, you could just cancel them out. I wondered if something similar held on the odd numbers, and I thought it would be an impressive feature of Collatz sequences if such a clean acceleration existed on the odd numbers. At the time I was surprised to find that for and odd, by using induction with , which ends up being a generalization of the fact that fixes , , but if you really give it some thought it’s not so surprising at all. I think this fact, or even a more general version of it has been known since the year 2000(Some Results on the Collatz Problem by Andrei, Kudlek & Niculescu). More intuitively, if you examine graphs of hailstone numbers, if you have an ‘interesting’ initial value like 27, you should have many what look like ‘spikes’, and since I used , this acceleration on the odd numbers corresponds to the lime/green portions, or increasing parts of the picture, the red parts are the iterated division by 2 which correspond to the Syracuse acceleration:

In some sense the ‘increasing’ parts and ‘decreasing’ parts of Collatz sequences defined with are ‘predictable’ if you knew the ‘factorization’ of the form or for and odd. I agree, perhaps the time you save with the factorization, because the mapping is then directly or , is payed by the time taken to find the factorization, but nevertheless, if you knew it, you’d know to which even number you’d be arriving at(for increasing) or to which odd number(for decreasing).
As far as I know, there is no such acceleration which combines these odd and even accelerations together. This corresponds to the yellow lines connecting consecutive minima on the graph, or ‘cutting the spikes.’

At first I was inspired by Economics in naming this combination of accelerations, I thought maybe ‘net-profits’ or the ‘sequence of net-profits,’ or maybe ‘archimedeans’ since we’re connecting consecutive minima, i.e. taking the shortest distance between these two points, but I settled on ‘Montreal iterates’ since after all they are a twist/add-on of the Syracuse iterates and if you look on a map, Syracuse and Montreal are a short road-trip and border crossing apart. 

27 only needs 17 let’s say ‘super-steps’ to get to 1 in terms of Montreal iterates: 



Mathematically, the Montreal function is also only defined on odd positive integer inputs, and

 

where and is odd and is the 2-adic valuation of .

This concludes the introduction of the Collatz sequences, the Collatz Conjecture, and the Montreal iterates. Now to introduce the Goodstein sequences.

I heard in a podcast once that Elon Musk was obsessed with exponential functions, and studying them, I wonder if Elon Musk knows about Goodstein sequences? Okay, maybe I’m throwing a little bit of shade at Elon, but it is a genuine curiosity. It would be pretty cool if he did know about them :-). 

To describe Goodstein sequences, first, the concept of ‘complete base-b notation’ or ‘hereditary base-b notation’ needs to be introduced. Much like you can write a positive integer in base-b notation, for b a positive integer ,

where and for

‘complete base-b notation’ or ‘hereditary base-b notation’ does so to the exponents, and then the exponents of the exponents as well, and then the exponents of the exponents of the exponents, until the process can’t go any further. What does that really mean? Take a particular example, the typical example I’ve seen is 266, let’s start in base-2:



now we notice that the exponents are , and these exponents in base- are , thus:



and the exponent of the exponent is , which terminates the process because we can’t reduce elements in the ‘power-towers’ further in base-2:

.

Goodstein sequences are defined with any natural number as initial value in complete base-2 notation (I know the name ‘hereditary base-b notation’ is more popular, but I’m more familiar with and have used more the former, so I’m sticking with it) and then the base b is bumped to up by 1, and the resulting number is subtracted by 1. The new number is rewritten in complete base-(b+1) notation, and the process restarts, bump the base, subtract by 1. If a Goodstein sequence reaches 0 it is defined to be 0 forever afterwards. Keeping with 266:





The resulting number is then written in complete base-3 notation, in the above case it is already written in complete base-3 notation, and we do this again, bump the base by 1 and subtract the resulting number by 1:



and so on, and so on:











Intuitively, one would think that the base bumping is always greater than the subtraction by 1 and that these sequences diverge exponentially. Counterintuitively, Goodstein’s Theorem proves that all Goodstein sequences converge to 0. The tiny subtraction by 1 does eventually overtake the base bumping! Beautiful! The proof has to do with ordinals, and it is just as beautiful as the result itself in it’s cleverness and simplicity, I think I have a rough-sketch in my mind of understanding the proof, but I would like to refine it some more before talking about it further. There are many resources available online, Stephen G. Simpson’s Unprovable Theorems and Fast-Growing Functions was the easiest for me to understand.

That defines Goodstein sequences (I’ve avoided the cumbersome notation usually used in describing Goodstein sequences mathematically) combined with Goodstein’s Theorem, the remarkable result that all these sequences converge to 0. 

Abstractly, Collatz sequences using Montreal iterates, have increasing part , a ‘partial’ base-bump, and decreasing part iterated division by 2. Before I discovered Goodstein sequences for myself, I was wondering at the time if there were other example of sequences that abstractly had ‘up-forces’ that fought with ‘down-forces’ and if the down forces also eventually won causing these sequences to eventually decrease because that is what we seem to observe with Collatz. Goodstein sequences can be an extreme example of this, if one has a fairly large power-tower then base-bumping would be an extreme leap up or ‘up force’, while the ‘down force’ for Goodstein sequences is humble and unassuming, simply take away 1. The reason why I say can is because if a number written in base-b is just b, then a base bump and subtraction by 1 leaves it unchanged , but now were are in base and thus would begin the decrease to 0 if we kept base-bumping(we don’t, the base-bumping is nullified and absent because we just have the constant ) and subtracting by : . I wondered specifically if there was a sequence with increasing part in the form of a base-bump and a decreasing part similar to division by 2, and if it would be known as fact that it would be eventually decreasing. Goodstein sequences are just that in terms of increasing base-bumping part, but as for decreasing part, I would have to weaken my criterion because division by 2 is stronger than subtraction by 1, but after all, division is a generalization of subtraction so we didn’t completely fall off track, and Goodstein’s Theorems proves that they are all eventually decreasing and converge to 0. Great! There was a catch though, Goodstein’s Theorem isn’t provable using the Peano axioms of arithmetic. At the time I was pondering the unprovability of Collatz, so I thought even better! Maybe that might lend itself to why Collatz is so hard to solve… 

When comparing Goodstein sequences and Collatz sequences, heuristically, since we are only doing a ‘partial’ base-bump, and always only from 2 to 3, for Collatz with Montreal iterates ( is unchanged) and then dividing by 2 at least once, the ‘up forces’ of Collatz are weaker than the ‘up forces’ of Goodstein which has a complete increasing base-bumping function, 2 to 3, 3 to 4, 4 to 5 and so on, and the ‘down forces’ of Collatz, which can vary between super-steps since they are iterated division by 2, are stronger than the ‘down forces’ of Goodstein which is the humble subtraction by 1. Using these heuristics, Collatz sequences ‘should’ converge to 1 before Goodstein sequences converge to 0. I think it is interesting to note that Goodstein sequences have a built-in stabilizer, i.e. once they reach 0 they are defined to be the constant function at 0 forever, Collatz sequences on the other hand have an in-built stabilizer that prevents them from decreasing further, namely that 1 cycles with itself. Interestingly enough, using Montreal iterates forces the Collatz sequences to be the constant function at 1 once they reach 1, since through the Montreal iterates. 

In a way Goodstein sequences have everything we wish we had for Collatz sequences. I recently did a talk at the CUMC, and I defined a stopping-time function in terms of the Montreal iterates called helper. I created the function using python code, and it ‘helps’ you find the stopping time of a number by having the computer do the heavy-lifting, hence the name helper. If you graph helper, it looks like chaos contained under some undefinable logarithmic function, here is an example of helper plotted for all odd positive integers less than : 

Goodstein sequences have a corresponding stopping-time function, the Goodstein function , and unlike the helper function there is a formula to calculate the stopping time(or length) of every Goodstein sequence. The Goodstein function is known to grow extremely rapidly, i.e. it takes Goodstein sequences a really long time to get to 0, for example while . It is also known how Goodstein sequences behave on their way to 0, they grow exponentially, and then become flat/constant functions for a period of time before making their decent linearly to 0 (they get to some number written in complete base- notation for ). Collatz sequences on the other hand are also called sequences of hailstone numbers, because the numbers in the sequences look like hailstones rising and falling in the clouds before eventually falling to the ground, and then bouncing on the ground forever. We don’t know what is going on with Collatz sequences while they appear to be on their way to 1. 

The most interesting thing I think Goodstein sequences have that Collatz sequences with Montreal iterates don’t is the lack of concern about the right ‘factorization’ (Goodstein sequences require making sure you are in complete base- notation at each step before performing the base bump and subtraction by 1, Collatz sequences with Montreal iterates require writing a number in the form   for and odd, and then knowing the 2-adic valuation of which when combined can be computationally expensive) at each step. Considering the example above (266), past 7, do we really know what the complete base-8 notation of the next number of the sequence? Sure we could always compute it, but as we continue to advance with the sequence, what about the complete base-9 notation at the next step, or the complete base-10 notation at the step after that, or the complete base-11 notation after that, or the complete base-12 notation where the situation is a little hairier because there is no constant anymore to cushion the calculation? The proof Goodstein’s Theorem bypasses all these local difficulties by creating a corresponding decreasing sequence of ordinals, where both sequences correspond at 0. I wont get into the details here. If you were to take note of every detail when computing Collatz sequences with Montreal iterates, it would quickly become overwhelming, especially if you were trying to find a chink in the armor to see why they are eventually decreasing, it is difficult enough trying to find out how many times you have to divide by 2, which makes it very difficult to guess what the next number is. Say I start with , then we know that , I know that is even, but unless I perform the calculations , only then would I know it is divisible by 2 once. (Sure, you could jot down for various values of and odd positive integers and try to find a pattern, but it is not so easy). 

That being said,

Especially given that Goodstein sequences take such a long time to get to 0, they should really give Collatz sequences more than enough time to converge to 1, if they do, and if they don’t then maybe insight into this question will perhaps illuminate the question of if there are divergent Collatz sequences, or cycles other than 1,4,2,1 (or 1,2,1 using T).

Goodstein sequences could be redefined to be the constant function at 1 forever afterwards once arriving at 1. Thus if we start with the same initial value, Goodstein sequences defined to be 1 forever instead of 0, and Collatz sequences with Montreal iterates, eventually describe the same sequence, the constant function at 1, if all Collatz sequence converge to 1. Goodstein sequences would act like a predictable cap over Collatz sequences (Collatz sequences always under Goodstein sequences, only converging when they are both constant functions, hopefully, but Goodstein sequences grow so wildly in the beginning that they should rapidly reach heights unattainable by Collatz and then linger there for a really long time giving Collatz enough time to settle), and allow us to bypass the randomness of Collatz sequences, much how the proof of Goodstein’s Theorem using ordinals and their properties to bypass the difficulties of Goodstein sequences themselves.