Index

The following is a graph of the solution space to the Collatz problem. Starting at any point on the graph, going downwards, we eventually hit 4, 2, 1.

Properties of the Solution Space Graph

Vertices

Define a vertex in this graph to be any node with two children.

Any node in this tree has at least one child. If a node is a single sibling or a right sibling it has the property that it is 2 times its parent. A left node has the property that its (parent’s value – 1) / is divisible by 3. The left node’s value is then (parent’s value – 1) / 3.

Accordingly, to be a vertex (a parent of a left sibling who isn’t an only child), you need to have the property that one minus your value is divisible by 3. Also, a vertex must be even.

Let’s examine some possible vertices by looking at all 3n+1 numbers for all n = 1 and onwards (natural numbers).

1 -> 4

~~2 -> 7~~

3 -> 10

~~4 -> 13~~

5 -> 16

and so on…

The strikethrough indicates that we discard any vertices that are odd (recall vertices must be even).

All Vertices are of the form 6k+4

We note that as a result of the above, all vertices are of the form 6k+4, for some natural k>=0.

All Nodes are either a left sibling, or 2^p * some left sibling

Examining nodes in the tree, we note that all nodes are either a left sibling, or 2^p * some left sibling for some natural p >=1.

What is the formula for all left siblings?

We know that any vertex is of the form 6k+4 for some natural k >=0. Then the left sibling is, generally, of the form:

( (6k+4) – 1 ) / 3

ßà

( 6k + 3 ) / 3

ßà

( 2k + 1 )

And now the formula for all left siblings and their desecendents

For the left siblings and all their descendents, we need only add (multiply by) the term 2^p

Thus in general, all nodes in the tree are of the form:

(2k + 1) * 2^pfor some natural k,p >= 0

The big question: for any natural number, does the Collatz sequence end in 4, 2, 1?

Perhaps this isn’t as big a question as was originally thought. Really it comes down to two things:

1) Are all natural numbers represented by the form (2k+1) * 2^p for some natural k,p >=0? If not, we introduce the possibility of nodes which aren’t on the graph for which we get runaway recursion (no possible route to 4,2,1).

2) Are they uniquely represented? Ie, is there more than one way of getting any given natural number? If so, we introduce the possibility of a cycle in the graph which would prevent us from ever completing.

An examination of (2k + 1) * 2^p

Here is a empirical examination of (2k + 1) * 2^p

k / p	p=0 **	p=1	p=2	p=3
k=0	1,1 ***	2	4	8
k=1	3	6	12	24
k=2	5	10	20	40
k=3	7	14	28	56
k=4	9	18	36	72
k=5	11	22	44	88
k=6	13	26	52	104
k=7	15	30	60	120

** Note: the p=0 column represents the set of left siblings.

*** 1 is mentioned twice because there is a duality about it. When I said that numbers must be uniquely represented, I should have been more precise. They need to be uniquely represented by pairs of multiples. For example, 18 is 9*2 (k=4,p=1) but it isn’t 2*9 in our regime because there is no k such that 2k+1 = 2. So for 18, there is only one way of multiplying two numbers (in our pairing) to get it. However in the case of 1, there is an ambiguity as to whether it’s 1 * 1’ or if it’s 1’ * 1. Another way of expressing this is to ask, what is the intersection of the set of vertices with the set of lone siblings. That’s 3n+1 = n*2^p where p>1 (can’t be 0, that’s a left child). The equation has only one solution and that is n=1. Either way, it’s mathematics’ way of telling us that there is an ambiguity about 1 as to whether it’s a left sibling or a lone sibling.

A rudimentary examination of the table suggests that 1) all natural numbers are present and 2) all natural numbers are uniquely presented. Find numbers 1 to 15 in the table to get a feel for the problem.

I shall have to examine my undergraduate notes to see if I have a proof for (2k + 1) * 2^p representing the entire natural number domain.

However, just by inspection, any natural number, if repeatedly divided by two will eventually land you on an odd number, of which there are an infinite supply, so this should be true. Also, this process of infinite division by two will land you one unique odd number. That is, they are uniquely represented in such a scheme (hence no possibility of loops in the graph).

If no such proof exists, and we prove the Collatz conjecture by other means, this will also be a proof that all natural numbers are represented by (2k + 1) * 2^p. However, if such a proof does exist (likely the previous paragraph will suffice), then it would seem that the Collatz conjecture is solved.

Why the 3n+c extensions fail

There are ‘extensions’ to the Collatz function. An extension occurs when you replace the ‘3n+1’ in the function with 3n+c, where c is a natural number greater than 1. The extensions fail for one of two reasons, 1) run away recursion (up down, but trending upwards forever) or 2) infinite loops or cycles in the graph.

Run away recursion occurs when you break the bijection. (A bijection is what we have in the table above, that is two unique values (p,k) map uniquely to one natural number.) That is, you create a scenario where not all natural numbers are represented in the equivalent of the table above. These are nodes that aren’t attached to the graph.

Infinite cycles or loops in the graph occur when there are two ways of representing a number in the attempted bijection. Examine the table above. Imagine the p=0 column had 2, 4, 6 , 8, … 16. Then 16 would be represented twice (once in the p=0 column and again in the k=0, or 2 leading row) in the attempted bijection and you would get a cycle involving the number 16.

Questions? Comments?

martin_winer@hotmail.com