Here are three really fun little proofs of some of the strongest results in group theory, all of which use very similar methods (strong induction and the class equation) in subtly different ways. They require a little bit of background (only some of which I’ve provided), and you should not expect to grasp it with a quick read-through. I encourage you to read through slowly and carefully, making sure you understand each step of the proofs. I promise it will feel rewarding once you’re done!

Background

These proofs mostly rely on the Class Equation. I’ll spend a little bit of time showing where it comes from. (You can skip this section if you already know or don’t care where it comes from.)

Partition Equation: Suppose G acts on X. Then the orbits of this action partition X. That is, the orbits of any two elements either share all their elements or none of them, and every element in X is in some orbit. So |X| = ∑|orb(x)|, where the sum is taken over representatives from each orbit.

Orbit Stabilizer Theorem: For any x in X, |orb(x)|⋅|stab(x)| = |G|. Here stab(x) refers to the subset of G that fixes x (“stabilizes” it) under the group action. So stab(x) = {g in G : g•x = x}.

Stabilizers are Subgroups: The stabilizer of any x in X is a subgroup of G.

Now we look at the special case of G acting on itself by conjugation. I.e. we define g • x = gxg^-1. The orbit of any element x is its conjugacy class Cl(x), and stab(x) is x’s centralizer C(x). So the partition equation for the conjugacy action is |G| = ∑|Cl(x)|, where the sum is taken over representatives of conjugacy classes. And the Orbit Stabilizer Theorem becomes |Cl(x)|⋅|C(x)| = |G|.

Cl(x) = {gxg^-1 for all g ∈ G}
C(x) = {g in G such that gx = xg}

 You can easily show that for any central element in G (that is, for any element that commutes with every other element in G), its conjugacy class just contains itself. This means that |Z(G)| terms in this sum are equal to 1. So we can rewrite our equation, taking this into account. This gives us the Class Equation.

Class Equation: |G| = |Z(G)| + ∑|Cl(x)|, where the sum is taken over non-central representatives of conjugacy classes.

Some notes about this equation:

• Z(G) is a subgroup of G, so |Z(G)| ≥ 1.
• Since the terms in the sum are by definition sizes of conjugacy classes of non-central elements, none of them have size 1. That is, |Cl(x)| > 1 for every non-central x.
• All terms divide |G|. This follows for Z(G) by Lagrange’s theorem (because it’s a subgroup). And it must be true for each |Cl(x)| by the Orbit-Stabilizer Theorem.

That’s all we need! We’re ready to prove Cauchy’s Theorem and Sylow’s First Theorem!

Proof of Cauchy’s Theorem

Cauchy’s theorem: G has a subgroup of size p for every prime p that divides |G|.

Part 1: First we show that Cauchy’s theorem holds for all abelian groups. This can be proven by strong induction. The base case is |G| = p, which trivially has a subgroup of size p (itself). Now we take a look at any larger group G such that p divides |G|. The strong inductive hypothesis is that Cauchy’s theorem holds for all abelian groups of size less than |G|.

Now, take any non-identity element g in G. Let H = <g>.

• Case 1: Suppose p divides |H|. Then g^|H|/p is an element of order p.
• Case 2: Suppose p doesn’t divide |H|. Then p must divide |G/H| (since |G| = |H|⋅|G/H|). Since G is an abelian group, G/H is also an abelian group. And since we chose g to be non-identity, |H| > 1, so |G/H| < |G|. Thus by the inductive hypothesis, G/H contains an element xH of order p. But this implies that |x| is a multiple of p. After all, xH is order p, and (xH)^|x| = x^|x|H = eH = H. So x^|x|/p is an element of order p. Done!

Now that we’ve proven Cauchy’s theorem for all abelian groups, we go on to prove it for all groups.

Part 2: We use strong induction again. The base case is |G| = p, which is trivial. Now, suppose G is a group such that |G| is divisible by prime p. The strong induction hypothesis is that Cauchy’s theorem holds for all groups of size less than |G|.

Let’s examine the Class Equation: |G| = |Z(G)| + ∑|Cl(x)|.

• Case 1: Suppose that for some x, |Cl(x)| is not divisible by p. Then for this x, |C(x)| must be divisible by p (since |Cl(x)|⋅|C(x)| = |G|). Since centralizers are subgroups, C(x) is a subgroup with size divisible by p. Furthermore, since |Cl(x)| > 1, |C(x)| < |G|. So by the induction hypothesis, C(x) has a subgroup of size p.
• Case 2: For all x, |Cl(x)| is divisible by p. But so is |G|. So |Z(G)| must be divisible by p as well. But Z(G) is abelian, so it must have a subgroup of size p (by Part 1).

And we’re done!!

With this result in hand, we can go even deeper and prove Sylow’s First Theorem. This one is slightly more involved, so take a breather if you need one…

… And now let’s dive into it!

Proof of Sylow’s First Theorem

Here’s Sylow’s First Theorem: For every prime power in the factorization of |G|, there is a subgroup of that size. In other words, if G is a finite group such that pⁿ divides |G| for some prime p, then G has a subgroup of order pⁿ.

Again, we proceed by strong induction. Our base case is |G| = p, which is trivial. Now we look at a larger group G, and assume that the theorem is true for all groups of size less than |G|.

Class Equation: |G| = |Z(G)| + ∑|Cl(x)|.

• Case 1: Suppose at least one of the terms in the sum ∑|Cl(x)| isn’t divisible by p. Then for this x, |C(x)| must be divisible by pⁿ (since |Cl(x)|⋅|C(x)| = |G|). Since centralizers are subgroups, we have a subgroup with size divisible by pⁿ. Furthermore, since each |Cl(x)| > 1, |C(x)| < |G|. So by the induction hypothesis, C(x) has a subgroup of size pⁿ.
• Case 2: Each |Cl(x)| is divisible by p, as is |G|. So |Z(G)| must be divisible by p. So by Cauchy, Z(G) has an element of order p, say g. Define N = <g>. N is normal, since it’s in the center. So G/N is a group. |G/N| = |G|/|N| = |G|/p, so by induction, G/N has a subgroup H of size p^n-1. Now, consider the canonical homomorphism φ: G → G/N defined by φ(g) = gN. It turns out that φ^-1(H), the inverse image of H, is a subgroup of G with size pⁿ, just what we were looking for!
  • Why is |φ^-1(H)| = pⁿ? Well, each element of G/N is a coset, and all cosets have the same size, namely |N|. This means that |N| elements are mapped to any given coset by φ. H is a subset of G/N, so it contains |H| cosets, each of which is mapped to by |N| elements. Since cosets are disjoint, there is no overlap. So φ^-1(H) = |N|⋅|H| = p⋅p^n-1 = pⁿ.

(Proofs can be found in Judson’s Abstract Algebra)

Order 1: 1 Group

	Abelian	Cyclic	Simple
ℤ1 = S1 = A2	Y	Y	Y

Order 2: 1 Group

	Abelian	Cyclic	Simple
ℤ2 = S2	Y	Y	Y

Order 3: 1 Group

	Abelian	Cyclic	Simple
ℤ3 = A3	Y	Y	Y

Order 4: 2 Groups

	Abelian	Cyclic	Simple
ℤ4	Y	Y
ℤ22 = K4	Y

Order 5: 1 Group

	Abelian	Cyclic	Simple
ℤ5	Y	Y	Y

Order 6: 2 Groups

	Abelian	Cyclic	Simple
ℤ6 = ℤ3 × ℤ2	Y	Y
Dih3 = S3

Order 7: 1 Group

	Abelian	Cyclic	Simple
ℤ7	Y	Y	Y

Order 8: 5 Groups

	Abelian	Cyclic	Simple
ℤ8	Y	Y
ℤ4 × ℤ2	Y
ℤ23	Y
Dih4
Dic2 = Q8

Order 9: 2 Groups

	Abelian	Cyclic	Simple
ℤ9	Y	Y
ℤ3 × ℤ3	Y

Order 10: 2 Groups

	Abelian	Cyclic	Simple
ℤ10 = ℤ5 × ℤ2	Y	Y
Dih5

Order 11: 1 Group

	Abelian	Cyclic	Simple
ℤ11	Y	Y	Y

Order 12: 5 Groups

	Abelian	Cyclic	Simple
ℤ12 = ℤ4 × ℤ3	Y	Y
ℤ6 × ℤ2 = ℤ3 × ℤ22	Y
Dic3
A4
Dih6 = Dih3 × ℤ2

Order 13: 1 Group

	Abelian	Cyclic	Simple
ℤ13	Y	Y	Y

Order 14: 2 Groups

	Abelian	Cyclic	Simple
ℤ14 = ℤ7 × ℤ2	Y	Y
Dih7

Order 15: 1 Group

	Abelian	Cyclic	Simple
ℤ15 = ℤ5 × ℤ3	Y	Y

Order 16: 14 Groups

	Abelian	Cyclic	Simple
ℤ16	Y	Y
ℤ8 × ℤ2	Y
ℤ42	Y
ℤ4 × ℤ22	Y
ℤ24	Y
Dih8
Dic4
Dih4 × ℤ2
Dic2 × ℤ2
K4 ⋊ ℤ4
ℤ4 ⋊ ℤ4
ℤ8 ⋊ ℤ2
(ℤ4 × ℤ2) ⋊ ℤ2
QD16

Order 17: 1 Group

	Abelian	Cyclic	Simple
ℤ17	Y	Y	Y

Order 18: 5 Groups

	Abelian	Cyclic	Simple
ℤ18 = ℤ9 × ℤ2	Y	Y
ℤ6 × ℤ3 = ℤ32 × ℤ2	Y
Dih9
S3 × ℤ3
(ℤ3 × ℤ3) ⋊ ℤ2

Order 19: 1 Group

	Abelian	Cyclic	Simple
ℤ19	Y	Y	Y

Order 20: 5 Groups

	Abelian	Cyclic	Simple
ℤ20 = ℤ5 × ℤ4	Y	Y
ℤ10 × ℤ2 = ℤ5 × ℤ3 × ℤ2	Y
Dih10 = Dih5 × ℤ2
Dic5
ℤ5 ⋊ ℤ4

Order 21: 2 Groups

	Abelian	Cyclic	Simple
ℤ20 = ℤ7 × ℤ3	Y	Y
ℤ7 ⋊ ℤ3

Order 22: 2 Groups

	Abelian	Cyclic	Simple
ℤ22 = ℤ11 × ℤ2	Y	Y
Dih11

Order 23: 1 Group

	Abelian	Cyclic	Simple
ℤ23	Y	Y	Y

Order 24: 14 Groups

	Abelian	Cyclic	Simple
ℤ24 = ℤ8 × ℤ3	Y	Y
ℤ12 × ℤ2 = ℤ6 × ℤ4	Y
ℤ6 × ℤ22 = ℤ3 × ℤ23	Y
Dih12
Dih6 × ℤ2
Dih4 × ℤ3
S4
S3 × ℤ4
A4 × ℤ2
Dic6
Dic3 × ℤ2
Dic2 × ℤ3
ℤ3 ⋊ ℤ8
ℤ3 ⋊ Dih4
SL(2,3) = 2T

Order 25: 2 Groups

	Abelian	Cyclic	Simple
ℤ25	Y	Y
ℤ52	Y

Order 26: 2 Groups

	Abelian	Cyclic	Simple
ℤ26 = ℤ13 × ℤ2	Y	Y
Dih13

Order 27: 5 Groups

	Abelian	Cyclic	Simple
ℤ27	Y	Y
ℤ9 × ℤ3	Y
ℤ33	Y
ℤ32 ⋊ ℤ3
ℤ9 ⋊ ℤ3

Order 28: 3 Groups

	Abelian	Cyclic	Simple
ℤ28 = ℤ7 × ℤ4	Y	Y
ℤ14 × ℤ2 = ℤ7 × ℤ22	Y
Dih14
Z7 ⋊ Z4

Order 29: 1 Group

	Abelian	Cyclic	Simple
ℤ29	Y	Y	Y

Order 30: 4 Groups

	Abelian	Cyclic	Simple
ℤ30 = ℤ15 × ℤ2 = ℤ10 × ℤ3 = ℤ6 × ℤ5	Y	Y
Dih15
Dih5 × ℤ3
S3 × ℤ5

Order 31: 1 Group

(Order p)

	Abelian	Cyclic	Simple
ℤ31	Y	Y	Y

Order 32: 51 Groups

I’m not going to list these all here, but seven of them are abelian.

(All cycle graphs stolen from Wikipedia)

Notable Groups

A₅: Smallest simple group that isn’t cyclic. Order 60.

ℤ₂²: Smallest non-cyclic group.

Dih₃: Smallest non-abelian group.

A₄: First example where n divides |G| but there is no element of order n. (n = 6)

Z₇ ⋊ Z₃: Smallest non-abelian group of odd size.

Dih₃: Smallest group with a normal subgroup that isn’t isomorphic to one of its subgroups.

General Patterns

1 group of order p
2 groups of order p²
5 groups of order p³
15 groups of order p⁴, for p > 2
2 groups of order pq for q-1 divisible by p
1 group of order pq for q-1 not divisible by p

Groups of Size 2ⁿ

Most finite groups are size 2ⁿ. For example, over 99% of all groups of size 2000 or less are size 1024.

How to Decompose a Group Into a Direct Product

If H and K are subgroups of G with trivial intersection, HK = G, and all elements of H commute with all elements of K, then G is isomorphic to H × K.

Kernel of Homomorphism Is Normal Subgroup

If φ: G → G’ is a homomorphism, then ker(φ) = φ^-1(e_G’) is a normal subgroup of G.

A homomorphism is a function from one group G to another group G’ that maintains the group structure: φ(ab) = φ(a)•φ(b). It’s similar to an isomorphism, but is not required to be one-to-one or onto (so multiple elements of G can be mapped to the same element of G’). The kernel of φ is the set of elements in G that are sent by φ to the identity in G’.

Cayley’s Theorem

Every group of size n is a subgroup of S_n, the the set of all permutations of n items. In addition, S_n contains S_m for all m < n.

This means that if you want to all groups of size 2000 or less, you just need to look at the structure of S₂₀₀₀ (which has 2000! elements). In some sense, then, the study of finite groups is just the study of the structure of large permutation groups.

Group Presentation Undecidability

A group presentation looks like ⟨S|R⟩, where S is a set of generators for the group, and R is a set of relations among the generators.

For example: ⟨a | aⁿ = e⟩ is the cyclic group of size n (Z_n). Another example: ⟨r,f | rⁿ = e, f² = e, fr = r^n-1f⟩ is the dihedral group of size 2n (the set of symmetries of a regular n-gon).

A finite presentation for a group is just a presentation where S and R are both finite. All finite groups have a finite presentation (easy proof: let S contain all the members of the group, and R be its Cayley table), as do some infinite groups (for example, ⟨a | ∅⟩, the group generated by a with no constraints).

Now, you can ask whether there exists an algorithm that takes as input a finite presentation, and figures out whether the group it represents has a certain property (like, is it the trivial group? Is it a finite group? Is it abelian? Is it simple? And so on.) It turns out that for each of these, the answer is no! In addition, the question of if two arbitrary words (e.g. for Dih_n, frfrfr and rfrrf) represent the same element is undecidable. So is the question of if two finite presentations represent isomorphic groups.

In general, for pretty much any non-trivial property of a group (a property that isn’t shared by all groups), there is no general algorithm that decides whether a finite presentation has that property!

If you’ve looked into abstract algebra at all, you might be intimidated by the variety of strange-sounding names; things like like monoids, magmas, semigroups, loops, fields, and so on. What are all these names about?

In general, the procedure is as follows: Choose some number of sets, equipped with some number of binary operations. Then endow these operations with some general structural constraints (things like commutativity, associativity, and so on). The result is some abstract mathematical object that might be very interesting or just medium interesting, depending on the constraints that you’ve applied. The different subfields within abstract algebra are just the studies of what you get when you apply particular <sets, operations, constraints> triples! Let’s take a little tour of these subfields.

We start with the most basic. The simplest choice you could make for the sets and operations would be one set S with one binary operation • on that set, denoted as (S, •). The most primitive constraint that you can apply to this operation is closure, which is the condition that the output of the binary operation must always be an element of S. Common constraints added on top of this include:

• Associativity (A): For all a, b, and c in S, (a • b) • c = a • (b • c)
• Identity (E): there is an element e in S such that for all a in S, e • a = a
• Invertibility (V): for all a in S, there is an element a’ in S such that a’ • a = e
• Commutativity (C): for all a and b in S, a • b = b • a

Now we can consider the different types of mathematical objects that arise from different combinations of these constraints!

AEVC = Abelian group
AEV = Group
AEC = Commutative Monoid
AE = Monoid
A = Semigroup
Only closure = Magma

These are just a few examples, and this is all for the case of a single set with a single operation. Two of the biggest objects of study in abstract algebra are rings and fields, both of which involve one set and two binary operations, usually denoted as + and •. The constraints for rings are as follows:

(R, +, •)
(R,+) is an abelian group (AEVC)
(R,•) is a monoid (AE)
Distributivity (of multiplication with respect to addition): a • (b + c) = a•b + a•c

(Rings also have a slightly more bare-bones cousin called rngs, which are basically rings without a multiplicative identity.)

Fields involve even more structure than rings:

(F, +, •)
(F, +) is an abelian group (AEVC) (call its identity 0)
(F \ {0}, •) is an abelian group (AEVC)
Distributivity (of multiplication w.r.t. addition)

There are so many other mathematical objects besides these, each of which has its own field of study. When you survey these fields at a high level of abstraction, an interesting pattern becomes apparent.

Observation 1: More structured objects are simpler and easier to fully characterize.

Think about vector spaces. A vector space has two sets (call them F and V) and four binary operations (two on F x F, one on V x V, and one on F x V). F forms a field with its two operations, and V forms an abelian group with its operation. And there are a few more constraints on the final operation, ensuring that it is well-behaved in a bunch of ways. Overall, vector spaces are highly constrained in many ways. And as such, linear algebra (the study of vector spaces) is a completely solved field. There are pretty much no interesting new discoveries in linear algebra, because there are only a few interesting things you can say about such well-structured objects, and all such things have been quickly discovered. (A quick caveat: linear algebra finds all sorts of applications in more complicated domains of math, many of which have unsolved problems. I’m not considering these problems as part of understanding vector spaces. There are also more applied open questions about, say, how to most efficiently calculate the product of two n x n matrices, which I again do not consider to reflect a lack of understanding of the structure of vector spaces.) And by the way, this is not a knock on linear algebra! I love vector spaces. It’s just that I think there are even more interesting objects out there!

Take another example, fields. Fields are less structured than vectors in a bunch of ways, but all the same, we can fully characterize all finite fields with a few simple equations. The work required to do this is fairly trivial; you can prove the classification theorems in a couple of minutes with barely any background required. For instance, you can quickly prove that all finite fields have sizes that are powers of primes. And furthermore, all finite fields of the same size are isomorphic! So if you were to write out a function f(n) for the number of non-isomorphic fields of size n, it would just be 1 for every prime power and 0 for everything else.

Similarly, compare abelian groups to groups. Abelian groups are strictly more structured objects that groups, being that they are just groups that satisfy the additional constraint of commutativity. They are also significantly less structured than fields, being that they only have to satisfy the constraints for one operation and thus don’t have to worry about distributivity between two operations. It turns out that just like with fields, you can actually classify all finite abelian groups, and write out a (relatively simple) equation for the number of finite abelian groups of size n. This number is the product of the partition numbers of the exponents of each prime in the prime factorization of n. Proving this takes a lot more work than the classification of fields, and the function is clearly much more complicated than the corresponding function for fields. But it’s enormously simpler than classifying all finite groups!

As far as I’m aware, there is no known formula that takes in a number N and returns the number of non-isomorphic groups of size N. Although there are lots of little facts known about the values of this function for particular values of N (for example, for any prime p, f(p) = 1 and f(p^2) = 2), classification in general is enormously difficult. Here are the numbers of finite groups of order N, for small values of N starting at 1.

[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51, 1, 2, 1, 14, 1, 2, 2, 14, 1, 6, 1, 4, 2, 2, 1, 52, 2, 5, 1, 5, 1, 15, 2, 13, 2, 2, 1, 13, 1, 2, 4, 267]

(Fun exercise, try seeing how many of these you can prove for yourself!)

Here’s a plot of this sequence, to give you a sense of how complicated and strange it is:

Furthermore, there are bizarre things like the sporadic groups with their stubborn resistance to categorization, and the king of the sporadic groups, the enormous Monster group. All this structure immediately vanishes as soon as you introduce commutativity, leaving you with a much less interesting object!

Observation 2: Highly unstructured objects also become easy to characterize. Think about magmas (M, •), whose only constraint is closure. How many magmas are there of size N? Well, for any two elements in M, there are N choices for the value of their product. So it’s just the number of ways of placing elements from M in N^2 spots, i.e. N^(N^2). Simple! The lack of structure here actually makes classification of the finite magmas extremely quick and easy.

Another example: Take a slightly more structured object, magmas with identity. This basically just fills in 2N – 1 of our slots (for all m, we get that e•m = m and m•e = m), so that our new classification is just N^(N^2 – 2N + 1). What if we add commutativity? Well, that just cuts our degrees of freedom roughly in half, since every time you choose the value of a•b, you have also chosen b•a! (It’s not exactly half, because of the elements that look like a•a).

But if you now add associativity, you end up with a commutative monoid. These objects are vastly more complicated and difficult to characterize. In general, associativity is probably the most interesting single property you can give to an operation (at least, of the commonly used properties we’ve discussed). By constraining an operation to be associative, you automatically endow your mathematical object with a great degree of interesting structure.

—

The conclusion I’ve drawn from these observations is that there is a sweet spot of subjective “interestingness” that exists between the highly structured and the highly unstructured. I think that objects like groups and rings occupy this sweet spot, and as you go further in either direction of the structure spectrum the objects you find become less interesting and harder to find surprising results about.

In the last post, I linked to a video of me explaining and proving Lagrange’s theorem. This theorem does a lot to empower us to get a deeper understanding of the structure of groups (for instance, allowing us to prove that there is only one single group of size p, where p is any prime number).

This time, we’ll be going a level deeper and proving a much much more powerful theorem: Cauchy’s theorem! While Lagrange’s theorem gives us a necessary condition for the existence of subgroups (that the subgroup’s size divides the group’s size), Cauchy’s theorem gives us a sufficient condition (that the subgroup’s size is a prime factor of the group’s size)!

This is a really powerful tool to add to our toolkit for analyzing groups. It also really nicely complements Lagrange’s theorem, in that Lagrange’s theorem is most powerful when applied to group sizes that are prime or have few prime factors, while Cauchy’s theorem is most powerful when applied to group sizes that are highly composite.

Anyway, here are the links to the two videos in which I go in depth into all of this!

Even though these two videos together are about 35 minutes, the proof itself is actually quite short! Most of the work done in the videos is just building up some powerful concepts (actions, orbits, stabilizers). These concepts allow us to prove the theorem in just a few lines! (In fact, if you look closely at the proof, you might notice a a way to get an even stronger result with just a few more lines!)

Voltaire said to not let the perfect be the enemy of the good. In that spirit, I’ve decided to post a few (highly imperfect) video lectures I recently on group theory. There’s a lot of things I would do to go back and improve these lectures, but I hope that the content makes up for any flaws!

There will be a third one coming soon, and will be a working-through of an example that shows the power of Lagrange’s theorem. This format is a bit of an experiment for me, and I’ll keep working to make it better. I hope you enjoy!

For some reason, I have a fascination with all the different sequences of numbers that arise out of thinking about the Collatz conjecture. In this post, we’ll look at a few more of these.

The Collatz chain for a number N is the sequence of numbers that arise from repeatedly iterating the function

until you get to 1. The Collatz conjecture is the statement that this sequence always terminates, no matter what n you start at.

In other words, f(N) is the function that tells you what N becomes after a single iteration. Let’s look at the inverse of this: what numbers become N after a single iteration?

One such number is 2N: 2N is always even, so after one step it falls down to n. Another possibility is m = (N-1)/3. Why? Well, if m is an odd number, then it will become 3m+1 = 3 (N-1)/3 + 1 = N – 1 + 1 = N. So for each N, we get either one or two new values.

The Collatz tree is what we get if we start at 1 and repeatedly iterate the inverse function. After n iterations, we get to the set of all numbers that take at most n steps to get to 1. Here’s what it looks like!

I’ve never actually seen it plotted this way, and I think it shows something potentially important. Look at the order in the image! Why do we get this grid of apparently identical rhombuses? I’d love an explanation for this.

I also like the idea of “surfing” the jagged lower end of this graph, staying as small as possible while iterating f. In general, the lower end of the graph is the sequence of smallest numbers that take N steps to get to 1.

Here are the first thirty numbers in this sequence:

1, 2, 4, 8, 16, 5, 10, 3, 6, 12, 24, 48, 17, 34, 11, 22, 7, 14, 28, 9, 18, 36, 72, 25, 49, 98, 33, 65, 130, 43

Plotted, this sequence looks like:

The first twelve of these numbers themselves form a Collatz chain. We leave this particular chain on the thirteenth step, at which point we enter a new chain containing 17. We stay in this new chain until seven steps later, at which point we enter a new chain containing 25. But now we only stay in this new chain for one step before departing for a new one! This is another sequence of numbers that fascinate me: the chain lengths at which our minimum values switch to entirely new chains. Here are the values for up to 100 steps:

12, 23, 24, 26, 27, 34, 36, 37, 38, 39, 44, 45, 46, 48, 49, 50, 51, 52, 53, 54, 55, 56, 60, 61, 63, 64, 65, 72, 73, 74, 75, 76, 97, 98

The differences between these values are plotted here:

Whenever this plot spikes, this points to an existence of a Collatz chain that surfs the bottom of the Collatz tree for some time before jumping up to a higher value!