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) = 211 / (7 * 35) = 2048/1701 = 1.2039976...

From her 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) = 261 / (993 * 332) = 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) = 2m/(seed x 3n) ≡ (2/3)n × 2m-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 single 'a' value, a1, the next number is:

1 × (2a1 − 1) / 3 = [1/3, 1, 7/3, 5, 31/3, ...].

The odd 'a' values don't generate integers and we can skip 2 as this generates the loop [1,4,2,1], so the set of viable 1-member lists starts with [[4], [6], [8], ...].

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], ...} and generate the sequence

5 × (2a2 − 1) / 3 = [3, 19/3, 13, 79, 3].

This time only the odd terms are valid, and the set of viable 2-member lists based on [4] starts [[4,1], [4,3], [4,5], ...].

The set of lists starting with [6]: [6,1], [6,2], [6,3], ...] generates the series

21 × (2a2 − 1) / 3 = [41/3, 83/3, 167/3, ...]

which contains no integer values. Generally if an a-list generates a value that is a multiple of 3 it is the end of the line. If a list generates a number of the form 6n + 1 then the next 'a' value must be even and for 6n + 5 it must be odd.

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) = 2m/(x × 3n) ≡ (2/3)n × 2m-n / x;

The forward equation (for odd numbers only) is

x → (3 × x + 1) / 2k.

So the reverse calculation is

x → (2k × 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(xn+1) / R(xn) = (2m+k/(3n+1 × xn+1) / (2m/(3n × xn))

= (2m+k × 3n × xn) / (2m × 3n+1 × xn+1)

= (2k × xn) / (3 × xn+1)

= (2k × xn) / (3 × ((2k × xn - 1) / 3)

= (2k × xn) / (2k × xn - 1)

= 1 + 1 / (2k × xn - 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.

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:

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 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.

(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:

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.

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.

VLBS works by taking the seed and calculating all the immediate precursors that are less than the limit. For 3973 and a limit of 1000000 these are 5297, 21189, 84757 and 339029. We then repeat this process on all the precursors, building up a list of all the numbers that converge on the seed without venturing outside the limit. This won't find all the values in a given range, though it will get most of those less than the square root of the range.

The charts on the left show the application of this algorithm with widths of 1 million, 10m, 100m and 1 billion. Notice how the distribution hardly changes.

The little peak to the right of the first chart represents 3531, where R=1.253024.

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.

149316262419637465401  1.2521362730073768
298632524839274930785  1.2521362730073768
298632524839274930803  1.2521362730073768
597265049678549861569  1.2521362730073768
597265049678549861571  1.2521362730073768
597265049678549861575  1.2521362730073768
597265049678549861605  1.2521362730073768
1194530099357099723139  1.2521362730073768
1194530099357099723141  1.2521362730073768
1194530099357099723213  1.2521362730073768
1194530099357099723217  1.2521362730073768
2389060198714199446277  1.2521362730073768

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.

See Also

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.

Other pages

 

(c) John Whitehouse 2011 - 2016