3x+1 Residues

The residue of a sequence is calculated by counting the number of odd and even terms in a descent and then calculating 2^even/(x * 3^odd). If we choose x=7, for instance we get the series [7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1], which has 11 even and 5 odd members (we don't count the '1'),  so:

Eric Roosendaal introduces residues on one of his pages - http://personal.computrain.nl/eric/wondrous/residues.htm, where he discusses the non-uniformity of the distribution and postulates that the largest residue is R(993):

On the rest of this page we will discus the distribution of the residue values and speculate on whether R(993) really is the largest value. My distribution will be slightly different from Eric's as I ignore the even numbers.

I've taken all the odd numbers in the range 3-1048575 (2²⁰-1) and divided their residues into bins of 0.001, in the range 1-1.260. The resulting distribution looks like

Clearly this is non-uniform. There is a large gap between 1.012 and 1.065 (actually there is one entry at R(21)=1.015873... which doesn't register on the chart) and numerous smaller gaps. The colour coding is explained in a later section.

If we have a number 'x' and its residue R(x) we can use reverse iteration to find the residues of its immediate odd precursors. For a number 'x' of the form 6n+1 the smallest odd precursor is 8n+1, and for 6n+5 it is 4n+3. The sequences continue:

Each value is 4 times the previous one, plus 1. The backward residue multipliers are (2^k*x)/ (3 * x_back), where 'k' is 2,4,6,... for 6n+1 and 1,3,5,...for 6n+5. The first iterations give

We can obtain the other multipliers by repeatedly iterating a/3b -> 4a/3(4b+1), or the simpler but equivalent a/b -> 4a/(4b+3). But as a is always b+1, we have (b+1)/b -> 4(b+1)/(4b+3) = (4b+4)/(4b+3) = 1 + 1/(4b+3).

If we replace n by (x-1)/6 or (x-5)/6 we get 

For positive 'n' all these multipliers are greater than 1, so the residues of the precursors of a number will always be greater than the residue of the number itself. If there is a largest residue then it must be a multiple of 3 (as multiples of 3 don't have precursors).

From the previous section we see that all odd numbers not divisible by 3 have an infinite number of immediate precursors. This diagram shows the first few for '1'. The labels show the number of iterations.

When discussing domains of attraction, we noticed that most (small) numbers pass through 5 on their way to one. These domains are used as the basis of the colour coding in the above chart. The half a million values used to construct the above chart are colour coded acording to which of these values they pass through on their way to 1. The details for each domain are shown in the table.

Domain Frequency min max 5 491,853 1.066 1.253 21 1 1.015 1.015 85 12,317 1.003 1.011 341 19,819 1.000 1.008 1,365 1 1.000 1.000 5,461 42 1.000 1.000 21,845 231 1.000 1.000 87,381 1 1.000 1.000 349,525 21 1.000 1.000 1,398,101 1 1.000 1.000

The multiples of 3 (21, 1365, ...) can only ever have one value so they don't really enter into the calculation. The values generated by the 85 and 341 sub-domains overlap but are confined to very small values compared to 5 (though there is no guarantee this is the case when we include the infinite set). The other values, 5461 etc. don't lead to any values greater than 1.001 which is why they don't feature in the above chart. This is a close up view of the range 1-1.015 where the contribution from 21845 becomes visible. 5461 is still too small to register.

If we run the reverse iteration for 1 we get the precursors and residues:

The second value of each pair is how much the residue will be multiplied by when moving from 1 to the corresponding precursor, but as R(1) = 1, so R(5) = 1+1/15.  Because the residue always increases as we move back up the tree all values that converge on 5 will have a residue greater than 1+1/15. Similarly all the values that converge on 85 will have a residue greater than 1+1/255 and those that converge on 341, 1+1/1023. This explains the leftmost extent of the distributions, but doesn't constrain the right.

The structure of the 5-domain is also quite complicated. We can use reverse iteration again to find the immediate precursors of 5 and their residue multipliers (shown in the next table). To get the actual residues the numbers in the second column need to be multiplied by R(5)=16/15. We also show the number of iterations that start with numbers in the range that 3-1048575 that go through each, and the range of residue values encountered. The first row represents '5' which doesn't go through a precursor.

The chart obtained by plotting these values looks like this. The uniform block that represented '5' in the previous chart now has 4 noticeable sub-components, of which two (13 and 53) cover a significant range.

The next graph shows the 13 and 53 routes further sub-divided.

It looks like all largish residues (for starting values less than 1048576) will pass through 35,53,5,1 or 17,13,5,1, with all values over 1.2 taking the second route.

The residues of a number's precursors are always larger than that of the number itself. The problem is that for largish numbers the increment is quite small. To obtain a large residue we therefore need a sequence with plenty of small numbers. All the tractable examples of this sort of sequence have been studied and the conclusion is that R(993) is the largest residue. To disprove this we would have to find a very long sequence, with very big numbers, where a lot of very small increments combine to overcome this.

The image on the left shows the descent of 993, R(993)=1.2531421. The branches show the points along this descent where the route doesn't follow the path of maximum residue multiplier. For instance at 43 (R=1.2389) the possible precursors were 57, 229 and 917. The corresponding inverse residue multipliers were N Multiplier R(N) 57 1 + 1/171 1.2461562550043928 229 1 + 1/687 1.2407145246331945 917 1 + 1/2751 1.2393615098844124 By following the 917 route we took a hit of about 0.007, quite significant in this game. R(745)=1.2527, not much less than 1.2531. There is an infinite tree of numbers rooted on 745, all of which have residues greater than 1.2527. Are none of these greater than 1.2531? The immediate predecessors of 745 are N Multiplier R(N) 993 1 + 1/2979 1.2531421443950681 3973 1 + 1/11919 1.2528267298105236 15893 1 + 1/47679 1.2527479009720532 A second excursion was made at 505, where the precursors are N Multiplier R(N) 673 1 + 1/2019 1.2494773856412769 2693 1 + 1/8079 1.2490134133480568 10773 1 + 1/32319 1.2488974741098366 Here by taking the less obvious route we sacrificed about 0.0046. This next chart shows the range of residues in the trees based on 673, 2693 and 3973 for values up to a million. This shows that although 673 might have appeared a better option at the time, 2693 had more potential overall and eventually produced the record holder at 993. 3973 is the next predecessor of 745 after 993 and would be a good candidate to start a search for higher residues from. I extended the above search out to 10 million but the shape of the chart was almost unchanged.