W

 Will Nicholes

Collatz tree / 3x+1 conjecture

The Collatz conjecture (also known as the “3x + 1” or “3n + 1” problem) involves a simple repeated formula, but yields some interesting sequences.

In short, begin with a positive integer; if it’s even, divide it by two; if it’s odd, multiply it by three and add one. Repeat this sequence until the result is 1. Starting with 28, for example, yields the sequence 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, and finally 1. If you continue past 1, the sequence cycles indefinitely with 4, 2, 1, 4, 2, 1...

It’s an open question whether all positive integers that are run through this process eventually wind up at 1; while it’s possible a sequence could instead increase forever, or enter a loop, none have so far been found.

“Reversing” the process yields a Collatz tree. Given a result 1, the two ways that result could be seen were if n/2 is 1 or if n3+1 is 1. Thus, the two possible “precursors” to 1 would be 2 or 0. While 2 is a valid precursor, 0 is not: since it’s even, it would not be run through the formula n3+1; it would instead be divided by two.

We can continue along this path to see what would result in a 2; since the normal operation applied is n/2 and 3n+1, we can perform the inverse operations 2n and (n-1)/3 to see what 2’s precursors are. The operations yield 4 (which is valid) and 1/3 (which is not, since it is not an integer.)

Iterating through the valid results gives us a tree:

Collatz Tree / 3x+1 problem

This shows both the valid and invalid nodes through the first 8 iterations. You can find a more complete version (without invalid nodes) here.

Some related integer sequences:

  • Traversing the tree from bottom to top gives integer sequence A088975: 1, 2, 4, 8, 16, 5, 32, 10, 64, 3, 20, 21...
  • Traversing the right-most node of each level from top to bottom gives the powers of 2 (1, 2, 4, 8, 16, 32...), while traversing the left-most node of each level gives integer sequence A101229: 1, 2, 4, 8, 16, 5, 10, 3, 6, 12, 24, 48...
    Note that the inverse 3x+1 formula (x-1)/3 will never generate an integer for a multiple of three, so starting with “6”, each number in this sequence will always be twice the previous number.
  • The number of nodes in each level is integer sequence A005186: 1, 1, 1, 1, 1, 2, 2, 4, 4, 6, 6, 8, 10, 14, 18, 24, 29...

 

Validate this page