A Unified Approach to the 3n+1 and 3n-1 Problems

The 3n+1 problem appears to have been first posed by Collatz in 1937.  In this problem, a sequence is generated starting with an initial natural number n.  The rule for generating the next natural number in the sequence is; if n is even, the next natural number in the sequence is n/2, or if n is odd, the next natural number in the sequence is 3n+1.  For example, if the initial value of n is 17, the sequence generated is {17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, ...}.  If the natural number 4 is encountered in the sequence, the sequence starts repeating ({4, 2, 1} is generated over and over).  There are three possibilities; (1) the natural number 4 is encountered in the sequence, (2) the sequence starts repeating, but for a different cycle than {4, 2, 1}, or (3) the sequence doesn't repeat (in which case the natural numbers generated in the sequence have to keep getting larger and larger).  The 3n+1 conjecture states that only the first possibility can occur.  Let c be an odd integer greater than or equal to -1 that is not divisible by 3.  The next number in the 3n+c sequence is defined to be 3n+c if n is odd, or n/2 if n is even (the next number in the sequence is always a natural number).  The sequence repeats for {4c, 2c, c} if c>-1 or {2, 1} if c=-1.  In this more general sequence, there are usually cycles other than {4c, 2c, c}.  For a given c value, there appear to be few (if any) non-trivial cycles.  When c is composite, some of the cycles that occur are essentially no different from the cycles that occur for a factor of c (the elements of the cycle are just a common multiple of the elements of the cycle for the factor of c).  Also, some cycles for a given c value appear to be interrelated; they have the same lengths (number of elements) and approximately the same dynamic range of elements.  Counting these types of cycles as redundant, a histogram of the apparent number of cycles for c values less than or equal to 151 is;

This data indicates that whether there are any cycles for a given c value is a matter of chance.  However, cycles can be classified into three different types in a natural way and there is some evidence that it can be proved that cycles of one of these types can't occur for c=1 or -1.  When c=-1, there are two known cycles other than (2, 1); the cycle (20, 10, 5, 14, 7) and the cycle (68, 34, 17, 50, 25, 74, 37, 110, 55, 164, 82, 41, 122, 61, 182, 91, 272, 136).  A criterion for classifying the cycle (20, 10, 5, 14, 7) with the cycle (2, 1) will be given.  Another type of cycle is one where no element is divisible by 8 (and the cycle isn't a "trivial" cycle) and the remaining type of cycle is one where at least one element of the cycle is divisible by 8.  Evidence will be presented that only trivial cycles and cycles where an element is divisible by 8 can occur when c=1 or -1.  No proofs are given in this article (all the "results" are empirically derived).  Other than the context in which statements are made, the empirically derived propositions are not specifically identified (usually) since, other than references to articles in the 3n+1 problem literature, the article consists almost entirely of empirically derived propositions.

Topics discussed are; (1) a restructured Collatz graph, (2) an alternate definition of the 3n+c sequence, (3) a probabilistic argument that the 3n+c sequence is bounded, (4) the formula s=(Xa-cZ)/Y for expressing the current sequence value (s) in terms of a subsequent sequence value (a), (5) least-residue trees (sub-trees of the Collatz graph where the sequence vectors of limbs are mostly 1-2 sequence vectors [a sequence vector is the array of the number of even elements between the odd elements of a sequence]), (6) different types of cycles in least-residue trees, (7) limit relationships in least-residue trees and a Diophantine equation associated with the formula s=(Xa-cZ)/Y, (8) R. E. Crandall's proof that cycles with small lengths cannot occur (for c=1), (9) the probability of occurrence of a certain type of cycle in least-residue trees, (10) another kind of least-residue tree, (11) m-cycles (cycles in the Collatz sequence having m local minima), (12) the formula M_l,n=∑(]jn/l[ - ](j-1)n/l[ )2^j-13^n-]jn/l[ for computing the minimum element in a cycle (where the summation is from j=1 to l, the reversed brackets denote the ceiling function, n is the number of odd elements in the cycle, and l is the length of the cycle [where the element in the sequence after an odd element i is defined to be (3i+1)/2 instead of 3i+1]), arbitrarily long 3n+1 and 3n-1 sequences that are "almost" cycles, and probability distributions pertaining to the minima in cycles having a prime number of odd elements, (13) common properties of least-residue trees for the 3n+1 and 3n-1 sequences (indicating that the sequences are essentially the same), (14) an outline of the approach to the 3n+1 and 3n-1 problems, (15) properties of cycles in the 3n+c sequence,  (16) general 3n+c sequences under certain "order" constraints having properties in common with least-residue trees, and (17) a generalization of 1-2 sequence vectors.  The general theme of the article is the importance of 1-2 sequence vectors and the order of sequences (where a natural number of the form 3∙2^k is greater than every element of the sequence).  

A Restructured Collatz Graph

The Collatz graph is a tree-like structure that shows how the sequence element 1 can be arrived at starting from different initial n values.  When n is even and n-1 is divisible by 3, there is a node in the graph where the previous elements in the sequence are 2n and (n-1)/3.  For example, in the Collatz graph, two limbs ending in 32 and 5 converge to form a limb starting at 16.  In the restructured Collatz graph, 5 is considered to be a continuation of the limb segment starting with 16.  In general, (n-1)/3 is considered to be a continuation of the limb segment at such nodes.  The limbs in the restructured Collatz graph are then;

Each limb other than (4, 2, 1) contains exactly one odd element divisible by 3.  Let j denote the odd natural number that is divisible by 3.  The natural numbers to the right of j are not divisible by 3 (since 3 does not divide 3j+1, (3j+1)/2, ...).  The natural numbers to the left of j must be of the form 2ⁱj where i is a natural number (no natural number can attach to this part of the limb since 3 does not divide 2j-1, 4j-1, 8j-1, ...).  (The limbs listed above [starting with the second limb] contain 3, 9, 15, and 21 respectively.  The second limb attaches to the first limb, the third and fifth limbs attach to the second limb, and the fourth limb attaches to the third limb.)  Note that other than the limb {4, 2, 1}, the next-to-last element in a limb is divisible by 8 and that no natural number to the right of the odd natural number divisible by 3 and before the next-to-last natural number is divisible by 8.

An Alternate Definition of the 3n+c Sequence

The 3n+c sequence can be defined by the recurrence operation [(3/2)^h(n+c)-c]/2→n, 2^h divides n+c, 2^h+1 does not divide n+c.  Each iteration of the recurrence operation will be referred to as a "jump".  If n is odd and 2² does not divide n+c, then the sequence {n, 3n+c, (3n+c)/2=(3/2)(n+c)-c, ...} is generated where every other element of the sequence up to (3/2)(n+c)-c is odd.  Similarly, if n is odd and 2² divides n+c, 2³ does not divide n+c, then the sequence {n, 3n+c, (3n+c)/2, 3[(3n+c)/2]+c, [3[(3n+c)/2]+c]/2=(3/2)²(n+c)-c, ...} is generated where every other element of the sequence up to (3/2)²(n+c)-c is odd.  In general, if 2^h divides n+c, 2^h+1 does not divide n+c, then the first element in the sequence that is divisible by 4 is the one just before (3/2)^h(n+c)-c.  If [(3/2)^h(n+c)-c]/2 is even, then the first element in the sequence that is divisible by 8 has been found.  Each limb of the restructured Collatz graph other than {4, 2, 1} consists of a series of jumps, the last jump ending in an even natural number (which connects the limb to the rest of the tree).  The question of whether the 3n+1 sequence (or the 3n+c sequence) is bounded then reduces to the question of whether there are any jumps ending in an even natural number.  The distribution of the number of jumps (denoted by i) before an even natural number is reached for the 1000000 sequences starting with 3, 9, 15, ..., 5999997 is;

The probability that i iterations are required is about (1/2)ⁱ.  Even though the probability that the sequence is unbounded is effectively 0, it's unlikely that this part of the 3n+1 conjecture is provable.  The corresponding distribution of the h values (out of a total of 1999939) is;

The remaining step is to find the smallest order for which a given e value occurs.  Another property of least-residue trees is;

(1)  One-half of the limbs in S consist of 1 element, about 1/3 of the limbs in S consist of two elements, about 1/12 of the limbs in S consist of four elements, about 1/72 of the limbs in S consist of five elements, about 1/36 of the limbs in S consist of seven elements, about 5/576 of the limbs in S consist of nine elements, about 7/864 of the limbs in S consist of ten elements, about 77/7776 of the limbs in S consist of twelve elements, about 13/15552 of the limbs in S consist of fourteen elements, and about 815/186624 of the limbs in S consist of fifteen elements.  The denominators of these fractions are a power of two times a power of three.  Denote a fraction by f.  The number of limbs in S (for an order of 3∙2^k, k>2) is 2^k-1.  Denote the number of limbs in S of a given length by m.  For limb lengths of 2, 4, or 5, 0≤[2^k-1f]+1-m≤1, for limb lengths of  7, 9, or 10, -1≤[2^k-1f]+1-m≤2, and for limb lengths of 12, 14, or 15, -2≤[2^k-1f]+1-m≤3, where the brackets denote the greatest integer function.  About 2/3 of  the limbs in S with a length of 1 are alive, about 1/2 of the limbs in S with a length of 2 are alive, about 1/2 of the limbs in S with a length of 4 are alive, about 1/6 of the limbs in S with a length of 7 are alive, about 1/3 of the limbs in S with a length of 9 are alive, about 25/154 of the limbs in S with a length of 12 are alive, and about 1/4 of the limbs in S with a length of 14 are alive.  Denote one of these fractions by f' and denote the number of live limbs in S of a given length by m'.  For limb lengths of 1, 0=[2^k-1ff']-m', for limb lengths of 2, 4, 7, or 9, 0≤[2^k-1ff']-m'≤1, and for limb lengths of 12 or 14, -1≤[2^k-1ff']-m'≤2.  For longer limb lengths, the portion of the limbs in S is similarly fixed.  The a+b values of the live limbs in S with lengths of 2, 4, 7, 9, 12, 14, ..., are 1, 2, 3, 4, 5, 6, ...., respectively.  For every value of j, j=1, 2, 3, ..., there is a relatively small odd natural number g, a relatively small natural number h, and a natural number i approximately equal to j such that 2^k-1(g/(2^h 3ⁱ)) closely approximates the number of live limbs in S with the corresponding length.  For live limbs in S with lengths of 17, 20, 22, 25, 27, 30, and 33, the g values are 233, 695, 6349, 3791, 2831, 3425, and 7359 respectively, the h values are 11, 11, 10, 12, 13, 8, and 13 respectively, and the i values are 5, 8, 10, 9, 9, 12,  and 13 respectively.  (These values aren't unique; similar g and h values can be found when i is set to j.)  For some limb lengths, live limbs associated with certain sequence vectors occur more frequently than live limbs associated with other sequence vectors.  For example, for a limb length of 12, there is a group of live limbs in S associated with the sequence vector giving the largest e value where the probability of occurrence is 17/(2⁶∙3⁵) and there is a group of live limbs in S associated with the sequence vector giving the smallest e value where the probability of occurrence is 1/(2³∙3⁵) (the sum of these probabilities is 25/(2⁶∙3⁵)).  For a limb length of 17, there is one group of live limbs in S associated with two sequence vectors (one of which is the sequence vector giving the largest e value) where the probability of occurrence is 1/(2¹⁰∙3¹), another group of live limbs in S associated with two other sequence vectors (one of which is the sequence vector giving the smallest e value) where the probability of occurrence is 13/(2¹⁰∙3⁵), and another group of live limbs in S associated with the remaining sequence vector where the probability of occurrence is 5/(2¹¹∙3³) (the sum of these probabilities is 233/(2¹¹∙3⁵)).  For a limb length of 22, the probabilities of occurrence for live limbs in S in the different groups are 1147/(2⁸∙3¹⁰), 5/(2¹³∙3³), and 13/(2¹³∙3⁵).  For a limb length of 25, the probabilities of occurrence for live limbs in S in the different groups are 1237/(2¹¹∙3⁹), 853/(2¹²∙3⁹), and 29/(2⁸∙3⁹).  For a limb length of 27, the probabilities of occurrence for live limbs in S in the different groups are 2567/(2¹³∙3⁹) and 11/(2¹⁰∙3⁸).  For a limb length of 30, the probabilities of occurrence for live limbs in S in the different groups are 131/(2¹²∙3⁷), 107/(2¹²∙3⁸), 865/(2⁹∙3¹²), 215/(2⁹∙3¹¹), and 185/(2¹⁰∙3¹¹).  For limb lengths of 14, 20, or 33, there is only one group of live limbs in S associated with the different sequence vectors.  The differences between the estimated number of live limbs in S using these probabilities (where rounding is done) and the actual number of live limbs in S for different orders and limb lengths (denoted by L) when c=1 are;

        k=12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   27   28   29   30   31   32   33
L=2       0     1     0     1     0     1     0     1     0     1     0     1     0     1     0     1     0     1     0     1     0     1
     4       0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     7       0     0     0     0     1   -1     0     0     0     0     0     0     0    -1    1    -1     0     0     0     0     0     0
     9       0     0     1     0     0     1     0     1     0     0     0     0     1     0     0     1     0     0     0     0     1     0
   12       0     0     0     0     0   -1     1   -1     1    -1   -1     0     0     0    -1    -1    0     0      0     0     0     0
   14      -1    0     0   -1     0     0    -1     0     0     0     0     0     0     0     0     0   -1     0     -1     0    -1    0
   17       0     1     1     1     0     1     0     1   -1     1     0     1     0     2     1     1     0     1     0     0     1     0
   20       0   -1     0    -1     1   -1     1     0     1    -1     1   -1     1     0     1    -1     0   -1     1    -1     1   -1
   22       0   -1     1     0    -3   -1    -2    0    -1    -1   -1   -2    -3   -2    -1   -3    -2     0     1     1     1     2
   25       0     0     0     1     2     1   -2     3     0     5     4     4     1     2     0     5     0    -1   -4     1     1     6
   27       0     0     0     0     1   -1     1     2     3    -1    0     4    -1     1     2     1     5     2     1     1     0     0
   30       0     0     0     0     0     1     3   -3     1     0    -2   -2    -1    1    -2    -2   -2     1     0     1     1     4
   33       0     0     0     0     0     0     0    0    -1     1    -1    1     0    -4     1     0     2    -3     2   -5      0   -7     
 
For every order and limb length, the difference between the number of live limbs in S associated with one sequence vector in a group and the number of live limbs in S associated with another sequence vector in the group is at most 1.  (This appears to still be true for live limbs in A, B, C, or D or any other similarly constructed subset of S where the last elements in the limbs are congruent to an odd natural number j modulo 2ⁱ, j<2ⁱ , i<k).

The above property can be used to estimate the smallest order for which a live limb in S with a given length occurs.  For example, assuming that the upper bound of the difference between the estimated and actual number of live limbs with a length of 25 (where the difference is given by the formula [2^k-1(3791/(2¹²∙3⁹))+0.5]-m') is 6 (a somewhat dubious proposition) gives m'≥1 when k=19 (when c=1, the smallest order for which a live limb with a length of 25 occurs is 3∙2¹⁷).  The n value for a limb length of 25 is 6487 and the largest e value is 811694, so n(order/2) is much greater than ce, c>0, n>0, when order=3∙2¹⁹.  The difficulty with this approach is determining the upper bound of the difference between the estimated and actual number of live limbs.

Another miscellaneous property of least-residue trees (of importance to the recursive algorithm for generating a and b values) is ;

(2) For live limbs in S with lengths of 4, 9, 14, 22, 27, ...(where the b values are 2, 3, 4, 5, 6, ... respectively and the b values for the next smaller limb lengths are 1, 2, 3, 4, 5, ... respectively), the upper bound of the maximum y value to order ratio associated with the sequence vector giving the largest e value is (3/4)X/Y.  (For large orders, the maximum y value to order ratio is approximately equal to the upper bound, and as the order decreases, the maximum y value to order ratio gradually decreases [but not monotonically].)  For some limb lengths, the upper bound of the maximum y value to order ratio associated with a group of sequence vectors is different from the upper bounds associated with other groups of sequence vectors.   (These groups of sequence vectors are the same as those giving different frequencies of occurrence of live limbs.)  For example, for a live limb with a length of 12, the upper bound of the maximum y value to order ratio associated with the sequence vector giving the largest e value is 2/3 ((3/4)X/Y for a live limb with a length of 4) and the upper bound of the maximum y value to order ratio associated with the sequence vector giving the smallest e value is 16/27 ((3/4)X/Y for a live limb with a length of 9).  For a live limb with a length of 17, the upper bound of the maximum y value to order ratio associated with two sequence vectors (one of which is the sequence vector giving the largest e value) is 2/3 ((3/4)X/Y for a live limb with a length of 4), the upper bound of the maximum y value to order ratio associated with two other sequence vectors (one of which is the sequence vector giving the smallest e value) is 128/243 ((3/4)X/Y for a live limb with a length of 14), and the upper bound of the maximum y value to order ratio associated with the remaining sequence vector is 16/27 ((3/4)X/Y for a live limb with a length of 9).  The upper bound of the maximum y value to order ratio associated with any sequence vector of a live limb of a given length is one of 2/3, 16/27, 128/243, 4096/6561, 32768/59049, ....     

When c>1, there are relatively few limbs in S having lengths other than 1, 2, 4, 5, 7, 9, 10, 12, 14, 15, 17, 18, 20, 22, 23, 25, ....  When k is sufficiently large for a given limb length and c value greater than 1, the limbs in S have many of the above properties.

More on Cycles in "Odd" Paths

In this section, c is restricted to being 1 or -1.  For a sufficiently large k, the elements of an odd path are in a limb of a least-residue tree (assuming there is a jump in the odd path that ends in an even natural number).  Limbs in G are not considered in this section; more evidence that a limb in S cannot attach to itself at its beginning is presented.

When c=1, the x/y values of limbs in S approach their limits from below, so x values for limb lengths where the limits are negative (1, 4, 9, 14, 17, 22, ...) can never reach 0.  Similarly, when c=-1, the x/y values of limbs in S approach their limits from above, so x values for limb lengths where the limits are positive (2, 5, 7, 10, 12, 15, 18, 20, 23, 25, ...) can never reach 0.  The following property of least-residue trees (applicable for general c values) precludes x=0 for more limb lengths;

(3)  If a limb in S is not dead and has more than one element, then the second element is odd.

Limbs in S having more than one element satisfy the Diophantine equation n(y/2)-(d/2)x=c(e/2) where d/2 is even.  By the above property, y/2 is odd when the limb is not dead so that e/2 must be odd.  Limbs with lengths of 5, 10, 15, 18, 23, ... (where the e values are divisible by 4) must then be dead.

These limit relationships and the Diophantine equation n(y/2)-(d/2)x=c(e/2) then preclude a limb in S from attaching to itself at its beginning for about 2/3 of the possible limb lengths.

Suppose i is the last element of a two-element limb in S.  A two-element limb in S cannot attach to itself at its beginning since (3i+1)/2 equals 2i only if i=1 (when c=1) or (3i-1)/2 equals 2i only if i=-1 (when c=-1).  Suppose i is the last element of a four-element limb in S.  In a four-element limb in S, the first and third elements are even and the second and fourth elements are odd.  A four-element limb in S cannot attach to itself at its beginning since (3i+1)/2 equals 2(2i-1)/3 only if i=-7 (when c=1) or (3i-1)/2 equals 2(2i+1)/3 only if i=7 (when c=-1).  Usually, a limb in A cannot attach to itself at its beginning since the limb is either dead, a one-element limb, a two-element limb, or a four-element limb.  Usually, limbs in S do not attach to other limbs of equal length.  Two-element, four-element, seven-element, twelve-element, seventeen-element, twenty-element, twenty-five element, and other longer length limbs in A sometimes attach to other limbs of equal length in A, B, C, or D.  A seven-element limb in A that attaches to a limb of equal length in A, B, C, or D is dead.  For c=1 and k=18, the only limb in A that is not dead, does not consist of two or four elements, and that attaches to another limb in A with the same length is (484034, 306305).  This limb has a length of 12 and attaches to the limb (459458, 290753).  For c=1 and k=20, the only limb in A that is not dead, does not consist of two or four elements, and that attaches to another limb in A with the same length is (2056898, 1301633).  This limb has a length of 12 and attaches to the limb (1952450, 1235537).  If c=-1, 11, 13, 25, 29, 31, 41, 43, 47, 59, 61, 73, 77, 79, 89, 91, or 95 (or larger unspecified values), let A_o denote the limbs in A where the last element of the limb divided by 8 is even (and let A_e denote the remaining limbs in A), or if c=1, 5, 7, 17, 19, 23, 25, 35, 37, 49, 53, 55, 65, 67, 71, 83, 85, or 97 (or larger unspecified values), let A_o denote the limbs in A where the last element of the limb divided by 8 is odd (and let A_e denote the remaining limbs in A).  Another property of least-residue trees (valid for general c values) that reduces the probability of a limb in S from attaching to itself at its beginning is;

(4)  A limb in A_o attaches to a two-element or four-element limb in A, B, C, or D.

For c=1 and k=21, the only limb in A_e that is not dead, does not consist of two or four elements, and that attaches to another limb in A_e with the same length is (3629762, 2296961).  This limb has a length of 12 and attaches to the limb (3445442, 2180321).

There is no known method for determining the probability that a limb in S attaches to itself at its beginning, but by using special-case properties such as the above, it can be shown that this probability is small.  (Of course, if the evidence in the previous section is accepted, this probability is zero.)

Another Kind of Least-Residue Tree

In this section, c is restricted to being 1 or -1.  Consider a tree where the order is of the form 3∙2^k and no element of a limb is greater than or equal to the order or divisible by 3.  The first element of a limb must be even and greater than the order divided by 2, the last element of a limb must be odd and greater than the order divided by 3, and every limb must contain at least one element that is divisible by 8.  (As for a limb in S of a least-residue tree, a limb cannot attach to its interior or the interior of another limb.)  The possible lengths of these limbs are 12, 14, 15, 17, 18, 20, 22, 23, ....  The lengths of the limbs are the same as those for a limb in S of a least-residue tree (except there are no lengths of 1, 2, 4, 5, 7, or 9) and the X and Y values are the same.  Denote the first element of a limb by y, the last element of a limb by i, (3i+c)/2 by z, and y-z by x.  As before, x and y satisfy the Diophantine equation ny-dx=ce where n=X-Y, d=X, and the e values are fixed for a given limb length.  Some e values are;

length=12, e=1202
length=14, e=3862
length=15, e=7724, 5780
length=17, e=24196, 22738, 18850, 18364, 16906, 16258, 14530, 14476, 13378, 13018
length=18, e=48392, 45476, 37700, 36728, 33812, 32516, 29060, 28952, 26756, 26036

For a given limb length, the largest e value is larger than the largest e value for a live limb in S of a least-residue tree (when not all of the limbs are dead for that length) and the smallest e value (when there is more than one e value) is smaller than the largest e value for a live limb in S of a least-residue tree (when not all the limbs are dead for that length).  The lengths of the sequence vectors for limb lengths of 12, 14, 15, 17, 18, 20, 22, and 23 are 5, 6, 6, 7, 7, 8, 9, and 9 respectively.  The largest elements in the sequence vectors for limb lengths of 12, 14, 15, 17, 18, 20, 22, and 23 are 3, 3, 3, 4, 4, 5, 5, and 5 respectively.  For some limb lengths, limbs associated with certain sequence vectors occur more frequently than limbs associated with other sequence vectors.  For example, for a limb length of 17, the number of  limbs associated with two sequence vectors is about [2^k-1(295/(2⁹∙3⁶))+0.5], the number of limbs associated with five other sequence vectors is about [2^k-1(5/(2¹⁰∙3¹))+0.5], the number of limbs associated with two other sequence vectors is about [2^k-1(5/(2⁹∙3³))+0.5], and the number of limbs associated with the remaining sequence vector is about [2^k-1(13/(2¹⁰∙3⁵))+0.5].  For every order and limb length, the difference between the number of limbs associated with one sequence vector in a group and the number of limbs associated with another sequence vector in the group is at most 2.  For some limb lengths, the upper bound of the maximum y value to order ratio associated with a group of sequence vectors is different from the upper bounds associated with other groups of sequence vectors.  (These groups of sequence vectors are the same as those giving different frequencies of occurrence of limbs.)  For example, for a limb length of 17, the upper bound of the maximum y value to order ratio associated with two sequence vectors is 512/729, the upper bound of the maximum y value to order ratio associated with five other sequence vectors is 2/3, the upper bound of the maximum y value to order ratio associated with two other sequence vectors is 16/27, and the upper bound of the maximum y value to order ratio associated with the remaining sequence vector is 128/243.  For limb lengths of 12, 14, 15, 17, 18, 20, 22, and 23, the number of limbs can be approximated by [2^k-1f+0.5] where f equals 17/(2⁵∙3⁵), 13/(2⁸∙3⁵), 353/(2⁸∙3⁶), 1057/(2⁹∙3⁶), 695/(2⁹∙3⁷), 6733/(2¹⁰∙3⁷), 9817/(2¹³∙3⁶), and 56915/(2¹⁴∙3⁷) respectively.  The number of limbs in one of these trees is approximately equal to the order divided by 144.

M-Cycles

In 2005, Simons and de Weger⁴ gave bounds for Λ=(K+L) log 2 - K log 3 (where K is the total number of odd elements and L is the total number of even elements in the m-cycle).  A corollary proved is 0<Λ<m/x_min.  For a limb in S of a least-residue tree (with a length of 3a+2b) to attach to itself at its beginning, this gives x_min<(a+1)/((2a+b+1) log 2 - (a+b) log 3).  This upper bound for the minimum is about twice as large as the actual minimum.

The Minimum in a Collatz Cycle

In 1997, Halbeisen and Hungerbuhler⁵ used the formula M_l,n=∑(]jn/l[ -](j-1)n/l[ )2^j-13^n-]jn/l[  where the summation is from j=1 to l to find the minimum in a Collatz cycle of length l (the minimum is M_l,n/(2^l-3ⁿ)).  For a limb in S of a least-residue tree (with a length of 3a+2b) to attach to itself at its beginning, l=2a+b+1 and n=a+b.  The 1-2 sequence vector corresponding to the smallest e value or a larger e value can be constructed from ]in/l[ - ](i-1)n/l[ (for 1≤i≤l) by rotating (if necessary) the vector and converting (1, 0)'s to 2's.  (There are ]n/2[-0, 1, or 2 (1, 1)'s in the parity vector.  The parity vector must be rotated so that a (1, 1) is at the beginning of the vector to match (mostly) the 1-2 sequence vector corresponding to the smallest e value.  The last element of the sequence vector will be a 2 and must be changed to a 1 to match the sequence vector corresponding to the smallest e value.  Note that the first element of a sequence vector just indicates that the first element of the limb is even [and not that there is an odd natural number in the 3n+c sequence immediately preceding it].  If a cycle were formed by a limb attaching to itself at its beginning, the first element of the sequence vector would be changed to a 2 [and the 2 would indicate that there were 2 even elements between odd elements in the sequence].)  For example, for a limb length of 20, the parity vector must be rotated right by 5 positions for the resulting sequence vector to match the sequence vector corresponding to the smallest e value.  (The possible right-rotates for a limb length of 20 are 0, 5, and 10.  In general, the difference between successive right-rotates is 3 or 5.)  The required right-rotates of the parity vector for limb lengths of 2, 4, 7, 9, 12, 14, 17, 20, 22, 25, 27, 30, 33, 38, and 43  are 0, 0, 0, 0, 0, 0, 0, 5, 11, 0, 11, 0, 5, 0, and 0 respectively.  If the un-rotated parity vector gives an e value for a limb in S, then the e value is the smallest for a limb in S and all the possible right-rotates give e values for limbs in S.  For limb lengths of 20, 22, 27, 33, 35, 40, 45, 48, 51, 53, and 56, the un-rotated parity vector gives e values too small to be a limb in S.  In these cases, a right-rotate of 5 gives an e value (usually not the smallest) for a limb in S.  No limb in S having a sequence vector corresponding to one of these "broken" cycles can attach to itself at its beginning (unless some other rotation of the parity vector gives the parity vector corresponding to the "broken" cycle).  A rotation of the parity vector so that a (1, 0) is at the beginning of the vector does not correspond to a live limb in S since the second element of a live limb in S is odd.  A rotation of the parity vector so that a (0, 1) is at the beginning of the vector corresponds to a live limb in S, but except for limb lengths of 7, 12, 17, 30, 43, ..., the e values given are too small.  (The resulting sequence vectors for limb lengths of 7, 12, 17, 30, and 43 are (1, 2, 1), (1, 2, 1, 2, 1), (1, 2, 1, 2, 1, 2, 1), (1, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 1), and (1, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 1) respectively.  These sequence vectors have bilateral symmetry and are the sequence vectors corresponding to the smallest e values.)  For most limb lengths, no live limb in S can attach to itself at its beginning.  (Similarly, a limb in the second kind of least-residue tree [where at least one element is divisible by 8] having a length of 12, 14, 17, 20, 22, 25, 27, 30, ..., cannot attach to itself at its beginning since the n and l values are the same as those for a limb in S having the same length [although there are fewer local minima for the second kind of least-residue tree].)  In the sequence vector corresponding to the smallest e value, there are no (2, 2, 2)'s and, except for the last two sequence values for limb lengths of 4, 9, 14, 22, 27, 35, 40, 45, 53, ..., no (1, 1)'s.  The number of sequence values between a pair of adjacent 2's and the next pair of adjacent 2's is always odd.  The last odd element in a limb is the largest.  The gain from one odd element in a limb to the second odd element following it is by about a factor of 9/8 except when a pair of adjacent 2's in the sequence vector is encountered, in which case the loss is by about a factor of 9/16, or when a pair of adjacent 1's in the sequence vector is encountered, in which case the gain is by about a factor of 9/4.  For example, the odd elements in a limb in S corresponding to the smallest e value for a length of 33 and an order of 3∙2³³ are 0x1ffff62a1, 0x17fff89f9, 0x11fffa77b, 0x1afff7b39, 0x143ff9c6b, 0x1e5ff6aa1, 0x16c7f8ff9, 0x1115fabfb, 0x19a0f81f9, 0x1338ba17b, 0x1cd517239, 0x159fd15ab, and 0x206fba081.  (The sequence vector is 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 1.)  The gains and losses for the first, third, fifth, ... odd elements are 9/16, 9/8, 9/8, 9/8, 9/8, and 9/8 respectively.  The gains and losses for the second, fourth, sixth, ... odd elements are 9/8, 9/8, 9/16, 9/8, and 9/8 respectively.  The odd elements in a limb in S corresponding to the smallest e value for a length of 35 and an order of 3∙2³³ are 0x1c7c26aa1, 0x155d1cff9, 0x1005d5bfb, 0x1808c09f9, 0x12069077b, 0x1b09d8b39, 0x14476286b, 0x1e6b13ca1, 0x16d04ed79, 0x111c3b21b, 0x19aa58b29, 0x133fc285f, 0x1cdfa3c8f, and 0x2b4f75ad7.  (The sequence vector is 1, 2, 2, 1, 2, 1, 2, 1, 2, 2, 1, 2, 1, 1.)  The gains and losses for the first, third, fifth, ... odd elements are 9/16, 9/8, 9/8, 9/8, 9/8, and 9/8 respectively.  The gains and losses for the second, fourth, sixth, ... odd elements are 9/8, 9/8, 9/8, 9/16, 9/8, and 9/4.

The minima where n is a multiple of a natural number d increase and decrease in a regular fashion.  For example, the truncated minima for n=5, 10, 15, ..., 65 are 24, 24, 24, 24, 24, -19, -27, -35, -48, -70 -111, -219, and -1004 respectively, the truncated minima for n=70, 75, 80, ..., 130 are 463, 204, 137, 108, 88, -58, -70, -86, -111, -147, -219, -361, and -1004 respectively, and the truncated minima for n =135, 140, 145, ..., 195 are 1561, 463, 281, 204, 162, 137, -111, -133, -165, -219, -295, -462, and -1004 respectively.  In general, the minima for d =5 have a roughly saw-tooth shaped curve with a period of 13 or 14.  The longest periods (and the largest minima) occur when d is of the form 12k-7, k=1, 2, 3, ....  For example, the periods for d=7, 12, 17, 19, 22, 26, 27, and 29 are 10 or 11, 51 or 52, 17 or 18, 8 or 9, 7 or 8, 4 or 5, 4 or 5, and 27 or 28 respectively.  The "superposition" of these quasi-periodic "waves" is of importance in determining the largest minima.  For example, a large truncated minimum (for c=-1) of -3664765 occurs when n=665=5∙7∙19.

Note that when l=3 and n=2, using the formula for M_l,n gives the minimum for the cycle 20, 10, 5, 14, and 7 (for c=-1) and when  l=6 and n=4, using the formula gives the minimum for the cycle 20, 10, 5, 14, 7, 20, 10, 5, 14, and 7.  This suggests that there cannot be a cycle when l=3k and n=2k, k>1, other than the repeated cycle for k=1.  Cycles where n is prime are then of interest.  The periods for prime n values less than 41346 and of the form 12k-1, k=1, 2, 3, ..., are 17, 24, 24, 18, 18, 22, 18, 15, 19, 19, ..., 17, 14, 16, 13, 13, 13, 16, 17, 15, and 13.  The difference in n values between successive peaks in minima values appears to be fairly constant (usually 612, but as small as 528 or as large as 696).  Similar results apply for prime n values of the form 12k-5, 12k-7, or 12k+1.  Let x denote one-twelveth of the difference in n values between successive peaks in minima values.  For prime n values less than 2000000, the x values range from 31 to 107, the distribution of x values for 31, 32, 33, ..., 71 is 2, 5, 3, 11, 14, 22, 29, 29, 46, 98, 110, 156, 171, 228, 394, 418, 563, 697, 1047, 1578, 1561, 1367, 953, 819, 823, 477, 333, 270, 190, 175, 102, 70, 70, 40, 46, 24, 12, 10, 6, 9, and 3 respectively (a population centered around x=51), and the distribution of x values for 91, 92, 93, ..., 107 is 1, 1, 0, 0, 0, 0, 1, 0, 3, 3, 3, 1, 3, 4, 3, 0, and 1 respectively (a second population centered around x=102) .  A Weibull probability plot of  the first population is;



For prime n values less than 4000000, the shaping parameter is .6692 (with a 95% confidence interval of (.5263, .8510)) and the scaling parameter is 477.4297 (with a 95% confidence interval of (294.3538, 774.3714)).  A Weibull probability plot of the second population of x values for prime n values less than 4000000 is;



There should be infinitely many such populations.  The minima appear to be bounded for all n values in a given population.  For example, 2⁴⁰∙1.5704 is an upper bound of the minima (as computed using the m-cycle inequality) in the first population when n is less than 1000000 and is still an upper bound of the minima in the first population when n is less than 6000000.  When c=-1, 2³⁹∙1.2002 is an upper bound of the minima in the first population when n is less than 3000000 and is still an upper bound of the minima in the first population when n is less than 6000000.

The minima in the second population do not increase monotonically within a period; there is a characteristic dip about half-way through the period.  For example, a graph of truncated upper bounds of minima (scaled by 32768.0) for n=609757, 609781, 609877, ..., 610993 (primes of the form 12k+1) is;



Similarly, there is a dip about a third of the way through the period and another dip about two-thirds of the way through the period for the minima in the third population.  For example, a graph of truncated upper bounds of minima (scaled by 32768.0) for n=5905433, 5905553, 5905673, ..., 5907353 (primes of the form 12k+5) is;



A graph of the maximum upper bounds of minima (scaled by 65536.0) for x values from 31 to 72 (in the first population) for prime n values less than 6000000 is;


(The scaled maximum upper bounds of minima for x=31, 32, 33, ..., 52 are 174, 188, 199, 226, 234, 248, 274, 295, 320, 344, 379, 418, 480, 532, 634, 746, 934, 1202, 1760, 3356, 24559, and 26346062 respectively.  This appears to be an exponential probability distribution where μ=1.1993e+06 with a 95% confidence interval of (.8219e+06, 1.9136e+06).  The scaled maximum upper bounds of minima for x=53, 54, 55, ..., 72 appear to be random samples from the same exponential probability distribution.)  A graph of the maximum upper bounds of minima (scaled by 65536.0) for x values from 89 to 114 (in the second population) for prime n values less than 6000000 is;


A graph of the sorted maximum upper bounds of minima for x values from 89 to 144 for prime n values less than 6000000 is;



The periods for prime l values of the form 54k+1 are approximately equal.  Similar results apply for prime l values of the form 54k+5, 54k+7, 54k+11, 54k+13, 54k+17, 54k+19, 54k+23, 54k+25, 54k+29, 54k+31, 54k+35, 54k+37, 54k+41, 54k+43, 54k+47, 54k+49, or 54k+53.  Let x denote one fifty-fourth of the difference in l values between successive peaks in minima values.  For prime l values less than or equal to 3169919, the distribution of x values for 11, 12, 13, ..., 17 is 504, 1488, 2848, 4712, 4054, 1907, and 1009 respectively (a population centered around x=14), the distribution of x values for 25, 26, 27, ..., 32 is 183, 937, 1510, 2826, 2409, 2020, 811, and 165 respectively (a population centered around x=28), the distribution of x values for 40, 41, 42, ..., 46 is 433, 664,1312, 1258, 899, 705, and 184 respectively (a population centered around x=42), etc.  These are Weibull probability distributions (with different parameters).  (The shaping parameters range from about 1.3 to 2.2, so these are "aging" processes.)  For prime l values less than or equal to 6339847, the scaled (by 65536.0) maximum upper bounds of minima (as computed using the m-cycle inequality) for x values of 11, 12, 13, ..., 17 are 6220270, 436632, 744405, 514414, 597, 256, and 166 respectively.  For prime l values less than or equal to 6339847, the scaled maximum upper bounds of minima for x values of 25, 26, 27, ..., 32 are 332686, 1366582, 93783, 526748, 831, 299, 179, and 130 respectively.  For prime l values less than or equal to 6339847, the scaled maximum upper bounds of minima for x values of 40, 41, 42, ..., 46 are 301174, 540827, 101914, 1552, 362, 196, and 139 respectively.  These appear to be exponential probability distributions.  For prime l values less than or equal to 9509761, the scaled maximum upper bounds of minima for x values of 11, 12, 13, ..., 17 are 6220270, 436632, 744405, 916817, 900, 387, and 246 respectively.  For prime l values less than or equal to 9509761, the scaled maximum upper bounds of minima for x values of 25, 26, 27, ..., 32 are 9037278, 1366582, 229310, 526748, 1320, 439, 269, and 195 respectively.  For prime l values less than or equal to 9509761, the scaled maximum upper bounds of minima for x values of 40, 41, 42, ..., 46 are 301174, 540827, 149513, 2343, 521, 294, and 204 respectively.  In general, the scaled maximum upper bounds of minima for the larger x values of each population are still growing.  (As the prime gaps become larger, the scaled maximum upper bounds of minima for even the larger x values of say the first population should stop growing.)

More Properties of Least-Residue Trees

In this section, c is restricted to being 1 or -1.  The many common properties of the least-residue trees of the 3n+1 and 3n-1 sequences indicate that it would be more logical to allow negative n values and consider the two sequences to be the same sequence.  More of these properties (for the first kind of least-residue tree) are;

(5)  If c=1, no limb other than {4, 2, 1} ends in an odd natural number less than 2^k.  If c=-1, no limbs other than {2, 1} and {20, 10, 5, 14, 7} end in an odd natural number less than 2^k.  (Note that the dead limb {..., 54, 27, 80, 40} attaches to {20, 10, 5, 14, 7} for k>4.)

(6)  If k>2, there are 2^k-3 limbs in A, B, C, or D.

(7)  If k>2, there are 2^k-3 limbs in E and F.

(8)  If k>4, a fourth of the limbs in A attach to four-element limbs.

(9)  If a limb in A ends in the natural number i where (3i+c)/2>2^k+1, then the limb attaches to a two-element limb.

(10)  The fourth element of a limb in E is even (there are at least four elements in a limb in E).

(11)  A four-element limb in A_e cannot attach to a four-element limb in A, B, C, or D.

(12)  A two-element limb in A_o cannot attach to a two-element limb in A or C.

(13)  There are no limbs in E with lengths of 2, 3, 5, 6, 8, or 11.

Outline of the Approach to the 3n+1 and 3n-1 Problems

The first step is to prove that twice the minimum odd element in a cycle is larger than the maximum odd element in the cycle.  (This will insure that the "gain" requirement for limbs in S of a least-residue tree can be met.)  If n (the number of odd elements in the cycle) is prime, twice the minimum element minus 3^n-1/(2^l-3ⁿ)  equals the maximum odd element.  (When the parity vector computed using the floor function is right-rotated by one position, the parity vector computed using the ceiling function is obtained except for the first element.)  When n is not prime, the parity vector (as computed using the ceiling function) may repeat (for example, after l/2 positions), in which case twice the minimum odd element is even larger than the maximum odd element.  In general, twice the minimum odd element in a cycle minus ∑3^n-1-ip∙2^il/r/(2^l-3ⁿ) where p denotes the number of odd elements in a repeating portion of the parity vector, r denotes n/p, and the summation is from i=0 to r-1 equals the maximum odd element in the cycle.  The parity vector can repeat only if r divides l.  The sequence vector derived from a repeating portion of the parity vector (or the entire parity vector if it does not repeat) by changing (1, 0)'s to 2's and the last 2 to a 1 has bilateral symmetry.  (This suggests that a live limb in S can only attach to itself at its beginning if n or l is prime [or, at the least, n and l are relatively prime].  For limb lengths of 7, 12, 17, or 48, the n values are prime and for a limb length of 30, l is prime.  The minima appear to be bounded for prime n or l values.)

Other steps are to find the admissible sequence vectors for limbs in S and to prove that the number of limbs in S is 2^k-1 (so that the 3n+1 "process" can be confirmed).

Properties of Cycles in the 3n+c Sequence

In this section, c values less than -1 and negative sequence values are allowed.  The order of a cycle is defined to be the smallest natural number of the form 3∙2^k that is greater than or equal to the element of the cycle with the greatest absolute value.  The format for displaying cycles is illustrated for c=-1;

c=-1, l=5, order=24
attaches at beginning
(10, 5, 14, 7, 20, 10)

c=-1, l=18, order=384
21→23, 68, count=28
(336, 168, 84, 42, 21, 62, 31, 92, 46, 23, 68, 34, 17, 50, 25, 74, 37, 110, 55, 164, 82, 41, 122, 61, 182, 91, 272, 136, 68)

The length of the cycle is denoted by l.  The phrase "attaches at the beginning" indicates that the cycle is an "odd" path.  In this case, the elements of the cycle are listed so that the odd element in the cycle with the largest absolute value is the third-to-last element.  "Attachment points" follow an element in the cycle that is divisible by 8.  If i is the first element in a sub-sequence of the cycle that is divisible by 8, then the primary attachment point is i/4, the secondary attachment point is i/16 (if 16 divides i), the tertiary attachment point is i/64 (if 64 divides i), etc.  In the example above, a primary attachment point is 68.  When there are attachment points, the 3n+c sequence is extended to the left until an odd natural number divisible by 3 is encountered.  Then if the cycle order has not already been exceeded, the sequence is further extended to the left until an element exceeds the cycle order.  If the cycle order has been exceeded (between the attachment point and the odd natural number divisible by 3), the "order" is set according to the element with the largest absolute value in this sub-sequence and not the cycle order.  The "count" variable is the length of this sequence.  In the example above, "21→23, 68" indicates that the attachment point is one jump away from the odd natural number divisible by 3, that is, 21 jumps to 23 and 68 follows 23.  (This will be referred to as a "one jump" attachment point.)  An attachment point where the odd natural number divisible by 3 is immediately before the attachment point will be referred to as a "no jump" attachment point.  Some properties of cycles (based on the known cycles for c in the range from -151 to 151) are;

(14)  If c is of the form 3j-1 where j is a natural number, then the odd natural number immediately before a primary attachment point is of the form 3k or 3k-1 where k is a natural number.  If c is of the form 3j+1, then the odd natural number immediately before a primary attachment point is of the form 3k or 3k+1.

(15)  The cycle order equals the order for a "one jump" attachment point.

(16)  There is at least one attachment point that is a "no jump" or "one jump" attachment point.

More cycles are;

c=5, l=4, order=12
3→1, -2, count=9
(6, 3, 4, 2, 1, -2, -1, -8, -4, -2)

c=5, l=8, order=192
attaches at beginning
(58, 29, 92, 46, 23, 74, 37, 116, 58)

c=5, l=8, order=192
3→11, 38, count=21
(96, 48, 24, 12, 6, 3, 14, 7, 26, 13, 44, 22, 11, 38, 19, 62, 31, 98, 49, 152, 76, 38)

c=5, l=44, order=12288
519, 1562, count=49
291→497, 1496, count=57
123, 374, count=51
(8304, 4152, 2076, 1038, 519, 1562, 781, 2348, 1174, 587, 1766, 883, 2654, 1327, 3986, 1993, 5984, 2992, 1496, 748, 374, 187, 566, 283, 854, 427, 1286, 643, 1934, 967, 2906, 1453, 4364, 2182, 1091, 3278, 1639, 4922, 2461, 7388, 3694, 1847, 5546, 2773, 8324, 4162, 2081, 6248, 3124, 1562)

c=5, l=44, order=12288
477, 1436, count=49
171→443, 1334, count=60
(7632, 3816, 1908, 954, 477, 1436, 718, 359, 1082, 541, 1628, 814, 407, 1226, 613, 1844, 922, 461, 1388, 694, 347, 1046, 523, 1574, 787, 2366, 1183, 3554, 1777, 5336, 2668, 1334, 667, 2006, 1003, 3014, 1507, 4526, 2263, 6794, 3397, 10196, 5098, 2549, 7652, 3826, 1913, 5744, 2872, 1436)

c=7, l=6, order=48
-3→1, 10, count=15
(-24, -12, -6, -3, -2, -1, 4, 2, 1, 10, 5, 22, 11, 40, 20, 10)

c=-11, l=7, order=96
attaches at beginning
(38, 19, 46, 23, 58, 29, 76, 38)

c=-11, l=8, order=96 or 48
21→13→7→1, -8, count=22
3, -2, count=12
(84, 42, 21, 52, 26, 13, 28, 14, 7, 10, 5, 4, 2, 1, -8, -4, -2, -1, -14, -7, -32, -16, -8)

c=11, l=22, order=384
9→17, 62, count=33
3→5, 26, count=32
(288, 144, 72, 36, 18, 9, 38, 19, 68, 34, 17, 62, 31, 104, 52, 26, 13, 50, 25, 86, 43, 140, 70, 35, 116, 58, 29, 98, 49, 158, 79, 248, 124, 62)

For c=5, there are two pairs of interrelated cycles; a pair with lengths of 8 and a pair with lengths of 44.  In the first cycle with a length of 44, there are several attachment points (the first two are primary attachment points and the third is a secondary attachment point).  The extended sequence shown corresponds to the first attachment point.  The "519, 1562" for the first attachment point indicates a "no jump" attachment point.  The "21→13→7→1, -8" for the c=-11 cycle with a length of 8 indicates that several jumps from the odd natural number divisible by 3 (21) are required to reach the odd natural number before the attachment point (1).  This will be referred to as a "multiple jump" attachment point.  (These attachment points are relatively rare and usually consist of several small jumps.)  Another property of cycles (a consequence of cycles consisting of whole jumps) is;

(17)  A primary attachment point is a "no jump", "one jump", or "multiple jump" attachment point.

More cycles are;

c=-13, l=5, order=24
3, -4, count=8
(12, 6, 3, -4, -2, -1, -16, -8, -4)

c=13, l=13, order=1536
attaches at beginning
(566, 283, 862, 431, 1306, 653, 1972, 986, 493, 1492, 746, 373, 1132, 566)

c=13, l=13, order=1536
attaches at beginning
(842, 421, 1276, 638, 319, 970, 485, 1468, 734, 367, 1114, 557, 1684, 842)

c=13, l=13, order=3072
147, 454, count=18
(2352, 1176, 588, 294, 147, 454, 227, 694, 347, 1054, 527, 1594, 797, 2404, 1202, 601, 1816, 908, 454)

c=13, l=13, order=3072
213→163, 502, count=20
(1704, 852, 426, 213, 652, 326, 163, 502, 251, 766, 383, 1162, 581, 1756, 878, 439, 1330, 665, 2008, 1004, 502)

c=13, l=13, order=3072
159→187, 574, count=23
(2544, 1272, 636, 318, 159, 490, 245, 748, 374, 187, 574, 287, 874, 437, 1324, 662, 331, 1006, 503, 1522, 761, 2296, 1148, 574)

c=13, l=13, order=3072
123→223, 682, count=25
(1968, 984, 492, 246, 123, 382, 191, 586, 293, 892, 446, 223, 682, 341, 1036, 518, 259, 790, 395, 1198, 599, 1810, 905, 2728, 1374, 682)

c=13, l=13, order=6144
99→277, 844, count=28
(3168, 1584, 792, 396, 198, 99, 310, 155, 478, 239, 730, 365, 1108, 554, 277, 844, 422, 211, 646, 323, 982, 491, 1486, 743, 2242, 1121, 3376, 1688, 844)

c=13, l=39, order=6144
345, 1048, count=44
51→358 (jumps over attachment point 262 [51, 166, 83, 262, ...]), count=48
21→19→115, 358, count=62
(5520, 2760, 1380, 690, 345, 1048, 524, 262, 131, 406, 203, 622, 311, 946, 473, 1432, 716, 358, 179, 550, 275, 838, 419, 1270, 635, 1918, 959, 2890, 1445, 4348, 2174, 1087, 3274, 1637, 4924, 2462, 1231, 3706, 1853, 5572, 2786, 1393, 4192, 2906, 1048)

For c=13 and a length of 13, there are seven interrelated cycles.  For the cycle with a length of 39, "51→358 (jumps over attachment point 262 [51, 166, 83, 262, ...])" indicates that the attachment point (262) is within the first jump from the odd natural number divisible by 3 (51).  Note that the attachment point is secondary.  Sometimes there are several jumps before the attachment point is "jumped over".  Another property of cycles is;

(18)  If the power of two that divides a primary attachment point is sufficiently large, a "no jump" attachment point is followed by an attachment point that is within the last of several (or one) jumps from the odd natural number divisible by 3, the attachment point that is within the last of several (or one) jumps from the odd natural number divisible by 3 is followed by a "one jump" or "multiple jump" attachment point, the "one jump" or "multiple jump" attachment point is followed by a "no jump" attachment point, etc.

A Property of General 3n+1 or 3n-1 Sequences

In this section, c is restricted to being 1 or -1.  Consider a segment of the general 3n+1 or 3n-1 sequence (not necessarily an "odd" path) where the third-to-last element of the sequence (denoted by i) is odd, the second-to-last element of the sequence is divisible by 8, and the segment has been extended to the left until an odd natural number divisible by 3 has been encountered.  The order of this segment is defined to be the smallest natural number of the form 3∙2^k greater than or equal to the element with the largest value.  The segment is then further extended to the left until the order is exceeded.  A property of this segment is;

(19)  If i is greater than the order divided by 6, segment lengths of 3, 6, 11, 16, 19, 24, 29, 32, 37, 42, 47, 50, 55, 60, 63, 68, 73, 78, 81, 86, 91, 94, and 99 (and larger unspecified values) are not permissible.

The permissible lengths of these generalized dead limbs include the permissible lengths of the limbs in S of a least-residue tree.  (New permissible lengths are three larger than the second element of a consecutive length pair.)  An example of such a segment with a permissible length (18) where c=1 and the order equals 24576 is {17508, 8754, 4377, 13132, 6566, 3283, 9850, 4925, 14776, 7388, 3694, 1847, 5542, 2771, 8314, 4157, 12472, 6236}.  Another example of such a segment with a permissible length (28) where c=-1 and the order equals 384 is {336, 168, 84, 42, 21, 62, 31, 92, 46, 23, 68, 34, 17, 50, 25, 74, 37, 110, 55, 164, 82, 41, 122, 61, 182, 91, 272, 136} (containing the eighteen-element cycle {68, 34, ..., 136}).  The lengths of these segments are of relevance in cycle formation.  (Note that if i is greater than the order divided by 6, then the second-to-last element in the segment [3i+1 or 3i-1] is greater than the order divided by 2, that is, the second-to-last element of the segment [along with other elements of the segment] determines the order.)

When one of these segments is a newly-formed dead limb in F of a least-residue tree (where one element has been appended at the beginning and two elements have been appended at the end of the limb from the previous order) and there is a cycle in the segment, Proposition (16) above imposes some constraints on the number of even elements and the number of odd elements in the cycle.  For example, when c=-1, there are 15 even elements and 10 odd elements in the limb (168, 84, 42, ..., 91) and there are 3 even elements and 3 odd elements in the jump from 21 (the odd natural number divisible by 3) to 23 (the odd natural number immediately before 68 [the first element of the cycle]).  68∙4=272 and 272 determines the order of the segment and in turn the number of even elements to the left of 21.

When c≥-1, most cycles with only one attachment point are contained in one of these segments and the sequence vector of a segment exhibits bilateral symmetry when the number of 2's in the sequence vector is even (disregarding the first and last elements of the sequence vector and sometimes the second or  next-to-last element of the sequence vector).  For example, the sequence vectors of the interrelated segments for c=13 and a cycle length of 13 are (4, 1, 1, 1, 1, 2, 3), (3, 2, 1, 1, 1, 2, 1, 3), (4, 1, 2, 1, 1, 2, 1, 1, 3), (4, 1, 1, 2, 1, 2, 1, 1, 1, 3), and (5, 1, 1, 1, 2, 2, 1, 1, 1, 1, 3).  The sequence vectors of the interrelated segments for c=37 and a cycle length of 9 are (6, 2, 1, 2, 1, 3) and (5, 1, 2, 2, 1, 1, 3).  The sequence vectors of the interrelated segments for c=47 and a cycle length of 11 are (4, 1, 1, 1, 2, 3), (4, 2, 1, 1, 2, 1, 3), (6, 1, 2, 1, 2, 1, 1, 3), and (7, 1, 1, 2, 2, 1, 1, 1, 3).  The sequence vectors of the interrelated segments for c=101 and a cycle length of 10 are (6, 2, 1, 2, 3) and (5, 1, 2, 2, 3).

A Generalization of 1-2 Sequence Vectors

In this section, c is restricted to being 1.  Let y be an even natural number such that y/2 is odd and denote [(y/2)(3/4)^f]+1 where f is a natural number and the brackets denote the greatest integer function by v₁.  (The 3/4 factor corresponds to the "loss" due to a 2 in a sequence vector.)  v₁ will be referred to as a "tumble" if it is odd (tumbles are the counterparts of jumps).  Usually, v₁ is not in the 3n+1 sequence starting with y/2.  Under the same order constraints as least-residue trees, a succession of tumbles and jumps (where the jumps start from the tumbles and the tumbles start from the jumps) have properties similar to a live limb in S of  a least-residue tree.  Denote the peaks and valleys in a succession of tumbles and jumps by y/2, v₁, p₁, v₂, p₂, v₃, p₃, ..., v_i, p_i and denote the exponents of the tumbles by f₁, f₂, f₃, ..., f_i and the exponents of the jumps by g₁, g₂, g₃, ..., g_i.  The conditions to be imposed on y and the jumps are that y be less than the order (of the form 3∙2^k) and greater than  order/2, each of p₁, p₂, p₃, ..., p_i be less than the order, and p_i be greater than order/3.  These conditions do not always guarantee that v₁ is in the 3n+1 sequence starting with y/2, v₂ is in the 3n+1 sequence starting with p₁, v₃ is in the 3n+1 sequence starting with p₂, etc., but they come close to doing so.   For example, for i=2, f₁=5, g₁=4, f₂=5, g₂=3, y=282825586, and an order of 402653184, v₁=33557919, p₁=169886969, v₂=40314975, and p₂=136063043 where y, p₁, and p₂ are within the specified bounds.  The 3n+1 sequence starting with 141412793 (y/2) and having a length of 3f₁+1 ends in 33557920, which is one larger than v₁ (the 3 factor of the tumble exponent corresponds to the number of elements in the 3n+1 sequence due to a 2 in a sequence vector) .  The 3n+1 sequence starting with 169886969 (p₁) and having a length of 3f₂+1 ends in 241889848, where [241889848/6]+1 equals v₂.  Denote the natural numbers these 3n+1 sequences end in by j and k.  Some possibilities for different y values giving tumbles and jumps with exponents of 5, 4, 5, and 3 respectively are; (1) v₁=j and v₂=k, (2) v₁=j-1 and v₂=[k/6]+1, (3) v₁=j-1 and v₂=[k/6], (4) v₁=j and v₂=[k/6], (5) v₁=[j/6]+1 and v₂=6k-5, (6) v₁=j-1 and v₂=k-1, (7) v₁=6j-5 and v₂=k, (8) v₁=[j/6]+1 and 3v₂+1=[k/12], (9) v₁=[j/6]+1 and 3v₂+1=[k/12]+1, and (10) v₁=j-1 and v₂=36k-9 (there are other possibilities).   In general, if  v₁ is in the 3n+1 sequence starting with y/2, there are f₁+1 odd natural numbers and 2f₁ even natural numbers in this sub-sequence (the same as for a sequence vector consisting of f₁ 2's), if v₂ is in the 3n+1 sequence starting with p₁, there are f₂+1 odd natural numbers and 2f₂ even natural numbers in this sub-sequence (the same as for a sequence vector consisting of f₂ 2's), if v₃ is in the 3n+1 sequence starting with p₂, there are f₃+1 odd natural numbers and 2f₃ even natural numbers in this sub-sequence (the same as for a sequence vector consisting of f₃ 2's), etc.  These limbs (not necessarily 1-2 sequence vectors) then have the same X and Y values as a live limb in S of a least-residue tree. 

References

(1)  Bohm, C., and Sontacchi, G., On the existence of cycles of given length in integer sequences like x_n+1=x_n/2 if x_n even, and x_n+1=3x_n+1 otherwise, Atti Accad. Naz. Lincei, VIII Ser., Rend., Cl. Sci. Fis. Mat. Nat. LXIV (1978), 260-264.

(2)  G. J. Wirsching, The Dynamical System Generated by the 3n+1 Function, 1681, Springer-Verlag (1998).
 
(3)  R. E. Crandall, On the "3x+1" Problem, Mathematics of Computation, Vol. 32, No. 144, Oct. 1978, Pgs. 1281-1292.

(4)  J. Simons and B. de Weger, Theoretical and computational bounds for m-cycles of the 3n+1 problem, Acta Arith., 2005.

(5)  L. Halbeisen and N. Hungerbuhler, Optimal bounds for the length of rational Collatz cycles, Acta Arith., LXXVIII.3, (1997), pgs. 227-239.

Software

MSVC++™ C programs were used to confirm the above propositions.

Use test0a to find cycles in the 3n+c sequence.  The "iters" variable specifies the number of jumps from the initial n value in the sequence (an odd natural number divisible by 3).  Usually, "iters" is set to 1.  The list of cycles for c in the range from -151 to 151 was generated using this setting.  The list of cycles was confirmed to be the same using an "iters" setting of 2 or 3.  The cycles were verified to be the same as those given by Keith Matthews' cycle-finding program at "http://www.numbertheory.org/keith.html".

Use test0b to regenerate a cycle in the 3n+c sequence given an entry point (must be even) into the cycle.  The order of the cycle is computed.  The output of "test0a" is input to this program.

Use test0c to regenerate cycles in the 3n+c sequence given a list of entry points into the cycles.  (The list of cycles is confirmed.)

Use test0d to regenerate cycles in the 3n+c sequence given a list of entry points into the cycles.  A check for 1-2 sequence vectors at entry points into the cycles is made (for "multiple jump" connection points).

Use test0e to regenerate cycles in the 3n+c sequence given a list of entry points into the cycles.  A check for 1-2 sequence vectors at entry points into the cycles is made (for "jumps over" connection points).

list consists of the cycles found for c in the range from -151 to 151.

list1 consists of one-attachment-point cycles found for c in the range from -151 to 151.

Use test1 to find the number of jumps in the 3n+1 sequence before an even natural number is reached (starting with an odd natural number divisible by 3).

Use test2 to generate a histogram of limb lengths for a 3n+c sequence that is not an "odd" path.  The third-to-last element of the sequence must be an odd natural number greater than order/6 and the second-to-last element of the sequence must be an even natural number divisible by 8.

Use test3a to generate limbs of least-residue trees where at least one element of the limb is divisible by 8.

Use test3b to generate limbs of least-residue trees where at least one element of the limb is divisible by 8.  Multiple-word arithmetic is used.

Use test3c to generate limbs of least-residue trees where at least one element of the limb is divisible by 8.  Multiple-word arithmetic is used.  This C program is for use on the TMS320C64™ digital signal processing chip (with hand-optimized assembly language subroutines).

Use test4a12, test4a13, test4a14, test4a15, test4a16, test4a17, test4a18, test4a19, test4a20, test4a21, test4a22, test4a23, test4a24, test4a25, test4a26, test4a27, test4a28, test4a29, test4a30, test4a31, test4a32, and test4a33 to compare the number of limbs in S of a given length to the estimated number of limbs.  Only live limbs are considered.

Use test5a to generate tumbles and jumps having three peaks and two troughs.

Use test5b to generate tumbles and jumps having four peaks and three troughs.

Use test6a to compute the largest y values, the smallest y values, the largest z values, and the smallest z values for live limbs in S associated with a given sequence vector.  The maximum |X(δ/y)| value is computed.

Use test6b to compute the largest y values for live limbs in S associated with a given sequence vector.  The maximum |X(δ/y)| value is computed.  This C program is for use on the TMS320C64™ digital signal processing chip (with hand-optimized assembly language subroutines).

Use test7 to check that n(order/2)>ce, c>0, n>0, or (-n)(order/2)>(-c)e, n<0, c<0.  Floating point arithmetic is used.

Use test8 to check that x>0 for limb lengths with positive limits and x<0 for limb lengths with negative limits.

Use test9 to generate least-residue trees.  The permutation of A, B, C, and D for different c values is checked.

Use test10 to generate least-residue trees for the 3n-1 sequence, k≤15.  Numerous properties of least-residue trees are tested.  Limbs in S having lengths of 5, 10, 15, 18, 23, and 28 are verified to be dead.

Use test11 to generate long limbs in S.  Sequence vectors are generated.

Use test12 to find sequence vectors corresponding to different e values.  All the orders up to 3∙2²⁴ are computed.  The maximum and minimum x/y values for live limbs are computed for every order and are verified to be either ascending of descending.

Use test13 to compute a and b values.

Use test14a to compute the minimum element in a cycle using the formula M_l,n=∑(]jn/l[-](j-1)n/l[)2^j-13^n-]jn/l[  where the summation is from j=1 to l.  Use test14b to compute the minimum element in a cycle in a limb of S of a least-residue tree.  Use test14c to compute the minimum element in a cycle in a limb of S of a least-residue tree (using the TMS320C64™ DSP.)  Use test14d to compute the minimum element in a cycle in a limb of S of a least-residue tree when n and n+2 are primes.  Use test14e to output the computed minima for a cycle in a limb of S of a least-residue tree.  Use test14f to compute an upper bound of the minimum element in a cycle in a limb of S of a least-residue tree where n and n+2 are prime.  Use test14g to compute an upper bound of the minimum element in a cycle in a limb of S of a least-residue tree when n is prime.  Use test14h to compute an upper bound of the minimum element in a cycle in a limb of S of a least-residue tree when n is prime (using the TMS320C64™ DSP).  Use test14i to generate the sequence vector corresponding to the smallest e from the parity vector.  Use test14j to compute the largest odd element in a cycle using the floor function.  Use test14k to compute an upper bound of the minimum element in a cycle in a limb of S of a least-residue tree when l is prime (using the TMS320C64™ DSP).  A graph of minima (along the y axis) for n=11, 59, 71, ..., 5099 (primes of the form 12k-1 where n+2 is also a prime) is;

A graph of minima for n=13, 61, 73, ..., 5101 (primes of the form 12k+1 where n-2 is also a prime) is;


A graph of minima for n=5, 17, 29, ..., 5021 (primes of the form 12k-7 where n+2 is also a prime) is;


A graph of minima for n=7, 19, 31, ..., 5023 (primes of the form 12k-5 where n-2 is also a prime) is;


A graph of the upper bounds of the minima for n=11, 59, 71, ..., 9767 (primes of the form 12k-1 where n+2 is also a prime) is;



A graph of the upper bounds of the minima for n=5, 17, 29, ..., 9929 (primes of the form 12k-7 where n+2 is also a prime) is;



The x values corresponding to these n values also have a Weibull probability distribution (but with different shaping and scaling parameters).

Multiple-word arithmetic C subroutines are add64, add128, add256, add512, add1024, carry, copy256, copy512, copy1024, div6432, div12864, div25632,  lshift256, lshift512, lshift1024, lmbd, mul6432, mul6464, mul12832, set256, set512, set1024, shift64, shift128, shift256, shift512, shift1024, sub64, sub128, sub256, sub512, sub1024, subr2, n-word arithmetic, table, table1, and table2.

Multiple-word arithmetic TMS320C64™ assembly language subroutines are add64, div12864, mul6432, mul6464, shift64, sub64, subr2, and n-word arithmetic.