Will Nicholes 
Collatz tree / 3x+1 conjectureThe 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 (n1)/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: 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:



