Paper 1
Paper 1 - A view of the structure resulting from the Collatz algorithm.
This paper is primarily concerned with the definition and construction of what I have called nchains. The tree of integers that converge to one is constructed of nchains. An nchain is a set of integers that require n steps before they converge to the same value.
My approach is also different to other approaches in that I include all even integers as significant start values.
| 1.1 | The Collatz conjecture states that by starting with any positive integer and alternating the following actions, eventually the odd integer produced by action (a) will be 1.
(a) if an even integer, divide by 2 until an odd integer is obtained One cycle through (b) and (a), ending with an odd integer, is a step. |
| 1.2 | Given an even integer as a start value, the normal definition of the Collatz conjecture would immediately reduce the even integer to an odd integer by dividing by the appropriate power of 2. However, throughout the analysis, start numbers that are even are treated differently. Whether the start value is an even or an odd integer, the first action is to multiply by 3 and add 1. The algorithm becomes: |
| Take any positive integer x where x >= 0
Calculate 3x+1 If x is even, this completes a step If x is odd, then 3x+1 is even, so divide by 2 until an odd integer is obtained to complete the step. Then follow the standard Collatz algorithm; actions (b) and (a) above. |
|
| Note: The usual approach to Collatz is to ignore even start values. Their inclusion in this manner, apparently doubling the number of possible start values requiring consideration, is essential to the calculations made in this paper. Since, after the first step, only nodes(odd integers prime to 3) are reached in each step, the new algorithm covers exactly the same odd integers as the usual approach. | |
| 1.3 | Integers that converge to the same value after the same number of steps are at the same level .
We use the notation Lr when referring to the relative levels of integers. The symbol for 'at the same level' is ==. If r is given an actual integer value, it implies that it takes r steps for integers at that level to converge to 1. Here is an intriguing example: 123456789 and 987654321 are both at L58. |
| 1.4 | A step from Lr to L(r-1) is a step down and the inverse, from L(r-1) to Lr, is a step up.
The symbol for a step down is >> and for a step up is <<. The sequence of odd integers produced by stepping down is a thread. Should a value be repeated in a thread, then the thread loops. No integer has yet been found which does not eventually loop on 1. |
| 1.5 | The set of integers at Lr that converge to the same integer at L(r-n) after n steps and that do not converge before reaching L(r-n), form an nchain.
An nchain is a subset of integers at the same level. A chain is the generic term for nchains. The first integer in a chain is a pivot. Each integer in a chain after the pivot is a link. Pivots and links may be odd or even positive integers; in fact, as will be seen later, for n > 2, an nchain contains more even than odd integers. |
| 1.6 | The length of every nchain is infinite.
Note: This paper is basically about the construction of nchains. Every integer in an nchain is the pivot of an (n-1)chain, every integer in the infinite number of (n-1)chains is the pivot of an (n-2)chain, and so on down to a set of 1chains. Starting with a pivot, it is theoretically possible (but, for values of n greater than 6, impracticable due to the sheer length of the sequence) to determine a sequence of equations which are cycled through to define the next link as a function of the previous link. For each n there is a common cycle of functions which define all nchains. The number of equations required to define the cycle is 2x3n-2 for n>1. Where n=1 it is one equation. |
| Example
Consider the 3chain starting with 27 as its pivot (how 3chains are derived comes later!) This 3chain is: 27, 55, 3564, 1782, 57040, 456324, 7301195, 14602391, . . . . . . 27 >> 41 >> 31 >> 47 55 >> 83 >> 125 >> 47 3564 >> 10693 >> 2005 >> 47 1782 >> 5347 >> 8021 >> 47 etc. Each value in the 3chain is the pivot of a 2chain For 27, the 2chain is 27, 220, 1763, 14108, . . . . . 27 >> 41 >> 31 220 >> 661 >> 31 1763 >> 2645 >> 31 etc. For 55, the 2 chain is 55, 444, 3555, 28444, . . . . . . 55 >> 83 >> 125 444 >> 1333 >> 125 3555 >> 5333 >> 125 etc. Each value in each 2chain is the pivot of a 1chain. Here are a couple of examples: For 1763, the 1chain is 1763, 7053, 28213, . . . . 1763 >> 2645 7053 >> 2645 28213 >> 2645 etc. For 444, the 1chain is 444, 1777, 7109, . . . . . 444 >> 1333 1777 >> 1333 7109 >> 1333 |
|
| 1.6 | Only the pivots of nchains are available as pivots and links for the construction of (n+1)chains. No link can be a pivot or link in a higher nchain.
If a pivot converges to 1, then the infinite number of links in the nchain and its associated (less than n)chains also converge to 1. The pivot is not necessarily the least integer in an nchain (for example: if the first function in a cycle is p/2). |
| 1.7 | The set of all possible integers created by stepping up and down, and by determining integers at the same level as those found, creates a graph
A graph can be obtained by starting with any integer and stepping up and down from that integer. If the integer is in the pass Collatz set, i.e. it will loop on 1 after a finite number of steps down. All graphs contain an infinite number of levels. A graph of integers which fail Collatz would either step down infinitely without reaching 1 or loop on a thread of values. |
| 1.8 | Proving the Collatz conjecture implies showing that there exists only one graph that contains every positive integer. This paper explores the structure of such a graph.
There are an infinite number of nchains for every value of n. Only one of the set of nchains occurs at Ln; this is the nchain for which the pivot is zero. All other nchains occur at higher levels than Ln. It is possible to calculate the proportion of the positive integers contained in every set of nchains; it is shown in Section 10 that this proportion decreases by a constant factor of 13/16 for every increment of n where n > 4. 2. 1chains
|
| 2.1 | Let F be the step down function, then an integer x steps down to an odd integer y, such that:
y = F(x) = (3x + 1)/2n where n has that integer value which makes y an odd integer (and is zero if x is even). If x is replaced by 4x + 1, we get F(4x +1) = (12x + 4)/2m = (3x + 1)/2(m+2) whence m+2 must equal n as it also reduces 3x + 1 to an odd integer, i.e. Hence x == 4x +1 == 16x + 5 == 64x + 21 == . . . . that is x == 4s.x + (4s - 1)/3 for all positive integral values of s.An infinitely long chain of links can formed, starting with any positive integer, by multiplying by 4 and adding 1 successively. This is the 4p + 1 rule, where p is the previous link in the chain, i.e. 4p+1 is the one equation needed to define a 1chain. |
| 2.2 | Applying the inverse of the 4p+1 rule shows that the pivot of a 1chain may be an even integer. This is the justification for the revised algorithm for Collatz. |
| Example
9 = 4x2+1 2 >> 7 and 9 >> 7 2 is at the same level as 9 and is the pivot of a 1chain whose second term is 9. |
|
| 2.3 | 1/4 of the positive integers have format 4i+1 (where i is a positive integer) and are therefore at the same level as i.
All 1chain pivots are either of format 2i or 4i+3. If the pivot is even, the powers of 2 needed to converge successive terms in the 1chain are 0,2,4,6,etc. If the pivot is odd, the powers of 2 needed to converge are 1,3,5,7,etc. After considering 1chains, only 3/4 of the positive integers need to be tested. Only an integer that is a pivot of a 1chain may be a pivot or a link in a 2chain. |
| 2.4 | There is one 1chain at L1: 0, 1, 5, 21, 85, 341, . . . . . . |
| 2.5 | Every positive integer, including 0, is either a pivot or a link on a 1chain. |
| 3.1 | Stepping down from any integer is a straightforward operation and can always be performed. It is also always possible to step up to find an integer at the next level up. The table below lists how to step up from any integer at Lr to an integer at L(r+1). It is not possible to step down to a multiple of 3 or to an even integer. The method generates the pivot of the 1chain at L(r+1) that steps down either to the given integer or to the first node after the given integer in the 1chain containing the given integer.
Let e represent an even integer and o an odd integer, then all integers have one of the formats 3e, 3e+1, 3e+2, 3o, 3o+1 or 3o+2: |
| Lr | L(r+1) | |
| 3e | steps up to | 4e |
| 3e + 1 | steps up to | e |
| 3e + 2 | steps up to | 16e + 12 |
| 3o | steps up to | 4o |
| 3o + 1 | steps up to | 8o + 3 |
| 3o + 2 | steps up to | 2o + 1 |
Note: This table is the fundamental basis of this paper.
| Proof:
Apply Collatz to each L(r+1) integer and use the 4p+1 rule when appropriate. |
||
| 4e | >> 12e + 1 = 4(3e) + 1 == | 3e |
| e | >> | 3e + 1 |
| 16e + 12 | >> 48e + 37 = 4(12e +9) + 1`== 12e + 9 = 4(3e+2) + 1 == | 3e + 2 |
| 4o | >> 12o + 1 = 4(3o) + 1 == | 3o |
| 8o + 3 | >> 24o + 10 ; (24o + 10) / 2 = 12o + 5 = 4(3o+1) + 1 == | 3o+1 |
| 2o+1 | >> 6o + 4 ; (6o + 4) / 2 = | 3o + 2 |
| 4.1 | The 2 functions which alternate to form the links in a 2 chain are (see Appendix 1):
8p+3 if p is even 8p+4 if p is odd |
|
|
| 4.2 | There is one 2chain at L2 : 0, 3, 28, 227, 1820, . . . . . . . |
| 4.3 | The pivot of a 2chain cannot have format 4i+1; the pivot of a 2chain is an integer of format either 2i or 4i+3, so all 2chain links have format either:
8(2i)+3 = 16i+3 8(4i+3)+4 = 32i+28 The format of the links alternates between 16i+3 and 32i+28 and all integers of these formats are links on a 2chain. Thus 1/16 + 1/32 of the positive integers do not need to be tested if the pivots of 2chains are tested. Deleting 1chain and 2chain formats leaves 3/4 - 3/32 = 21/32 of the positive integers available to construct 3chains. |
| 5.1 | The cycle of 6 functions required to produce a 3chain is (see Appendix 2):
8p+4, 16p+11, 2p+1, 64p+44, p/2, 32p+16 The formats available for a 3chain pivot are those left after deleting the 1chain and 2chain link formats; this means that a 3chain pivot must have one of the following formats: 8o+3, 4e+7, 2o, 4e, 8e+4 or 16e+12 These formats encompass the six possible formats listed in 3.1. The calculations in Appendix 2 show that each of these 6 formats requires the cycle to start at a different one of the six functions. Which function is defined by the format of the pivot. For a pivot format of 8i, the first function in the cycle is 8p+4 |
|
| Example
a 3chain is : 8, 68, 1099, 2199, 140780, 70390, 2252496, 18019972, . . . . each integer of which steps down to 29 in 3 steps. |
||
| For a pivot of format 16i+4, the first function in the cycle is 16p+11 | ||
| Example
a 3chain is : 20, 331, 663, 42476, 21238, 679632, 5437060, 86992971, . . . . each integer of which steps down to 35 in 3 steps |
||
| For a pivot of format 16i+11, the first function in the cycle after a pivot of format 8o+3 is 2p+1 | ||
| Example
a 3chain is : 11, 23, 1516, 758, 24272, 194180, 3106891, 6213783, . . . each integer of which steps down to 5 in 3 steps |
||
| For a pivot of format 32i+12, the first function in the cycle is p/2 | ||
| Example
a 3chain is : 12, 6, 208, 1668, 26699, 53399, 3417580, 1708790, . . . . each integer of which steps down to 11 in 3 steps |
||
| For a pivot of format 8i+7, the first function in the cycle is 64p+44 | ||
| Example
a 3chain is : 15, 1004, 502, 16080, 128644, 2058315, 4116631, 263464428, . . . each integer of which steps down to 53 in 3 steps |
||
| For a pivot of format 4i+2, the first function in the cycle is 32p+16 | ||
| Example
a 3chain is : 2, 80, 644, 10315, 20631, 1320428, 660214, 21126864, . . . . each integer of which steps down to 17 in 3 steps |
||
| 5.2 | In each 3chain the format of links cycles through the 6 stepping up formats (see 3.1) in the following sequence:
16e+12, e, 4e, 4o, 8o+3, 2o+1 |
|
| 5.3 | The format of the links in a 3chain are calculated as follows:
Thus a further 1/16 + 1/128 + 1/64 +1/256 + 1/32 + 1/512 = 63/512 of the positive integers do not need to be tested if the pivots of 3chains are tested. |
|
| 5.4 | Deleting 3chain link formats leaves 21/32 - 63/512 = 273/512 of the positive integers available to construct 4chains.
Note that 273/512 = 13/16 of 21/32. |
|
| 5.5 | The 3chain at L3 is 0, 4, 75, 151, 9708, 4854, 155344, 1242756, 19884107, 39768215, . . . . . . |
| 6.1 | The functions which define the (less than n)chains must be known before an nchain can be constructed. As an example for the procedure, the construction of a 3chain (as done in Appendix 2) will be used, but the method is equally applicable to all nchains. | ||||||||||||||||||
| 6.2 | The first step is to determine the link formats of all the (less than n)chains; these can be calculated from the link functions. | ||||||||||||||||||
| Example
The 1chain link function is 4p+1 and all the links in a 1chain have format 4i+1 The 2chain link functions are 8p+3, 8p+4. Since these pivot and links cannot have format 4i+1, they have format either 2i or 4i+3. If the pivot is 2i, then the links have format 16i+3, 128i+28, 1024i+227, etc. If the pivot is 4i+3 , then the links have format 32i+28, 256i+227, 2048i+1820, etc. The links in a 2chain alternate between the formats 16i+3 and 32i+28. |
|||||||||||||||||||
| 6.3 | Discarding the link formats of the (less than n)chains leaves the formats available as pivots for nchains. | ||||||||||||||||||
| Example
The formats to be discarded for the (less than 3)chains are 4i+1 , 16i+3 and 32i+28. This leaves six formats available for 3chain pivots: 8i, 4i+2, 32i+12, 16i+4, 16i+11 and 8i+7 |
|||||||||||||||||||
| 6.4 | Each available pivot format must be associated with one of the stepped up formats in section 3.1. | ||||||||||||||||||
| Example
8i has format 4e 4i+2 has format e 32i+12 has format 16e+12 16i+4 has format 4o 16i+11 has format 8o+3 84+7 has format 2o+1 |
|||||||||||||||||||
| 6.5 | Construct the (n-1)chains whose pivots are the format from which the stepped up formats are obtained. | ||||||||||||||||||
| Example
3e steps up to 4e, the 8i ipivot, so a 2chain is 3e, 24e+3, 192e+28, 1536e+27, etc. 3e+1 steps up to e, the 4i+2 pivot, so a 2chain is 3e+1, 24e+12, 192e+99, etc. |
|||||||||||||||||||
| 6.6 | The pivot of each 2chain can be expressed in terms of i. | ||||||||||||||||||
| Example
The pivot format 16i+11 has format 8o+3, thus o = 2i+1. 3o+1 steps up to 8o+3, so the 2chain pivot has format 3(2i+1) +1 = 6i+4 |
|||||||||||||||||||
| 6.7 | At this point it is convenient to check that stepping down from the nchain pivot does give the (n-1)chain pivot (the i format of the 2chain pivot is irrelevant for further calculation). | ||||||||||||||||||
| Example
16i+11 >> (48i+34)/2 = 24i+17 == 6i+4 (using the 4p+1 rule). |
|||||||||||||||||||
| 6.8 | Convert each link in each (n-1)chain to a section 3.1 format and do the appropriate step up to create an nchain. | ||||||||||||||||||
| Example
Consider the 2chain: 3e, 24e+3, 192e+28, 1536e+227, etc. This becomes:
|
|||||||||||||||||||
| 6.9 | Compare successive links in each nchain to determine the link functions. | ||||||||||||||||||
| Example
The 3chain constructed in 6.8 starts: 4e 32e+4, 512e+75, 1024e+151 Thus the cycle of link functions starts 8p+4, 16p+11, 2p+1 |
|||||||||||||||||||
| 6.10 | The link functions have a cycle of 2x3n-2 functions for every nchain (n>1).
Each possible pivot value is associated with a particular start point in the link function cycle. |
||||||||||||||||||
| Example
The link functions for a 3chain cycle through: 8p+4, 16p+11, 2p+1, 64p+44, p/2, 32p+16
|
|||||||||||||||||||
| 6.11 | The full calculations for 3chains, 4chains and 5chains are shown in the Appendices. |
| 7.1 | In Appendix 3 the formats of the links in a 4chain are listed. The formats are:
|
||||||||||||||||||
| 7.2 | The proportion of integers that can thus be ignored is:
1/32 + 2/64 + 2/128 + 3/256 + 3/512 + 3/1024 + 2/2048 + 1/4096 + 1/8192 = (256+256+128+96+48+24+8+2+1)/8192 = 819/8192 |
||||||||||||||||||
| 7.3 | The total proportion that can be ignored after considering 1chains, 2chains, 3chains and 4chains is:
1/4 + 3/32 + 63/512 + 819/8192 = (2048+768+1008+819)/8192 = 4643/8192 |
||||||||||||||||||
| 7.4 | This leaves the proportion of integers available to construct 5chains as 3549/8192 = 13/16 of 273/512 | ||||||||||||||||||
| 7.5 | The 4chain at L4 is : 0, 11, 100, 50, 12944, 6472, 414251, . . . . . . |
| 8.1 | Summing the 54 link formats listed in Appendix 4 gives:
1/64+3/128+4/256+6/512+8/1024+8/2048+8/4096+6/8192+5/16384+3/32768+1/65536+1/131072 = (2048+3072+2048+1536+1024+512+256+96+40+12++2+1)/131072 = 10647/131072
|
| 8.2 | The total proportion that can be ignored after considering 1chains, 2chains, 3chains, 4chains and 5chains is:
4643/8192 + 10647/131072 = (74288+10647)/131072 = 84935/131072
|
| 8.3 | This leaves the proportion of integers available to construct 6chains as 46137/131072 = 13/16 of 3549/8192 |
| 8.4 | The 5chain at L5 is : 0, 7, 267, 268, 69036, 17259, 276167, 2209344, . . . . . |
| 9.1 | All the pivots and links in an nchain have the format of pivots of an (n-1)chain.
The proportion of positive integers available to form the chains calculated so far is: 1chains: all positive integers All the pivots and links in an nchain have the format of pivots of an (n-1)chain. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 9.2 | In the Appendices the formats of pivots are shown. If the pivot formats pass Collatz, then so do all the integers in the associated chains. For every pivot format there is a link format which is a sub-set of that format. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Example
Consider the pivot and link formats shown in Appendix 2 for 3chains:
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 9.3 | The calculation of 6chains using the method so far employed would require the construction of a worksheet with 131072 entries in order to define the 162 available pivot formats (this is possible, but distinctly onerous!). This can be avoided by a change of focus if we now concentrate on the calculation of formats available at each level. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Only the pivot formats for a 1chain are available to construct 2chains, that is only integers of format 2i and 4i+3.
The format of the pivot or link stepped up to, depends on the format of i mod 3. Using the step up rules in para 3.1:
These are the pivot formats for 2chains and the only formats available to form 3chains. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 9.4 | Consider the pivots, derived in 9.3, modulus 32:
This leaves 32i+1, 32i+3, 32i+5, 32i+9, 32i+13, 32i+17, 32i+19, 32i+21, 32i+25, 32i+28 and 32i+29. All integers of format 4i+1 are 1chain links, i.e. 32i+(1, 5, 9, 13, 17, 21, 25 or 29) This leaves 32i+3, 32i+19 and 32i+28, i.e. 16i+3 and 32i+28, that are the link formats of 2chains. Hence the pivot formats derived in 9.32, plus the link formats of 1chains and 2chains, include all the positive integers. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 9.5 | The proportion of positive integers available for 3chains is obtained by summing the inverse of the coefficients of m in the 2chain pivot formulae:
1/8 + 1 /32 + 1/16 + 1/16 + 1/4 + 1/ 8 = (4+1+2+22+8+4)/32 = 21/32 This is the value derived in 4.3 above. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 9.6 | Stepping up from the 2chain pivots listed in 9.3 gives the formats of 3chain pivots:
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 9.7 | The proportion of positive integers available for 4chains is obtained by summing the inverse of the coefficients of m n 9.5:
1/8+3/16 +4/32+4/64+3/128+2/256+1/512 = (64+96+64+32+12+4+1)/512 = 273/512 This is the value derived in 5.2 above. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 9.8 | The formats used for 5chains, 6chains and 7chains are calculated in Appendices 6, 7 and 8. This enables the calculation of the the proportion of the positive integers used in these chains. Summarising:
1chains include all positive integers (including 0) 2chains are formed from 3/4 of the positive integers 3chains are formed from 21/32 of the positive integers 4chains are formed from 273/512 of the positive integers 5chains are formed from 3549/8192 of the positive integers 6chains are formed from 46137/131072 of the positive integers 7chains are formed from 599781/2097152 of the positive integers Note that the proportion reduces by a constant factor of 13/16 for 4chains and above. |
Required to prove that the proportion of positive integers used to form the infinite set of nchains is:
( 21/32 ) x ( 13/ 16 )(n-3)
| 10.1 | Each pivot has format 2k.i +c, where i is any positive integer including zero and c is a constant less than 2k.
In order to step up from a pivot, it has to be converted to a format of the form 3i+d, where d= 0,1 or 2 (see 3.1). Since every i has one of the three formats 3m, 3m+1 or 3m+2, this is effected by substituting these three formats for i. Thus there are three pivot formats at L(r+1) for every pivot format at L(r); this is why the cycle of equations defining the formats at L(r+1) is three times as long as the cycle for L(r). |
|||
| 10.2 | In order to determine all the possible results of stepping up from a pivot of format 2k.i+c, it is necessary to consider all the possible formats obtained by the values that k, i and c may take :
k may be odd or even Thus there are 2 x 3 x 6 = 36 possible formats to consider. The relevant calculations are listed in Appendix 9. |
|||
| 10.3 | In Appendix 9 the symbols o and e are used solely to indicate that the relevant term is either odd or even, they do not represent an actual value.
The re-formatting between columns uses the fact that odd powers of 2 can always be expressed as 3e+2 for some even integer e, and even powers of 2 can always be expressed as 3o+1 for some odd integer o. Thus 22t is replaced by 3o+1 and 22t+1 is replaced by 3e+2 when appropriate. |
|||
| 10.4 | From the final formats obtained, as shown in the table in Appendix 9 , it is apparent that:
Of each set of three L(r+1) pivots derived from a pivots at L(r) with the same values for k and c, two are even and one is odd. There are, effectively, only two patterns of three derived formulae as far as coefficients are concerned. If the coefficient of i at Lr is of form 2k, then the three coefficients at L(r+1) are either of form:
When c is odd, i.e. 3o, 3o+2 or 3e+1, the L(r+1) coefficients are 2k, 2k+1 and 2k+2. When c is even, i.e. 3o+1, 3e, or 3e+2, the L(r+1) coefficients are 2k+2, 2k+3 and 2k+4. The even pivots at L(r+1) have coefficients: 2k, 2k+2 or 2k+4. The odd pivots at L(r+1) have coefficients: 2k+1 or 2k+3. |
|||
| 10.5 | Consider the pattern of odd and even pivots produced by stepping up from pivots with coefficient 2k.
Even pivots at Lr give even pivots at L(r+1) that have coefficients 2k+2 and 2k+4, and these coefficients define 1/2k+2 + 1/2k+4 = 5/16 as many positive integers as are defined by the 2k pivot at Lr. Even pivots at Lr give odd pivots at L(r+1) that have coefficient 2k+3, and these coefficients define 1/8 as many positive integers as are defined by the 2k pivot at Lr. Odd pivots at Lr give even pivots at L(r+1) that have coefficients 2k and 2k+2, and these coefficients define 1/2k + 1/ 2k+2 = 5/4 as many positive integers as are defined by the 2k pivot at Lr. Odd pivots at Lr give odd pivots at L(r+1) that have coefficient 2k+1, and these coefficients define 1/2 as many positive integers as are defined by the 2k pivot at Lr. |
|||
| 10.6 | From Section 2 above, there are two pivot formats at L1 : 2i and 4i+3.
The proportion of positive integers which are pivots at L1 is 3/4 and 2chains are constructed using these. The ratio of even to odd pivots at L1 is 2:1 To simplify the presentation of the following, let the proportion of even pivots at L1 be 2a and the proportion of odd pivots be a. Then from 10.4: pivots at L1 produce 2a x 5/16 + a x 5/4 = 15a / 8 even pivots at L2 The total of pivots at L1 is 2a + a = 3a ; the total at L2 is 21a/8 ; 21/8 is 7/8 of 3 The proportion of positive integers which are pivots at L1 is 3/4, thus the proportion of positive integers which are pivots at L2 and which are used to construct 3chains is 3/4 x 7/8 = 21 / 32, as given in section 9.7. |
|||
| 10.7 | From 10.5, and using a similar argument, the ratio of even to odd pivots at L2 is 15:6 = 5:2
pivots at L2 produce 5a x 5/16 + 2a x 5/4 = 65a / 16 even pivots at L3 The total at L2 is 5a + 2a = 7a ; the total at L3 is 91/16 x a ; 91/16 is 13/16 of 7 The proportion of positive integers which are pivots at L2 is 21/32, thus the proportion of positive integers which are pivots at L32 and which are used to construct 3chains is 21/32 x 13/16 = 273 / 512, as given in section 9.7. |
|||
| 10.8 | Since 65/16 : 26/16 = 5 : 2 , the relative proportions of odd and even pivots will remain constant for all nchains and the ratio of 13/16 will apply to all Lr to L(r+1) pivot step-ups.
Q.E.D. |