Domains of attraction

We've seen earlier that once we remove the even numbers the tree becomes more compact. Now the root node (one) has an infinite number of immediate precursors, starting with:

1, 5, 21, 85, 341, 1365, 5461, 21845, 87381, 349525, 1398101, 5592405, 22369621, 89478485, 357913941, 1431655765, 5726623061, 22906492245, 91625968981, 366503875925, ...

This gives us the opportunity to partition the set of positive integers according to which of these precursors they pass through on their way to one. Most numbers appear to go through 5and there is no obvious pattern to how they are arranged. The following sections discus this in more detail.

For small numbers most sequences pass through 5, but how do the proportions vary as we move to higher numbers? To get a better feel for this I've written some C++ code using Microsoft's C++ 7 64 bit integer support, which runs quite fast even on my 800MHz PC. I divided the seeds into tranches of 2¹⁹ (512288) odd numbers. This first chart show the number of seeds in the first 99 tranches that converge on 5. The first 5 tranches contain about 492000 values (about 93.8%) but the distribution spreads out as we move to larger numbers. The lowest value observed, 472345 is 90.1%.

This next chart shows the corresponding values for 85 (dark blue) and 341. Here 20,000 represents about 3.8% of the values.

This 3rd chart compares 5461 (dark blue) with 21845. 200 is about 0.04%.

These chart shows the ratio of nodes converging on 341 to those converging on 85. The first chart shows the ratios in the corresponding tranches, the second the cumulative ratio.

By running an exhaustive search of the first 2 million numbers I've identified the smallest member of the first 11 sub-trees. We can also see how the frequency of the various routes varies as the sample size increases. The red (6n+3) sub-trees have very few members are they are confined to just the root multiplied by successive powers of two. What is more interesting is that the 6n+5 sub-trees have more members that the preceding 6n+1 sub-tree, whereas statistically one would expect there to be more converging on the smaller number. This might change as we include much larger numbers.

Sub-tree	Smallest	1-99	1-255	1-1023	1-4095	1-1048575
1	1	7	8	10	12	20
5	3	87	234	953	3839	983,309
21	21	3	4	6	8	16
85	75	2	6	27	98	24,830
341	151		3	26	136	39,768
1,365	1,365				2	10
5,461	5,461					104
21,845	14,563					480
87,381	87,381					4
349,525	184,111					33
1,398,101	932,067					1

Converging on 5: This page uses this reverse iteration algorithm to find those numbers that converge on 5.

The 85 Tree: See a an illustration of the base of the 85 tree.

Residues: These are defined as 2even/(X * 3odd). Their distribution is quite interesting, and is related to these domains of attraction.

Raw Data: The numbers behind the graphs..