Workshop Recreational Mathematics |
|
The Collatz-Problem
|
|
Abstract: Some views, textbased and a fractal graphic view, are shown here. Some of the concepts used here are also basic for my general studies and describtions of the collatz-problem. external links: see bottom of text |
Some text-based trees
The most intuitive tree
|
Page -1- |
|
For Collatz-freaks the transformation-tree is known for instance in a text-based-format, as it can easily be produced by a spreadsheet like Excel or in some semi-graphic-format. A common text view is like this, the most obvious one. The arrows show one step of the original Collatz-transformation, ... |
|
1<--2<--4<--8<---16<---32<---64<--128<---256<---512<---1024<---2048 ^ ^ ^ ^ ^ ! ! ! ! 341<---642 ! ! ! ! ! ! ! 85<---170<----340<---680 ! ! ! ! ! 21<---42<----84<---168<--- 336<---672 ! ! ! 5<---10<---20<---40<----80<---160<--- 320<---640 ! 1<--2<----4<----8<---16<---32<----64<---128<--- 256<---512 |
|
...where also the other entries, like 10 for instance, should get an own arrow coming from 3 etc. The recursivity of this tree-structure (not of the tree values themselves, that's the problem of the nonexistence of a loop) and the difficulty to give it an appropriate graphical representation, which also focuses the most important numerical properties of each entry, might be the reason for so many graphic displays of the numbers of the Collatz tree. |
A compressed and "constructive" (=reversal orientated) tree
|
Page -2- |
|
The following is the transformation-tree, with the arrows in *opposite* direction, since I made this tree from the view of creating the tree, starting from 1 instead of starting from a number and iterating the 3x+1 transformation down to 1. Note also, that I suppressed the even numbers, since they are only powers of 2 multiplied with the odd values. So the main row is just the first diagonal of the "most-intuitive-tree", which means it contains all numbers declining to 1 by one 3x+1 transformation, followed by the complete set of x/2 transformation until an odd number results.
|
|
In this reversed view as a *generating* process, we can call 1 the root, and the row of all numbers which decline to 1 by one complete transformation, their childs (which means in the reversed view, they can be generated from 1 by one constructive operation with a free parameter A ) : x1 = (x0*2A-1)/3 The root 1 is the left-most column in the middle of the rows. The arrows are to be read as a constructing operation, and the row, where the arrow points to is the list of all numbers, which can be reached by one constructive operation with the free parameter A, the row of childs. This can be represented by a notation like the following x1 = C(x0;A) := x1 =(x0*2A-1)/3 So all numbers like 1,5,21,85... can be generated as childs from the parent 1 (you find the row about in the middle of the next text-graph). Then all numbers 3,13,53,213,... can be generated as childs from the parent 5 by one constructive transformation and so on. x1 = C(x0;A) x2 = C(x1;B) = C( C(x0;A) ; B) = C(x0;A,B) Example 3 = C(5;2) 5 = C(1;4) 3 = C(1;4,2) The deepness of the tree is obviously infinite, and the collatz conjecture implies, that it covers all odd numbers, so that all odd numbers can be represented by a finite expression of odd-number = C(1;A,B,C,D,...,Z) where the indexes A,B,C are natural numbers>0 (and are further restricted to keep the intermediate occuring childs integer) |
|
Page -3- |
|
The following graphs illustrate the above remarks in more detail, with some properties highligted by coloring. Green numbers are congruent 1 (modulo 3) and the head of their child-lists is *smaller* than their values. Red numbers are congruent 2 (modulo 3) and the head of their child-lists is *greater* than their values. Grey numbers are congruent 0 (modulo 3) and they don't have childs Orange cells are congruent to 1 (mod 4), yellow cells are congruent to 3 (mod 4): the imbalance between the occurences of each of these types looks like a paradoxon, since the Collatz-conjecture includes *all* odd numbers; and it might look here, as if many more 4x+1-numbers are involved than 4x+3-numbers... |
|
|
|
Note, that the progression in a row is 4x+1; the difference between two entries is always 3x+1, since (4x+1)-x = 3x+1. The progression from one head of child-row to the next head of child-row (3,227,...) as childs of (5,341,...) has progression 64x+35, or 64x+49 like the sequence (1,113,...) as childs of (1,85,...) |
|
Page -4- |
|
It may be of interest to see one of the most simple properties of this desert of numbers. This will be uncovered, if we look at them in base4 |
|
|
|
Only a small part is shown, with the row of 3 in the center. Immediately the most simple property of all numbers of a row can be seen: its just added a repunit to a certain head; the sequence goes 3,31,311,3111, and so on. This gives reason for the next step of compression (after the omitting of the even numbers), but this will not be shown here. More interesting is the sequence of child-heads of a sequence. For instance 3. To the bottom the childs starts with 203,203203,203203203,... and there is no need to do any computations at all to find the next entries. The childs to the top are 101,101301,101301301,.... and again we need no computation to guess the progression. Now one could start to analyze, why from 3 their top-childs start with 101 and the bottom childs with 203. From 23 the bottom-childs are 13,13203,13203203,... and the top-childs are 3301,3301301,... |
|
One can try to make more compressions on this basis. I assume, this is related to that what mensanator in sci.math did with his representation in binary ad identification from patterns like pulsars and others. I didn't proceed from here with these graphics, but tried to find any analytical access to the properties of this tree and the -by the collatz-conjecture- implied "greedyness" of this constructive operations in the sense of "creates all od numbers". |
A more graphic-oriented tree
The bottle-brush tree
|
Page -5- |
|
|
In the follwing I present my favorite type of graphic-representation of the collatz-tree, which combines the most important properties of the numbers and an imagination for the infinite recursion of the structure including the non-periodicity, which is measured by the modulus by 3. The middle of a tree is the parent, and the whiskers are the row of its childs. So the main bottle-brush has parent 1 (the root) and reading the whiskers from right in counter-clockwise direction, they have the numbers 1,5,21,... Also they are colored in green (x==2 (modulo 3)), red (x==1 (mod 3)) and grey (x=0 (mod 3)). The grey whiskers have no childs. The imagination of a bottle-brush is suggested by a third dimension, a z-axis with ascending powers of 2 (multiplied by the parent) so it could be imagined the the z-axis of the main brush has the values 1,2,4,8,16,... and the 5-whisker stems from the 4'th level of z. Now the green and the red whiskers have childs; the whisker 5 for instance the sequence 3,13,53, which makes 5 as a parent of a next brush, having the whiskers 3,13,53,... |
|
|
|
|
|
Also we can see, that the progression of the red whiskers from 1,85,5461,... is x1 = 64*x0+21, the same with the green and the grey whiskers. Here we see the relation to the 64-base-system. The imagination can be improved, if the whiskers are sorted by their modulo group. |
|
|
In this graph one recognizes the non-periodicity of the recursion: the sequence of green-red-grey whiskers of a parent is opposite for green and red parents and different on each level. |
|
|
Page -6- |
|
|
The sequence of the grand-children of the red whiskers is 1,113,7261,... which is x1=64*x0+49, the respective sequence of the green whiskers' grandchildren is 3,227,14563,... which is x1 = 64*x0+35. These both last observations correlate with the observation in the base-4-tables, that the sequence of the child-heads is appending 203 or 301 in base 4 which means multiplication by 64 and adding 35 (203 base 4) or 49 (301 in base 4) to the new value. This can be seen in the following display, which is essentially the same as before, but focuses the grand-children-relation and the x0*64+d-relation. |
|
|
|
|
|
And respecting the modulus 3-order |
|
|
|
|
final remark
|
These nice graphs surely "explain" or even "prove" nothing; they only illustrate. The power of a graph is, how helpful it is either to focus the most important known properties or if it suggests an understanding for crucial regularities, which can then be studied with analysis tools. Even if it looks, that this algorithm could match each odd number: this is not sure, and is still left to be rigorously proved. But the greediness of this construction algorithm may possibly be proven, when it can be shown, that the detected progressions, which can be seen as definitions of mutually exclusive classes of numbers, are completely exhaustive for the odd numbers. |
Gottfried Helms
Univ Kassel
|
Some external links concerning the Collatz-problem: |