Contents
Introduction
The residue of a sequence is calculated by counting the number of odd and even terms in a descent and then calculating 2even/(x * 3odd). 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:
R(7)=2^[11]/(7*3^5)=2048/1701=1.2039976…
From here on we will refer to the number of even steps as 'm' and odd steps as 'n'. You can calculate residues using these controls:
Eric Roosendaal introduces residues on one of his pages - http://www.ericr.nl/wondrous/index.html, where he discusses the non-uniformity of the distribution and postulates that the largest residue is R(993):
R(993)=2^[61]/(993*3^[32])=1.2531421…
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.
The Distribution
I've taken all the odd numbers in the range 3-1048575 (220-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.
A-Lists and Residues
The a-lists we introduced on the index page (and continued on their own page) to help locate cycles can also give some insight into the search for residue values. On the observations page we presented an interactive residue calculator that was underpinned by the a-list generated by a seed. The residue equation is;
R(seed)=2^m/(seed*3^n) ≡ (2/3)^n*2^(m-n)/seed
where 'n' is the number of 'a' values and 'm', their sum.
We can set up an algorithm that generates all possible a-lists and then searches this for residue values, this is esentially the same as the working backwards algorithm introduced previously, but is more compact.
The set of a-lists with one member is infinite, starting [[1], [2], [3], …]. The tree is anchored at 1 and for a particular 'a' value, a¬[1,i], the value is:
V(i)=(1*2^[a1i]-1)/3=[1/3, 1, 7/3, 5, 31/3, …]
The odd 'a' values don't generate integers, [1/3, 7/3, …), and we can skip '2' as this generates the loop [1,4,2,1], so the set of viable single member lists starts with [[4], [6], [8], …] and generates the sequence [5, 21, 85, 341, …]. This is the set of odd numbers that converge directly on '1' without visiting any other odd numbers, for instance 341*3+1=1024, which being a power of two cascades all the way to the end.
We can now look at the second term. The set of lists starting with [4] is also infinite and starts [[4,1], [4,2], [4,3], …}. We saw in the previous paragraph, [4] generates the value 5, this series of A-lists generates the odd predecessors of 5. If we label the A-values a¬[2,i] we get:
V(i)=(5*2^[a2i]-1)/3=[3, 19/3, 13, 79, 3, …]
This time only the odd terms are valid, and the set of viable 2-member A-lists based on [4] starts [[4,1], [4,3], [4,5], …].
The set of lists starting with [6]: [6,1], [6,2], [6,3], …] behaves differently, fromt eh previous examples you would expect this to generate all the odd values that map to 21. But if you make the calculation you see that the potential values
V(i)=(21*2^[a2i]-1)/3=[41/3, 83/3, 167/3, …]
which contains no integers. Generally, (3*2^n-1)/3 can never be a multiple of three, so the orbit of any odd number will never pass through a multiple of 3. If an A-list generates a number of the form 6n+1, then to extend this list the 'a' value must be even, and for 6n+5 it must be odd. If an A-list generates a multiple of three it can't be expanded.
Working Backwards
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. The working back page describes this reverse iteration in detail, here we look at searching this backwards tree for residue records. As we saw in the a-lists section the equation to calculate a residue is:
R(x) = 2^m/(x*3^n) ≡ (2/3)^n*2^[(m-n)]/x
The forward equation (for odd numbers only) is
x → (3*x + 1)/2^k
So the reverse calculation is
x → (2^k*x-1)/3
Which has the effect of increasing m by k and n by 1. Not all 'k' values are valid, for instance if we start with 5, we can use k values of [1, 3, 5, 7, …] giving new x values of [3, 13, 53, 213, …]
R(x¬[n+1])/R(x¬n)=(2^[m+k]/(3^[n+1]*x¬[n+1])/(2^m/(3^n*x¬n))
=(2^[m+k]*3^n*x¬n)/(2^m*3^[n+1]*x¬[n+1])
=(2^k*x¬n)/(3*x¬[n+1])
=(2^k*x¬n)/(3*((2^k*x¬n-1)/3)
=(2^k*x¬n)/(2^k*x¬n-1)
=1+1/(2^k*x¬n-1)
This term is alway greater than one so the residues of the precursors of a number will always be greater than the residue of the number itself. This implies that if there there is a largest residue then it must be a multiple of 3 (as multiples of 3 don't have precursors).
Although the value is always increasing, for large x the difference is very small. I suspect that the most you can get out of a sequence is limited, but this isn't easy to analyse, as for instance, when k is 1 the value of x decreases, whereas for 2 or more it increases.
Another way to work backwards uses the 4n+1 series described here. This only has one or two predecessors at each level and k is always 1 or 2. Because there are only two routes the tree can take at each step we can map the options onto the binary digits 0 and 1. The choice is arbitrary, but I'm choosing to have '0' represent the (2x−1)/3 and (4x−1)/3 options and 1 represent the 4n+1 option. You can iterate backwards in this tree using these controls. The number creates a binary sequence of steps, the "table" option extends it.
Partitioning the Distribution
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 (about 95%) 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.
|
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. |
If we run the reverse iteration for 1 we get the precursors and residues:
| Precursor | Residue |
| 5 | 1 + 1/15 |
| 21 | 1 + 1/63 |
| 85 | 1 + 1/255 |
| 341 | 1 + 1/1023 |
| 1365 | 1 + 1/4095 |
| 5461 | 1 + 1/16383 |
| 21845 | 1 + 1/65535 |
| 87381 | 1 + 1/262143 |
| 349525 | 1 + 1/1048575 |
| … | … |
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 iterations that start in the range 3-1048575 partition among the precursors, and the range of residue values encountered in each partition. The first row represents '5', which doesn't go through a precursor.
(1 + 1 / a) * (1 + 1 / b) = 1 + (a + b + 1) / ab
| Precursor | Multiplier | Residue | Frequency | Min | Max | |
|---|---|---|---|---|---|---|
| - | 1 + 1/15 | 1.066666666667 | 1 | 1.066 | 1.066 | |
| 3 | 1 + 1/9 | 1 + 5/27 | 1.185185185185 | 1 | 1.185 | 1.185 |
| 13 | 1 + 1/39 | 1 + 11/117 | 1.0940170940171 | 249,018 | 1.094 | 1.253 |
| 53 | 1 + 1/159 | 1 + 35/477 | 1.0733752620545 | 239,467 | 1.073 | 1.198 |
| 213 | 1 + 1/639 | 1 + 131/1917 | 1.0683359415754 | 1 | 1.068 | 1.068 |
| 853 | 1 + 1/2559 | 1 + 515/7677 | 1.0670834961574 | 2,577 | 1.067 | 1.068 |
| 3,413 | 1 + 1/10239 | 1 + 2051/30717 | 1.0667708435069 | 756 | 1.066 | 1.067 |
| 13,653 | 1 + 1/40959 | 1 + 8195/122877 | 1.0666927089691 | 1 | 1.066 | 1.066 |
| 54,613 | 1 + 1/163839 | 1 + 32771/491517 | 1.0666731771231 | 25 | 1.066 | 1.066 |
| 218,453 | 1 + 1/655359 | 1 + 131075/1966077 | 1.0666682942733 | 4 | 1.066 | 1.066 |
| 873,813 | 1 + 1/2621439 | 1 + 524291/7864317 | 1.0666670735679 | 1 | 1.066 | 1.066 |
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.
Finding the Maximum
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:
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
A second excursion was made at 505, where the precursors are
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. |
Exploring the limits
Every number has an infinite sequence of precursors (in the 4n+1 tree) related by the formula
x → 4 × x + 1
Where the residue decreases by the factor (1 - 1 / (4 × x + 1)). You can see how the residue converges as you move along this sequence using the following controls. The number in the first box is the value of the binary sequence that generates the first seed, for instance, '5' generates the sequence [1,0,1], which leads to 13.
These next controls will search various seeds for residue records along the 4n+1 chains. It's been initialised with seeds up to 100, if you try a larger number you may find some more.
If you do try larger numbers you will find the residue for 993 is 1.253142…, the largest known, but this isn't the value with the largest asymptote. The 993 sequence converges on about 1.252722…, whereas the number 35271, whose residue is only 1.252995… converges on 1.252983… As you get deeper into the tree the penalty for taking the 4n+1 route gets smaller and smaller so there is plenty of scope for searching. For instance there are an infinite number of values in the 4n+1 sequence based on 35271 that have residues around 1.252983, a lot of these will all have predecessors with higher residues.
Value Limited Backward Searching
 |
The charts on the left show the results of what I call "Value Limited
Backward Searching", based on the seed of 3973, R=1.252827. The
results are divided into bins of 0.00001. |
Width Limited Backward Searching
 |
This works by taking a seed and finding the 'n' smallest precursors, 'n' being the width. The next iteration works by finding the precursors of the current set of 'n' values and extracting the 10 smallest. There is no stopping condition for this search, we can either stop when the smallest value is greater than some threshold or after a fixed number of iterations (depth). If we try this for a seed of 5, with a width of 4 and depth of 5 we get the chart on the left. Because this algorithm only takes the smallest values for each iteration it has the potential to miss interesting results. In this example, for instance, the branch at 61 is chopped off. Using a width of 4 would also miss 993. This is because the precursor, 917, appears in the 12th column, as can be seen in the next table, which shows how the iteration would progress with a width of 12. |
| 3 | 13 | 53 | 213 | 853 | 3413 | 13653 | 54613 | 218453 | 873813 | 3495253 | 13981013 |
| 17 | 35 | 69 | 141 | 277 | 565 | 1109 | 1137 | 2261 | 2275 | 4437 | 4549 |
| 11 | 23 | 45 | 93 | 181 | 369 | 373 | 725 | 739 | 753 | 1477 | 1493 |
| 7 | 15 | 29 | 61 | 117 | 241 | 245 | 469 | 483 | 497 | 965 | 981 |
| 9 | 19 | 37 | 77 | 81 | 149 | 163 | 309 | 321 | 325 | 331 | 597 |
| 25 | 49 | 51 | 99 | 101 | 197 | 205 | 217 | 397 | 405 | 433 | 441 |
| 33 | 65 | 67 | 131 | 133 | 261 | 269 | 273 | 289 | 525 | 529 | 533 |
| 43 | 87 | 89 | 173 | 177 | 179 | 349 | 355 | 357 | 385 | 693 | 705 |
| 57 | 59 | 115 | 119 | 229 | 237 | 461 | 465 | 473 | 477 | 513 | 917 |
| 39 | 79 | 153 | 157 | 305 | 307 | 315 | 317 | 611 | 613 | 629 | 1221 |
| 105 | 203 | 209 | 211 | 407 | 409 | 419 | 421 | 813 | 817 | 837 | 845 |
| 135 | 139 | 271 | 279 | 281 | 541 | 545 | 557 | 561 | 563 | 1085 | 1089 |
| 185 | 187 | 361 | 363 | 371 | 375 | 721 | 723 | 741 | 749 | 1445 | 1453 |
| 123 | 247 | 249 | 481 | 493 | 499 | 961 | 963 | 989 | 997 | 1925 | 1937 |
| 329 | 641 | 657 | 659 | 665 | 1281 | 1283 | 1291 | 1317 | 1329 | 2565 | 2629 |
| 219 | 427 | 439 | 443 | 855 | 877 | 1709 | 1721 | 1757 | 1773 | 3421 | 3505 |
| 295 | 569 | 585 | 1139 | 1147 | 1169 | 1171 | 1181 | 2277 | 2341 | 4557 | 4561 |
| 379 | 393 | 759 | 779 | 787 | 1517 | 1529 | 1561 | 1573 | 3037 | 3117 | 3121 |
| 505 | 519 | 1011 | 1019 | 1049 | 2021 | 2077 | 2081 | 2097 | 4045 | 4049 | 4077 |
| 673 | 679 | 699 | 1347 | 1387 | 2693 | 2699 | 2717 | 2769 | 2797 | 5389 | 5393 |
| 897 | 905 | 1795 | 1799 | 1811 | 1849 | 3589 | 3595 | 3621 | 3729 | 7181 | 7185 |
| 603 | 1199 | 1207 | 2393 | 2413 | 2465 | 4785 | 4787 | 4793 | 4797 | 4829 | 9573 |
| 799 | 1595 | 1609 | 1643 | 3191 | 3195 | 3197 | 3217 | 3219 | 6381 | 6437 | 6573 |
| 1063 | 1065 | 1095 | 2127 | 2131 | 2145 | 4253 | 4261 | 4289 | 4291 | 4381 | 8509 |
| 1417 | 2835 | 2841 | 2859 | 5669 | 5681 | 5721 | 5841 | 11341 | 11345 | 11365 | 11437 |
| 1889 | 3779 | 3787 | 7557 | 7563 | 15117 | 15121 | 15149 | 15153 | 15249 | 30229 | 30253 |
| 1259 | 2519 | 5037 | 5049 | 10077 | 10099 | 20149 | 20161 | 20197 | 40305 | 40309 | 40337 |
| 839 | 1679 | 3357 | 6717 | 13429 | 13465 | 26865 | 26869 | 26881 | 26891 | 26929 | 53717 |
| 559 | 1119 | 2237 | 4477 | 8949 | 17905 | 17909 | 17927 | 17953 | 35797 | 35811 | 35825 |
| 745 | 1491 | 2981 | 5965 | 5969 | 11925 | 11939 | 11951 | 23861 | 23873 | 23877 | 23883 |
| 993 | 1987 | 3973 | 3979 | 7949 | 7953 | 7959 | 7967 | 15893 | 15907 | 15915 | 15917 |
  
|
The residues generated from the above table are shown in the chart on the
left. If you compare this chart with the earlier ones you will see that
here the residues are clustered more towards the right. So although this
algorithm has flaws it does tend to find the higher residues. If we extend the iteration to a depth of 300 we get the second chart, where all the values are crammed up at the right hand edge. The 3rd chart is a log10 chart of the spike in the second chart. This only shows values greater than one so 993 at 1.2531 doesn't appear. By the 300th iteration the numbers and residues we were working with are shown in the following table.
These residues are a bit unreliable as if we calculate R(149316262419637465401) directly we get 1.2521362730073702 (a difference of 0.0000000000000066). Depending on how you do the calculations introduces different rounding errors. |
|||||||||||||||||||||||||
 |
The chart on the left shows the effect (on the log plot) of widening the
search to 24. It's found a few more of the very high ones around 1.2529
but the current search value is R(4556863913839675) = 1.25211, which is
actually worse than the narrower search. The largest non multiple of 3 found along the way R(250817) = 1.2529895. This and the other top 10 values found form part of a tree routed at 5297 (R=1.2529), which is one of the predecessors of 3973 (R=1.2528) we found earlier. |
Other 3x+1 related pages
Click the images...
 |
Working Backwards: The forward equation we introduced above is quite straightforward. This page explores working backward to find a number's predecessors. |
|
Domains of Attraction: Before converging on one, sequences must pass through one of one's predecessors (1, 5, 21, etc). This pages explores the relative popularity of these gateways. |
|
Residue Records: Although 993 is probably the largest , if we ignore multiples of three, the numbers keep growing. |