1.0 Introduction

      Notation:  #3a0d       Hexadecimal values have a leading pound sign.

                 X*Y         Multiplication

                 X^Y         Exponentiation

                 log2( x )   Log base 2 of X




The original Collatz sequence is:

      N is Even:    N'  =  N / 2

      N is Odd:     N'  =  3 * N + 1




A variation is to rewrite it as a series of Odd steps. In this form E_i is the number of Even steps in each transition. This is also the number of trailing zeros in the result from each Odd transition. It will always be one or more. The second Odd form runs a little faster and easier to code when computing sequence values.

      N0   = Seed

             Ni * 3 + 1      |N / 2| + N + 1
      Ni+1 = -----------  =  ----------------
                 2^Ei              2^Ei




To misappropriate the terms from astrophysics, the point where the sequence dips below the starting Seed is the (event) horizon. Any series that goes below the horizon collapses to the singularity, one.

Here a run length is defined as the number of odd steps until the sequence goes below the horizon. This definition is useful because it corresponds wo the number of terms in the algebraic expansion.

1.1 Expand the Sequence

The algebraic expansion of a full run of length, L, is:

       Seed * 3^L + DL
NL  =  ---------------
            2^EL


                  L
   where:  DL  =  ∑  3^(L-j) * 2^Kj-1
                 j=1




K_j-1 is the total number of even transitions up through step j. To expand this sequence it is useful to define K_j-1 as a sequence.

K0  =  0

Ki  =  Ki-1 + Ei




This lets us expand the sequence to form an iterative sequence.

N0  =  Seed                           Only odd Seeds are allowed


N1  =  Seed * 3 + 1 / 2^K1            K1 = E1


N2  =  Seed * 3 + 1              Seed*9 + 3 + 2^K1  
       ------------  * 3 + 1  =  -----------------
            2^K1                        2^K2
            ----------------
                2^E2


N3  =  Seed*9 + 3 + 2^K1              Seed*27 + 9 + 3*2^K1 + 2^K2
       ----------------- * 3 + 1  =  ----------------------------
               2^K2                              2^K3
               -----------------
                       2^E3


                    i
Ni  =  Seed*3^i  +  ∑  3^(i-j) * 2^Kj-1  
                   j=1
      --------------------------------
                   2^Ki




To simplify the expansion let D_i signify the sum through step i. This term is useful since D_i encapsulates the non-algebraic portion of the sequence known as the hailstone effect.

       Seed * 3^i + Di                  i
Ni  =  ---------------           Di  =  ∑  3^(i-j) * 2^Kj-1
            2^Ki                       j=1




D_i can also be computed using a recursive sequence derived directly from the Collatz sequence. This recursive form is useful to validate that D_i is properly calculated.

D0  =  0                 Di+1  =  Di * 3 + 2^Ki




The value of K_L is defined as the final value of K_i in a run.

       Seed * 3^L + DL
NL  =  ---------------  <  Seed
            2^KL




Since the values of N_i only drops below the Seed at the end of a run then 2^K_L will be just large enough to satisfy this constrint. Dividing both sides by the Seed we get:

3^L + DL / Seed
----------------   <  1
      2^KL




Here the term D_i/Seed is much smaller than 3^i so it can be dropped. This leaves 2^K_L as the lowest power of two that is a little greater than 3^L.

3^L  <  2^KL    and    KL  >=  ⌈log2( 3^L )⌉




This example combines all four sequence components; showing how they interrelate. The horizon line is the point where the series drops below the Seed.

  i       Ei       Ki       Ni           Di

  0       0        0       139           0    Seed = 139
  1       1        1       209           1    (139*3^1 + 3^0*2^0) / 2^1
  2       2        3       157           5    (139*3^2 + 3^1*2^0 + 3^0*2^1) / 2^3
--------------------------------------------  Horizon
  3       3        6        59          23    (139*3^3 + 3^2*2^0 + 3^1*2^1 + 3^0*2^3) / 2^6
  4       1        7        89         133
  5       2        9        67         527     
  6       1       10       101        2093
  7       4       14        19        7303
  8       1       15        29       38293
  9       3       18        11      147647
 10       1       19        17      705085
 11       2       21        13     2639543
 12       3       24         5    10015781
 13       4       28         1    46824559




The value of 2^K_L includes on the final value of E_L. In the final step as even transitions are applied the series goes below the horizon when the total 2^K_o reaches the bound ⌈log₂( 3^L )⌉. However, this can happen before the final group of even transitions complete. Consequently the complete 2^K_L can exceed that bound.

The length of a run, L, is the number of terms in the expansion. Since there are differnt interpretations of K for runs with the same number of terms, the number of even transitions is not a consistent metric for the run length. For example, runs with Seeds of 608_111 and 3_124_719 both have 100 terms. However the value of K for 608_111 is 159 and for 3_124_719 it is 160.

Here is the algebraic expansion for a longer run with a Seed of 359. The run length is 3 and K is 6, but ⌈log₂( 3^L )⌉ is 5.

                        Ni * 2^Ki  =  Seed * 3^i + Di


    i           1        2        3        4        5        6        7        8        9       10  

   Ei           1        1        2        1        1        1        1        4        2        2

   Ki           1        2        4        5        6        7        8       12       14       16

   Ni         539      809      607      911     1367     2051     3077      577      433      325

 Ni*2^Ki     1078     3236     9712    29152    87488   262528   787712  2363392  7094272 21299200 

Seed*3^i  359*3^1  359*3^2  359*3^3  359*3^4  359*3^5  359*3^6  359*3^7  359*3^8  359*3^9  359*3^10

Di              1        5       19       73      251      817     2579     7993    28075   100609

Di        3^0*2^0  3^1*2^0  3^2*2^0  3^3*2^0  3^4*2^0  3^5*2^0  3^6*2^0  3^7*2^0  3^8*2^0  3^9*2^0
                   3^0*2^1  3^1*2^1  3^2*2^1  3^3*2^1  3^4*2^1  3^5*2^1  3^6*2^1  3^7*2^1  3^8*2^1
                            3^0*2^2  3^1*2^2  3^2*2^2  3^3*2^2  3^4*2^2  3^5*2^2  3^6*2^2  3^7*2^2
                                     3^0*2^4  3^1*2^4  3^2*2^4  3^3*2^4  3^4*2^4  3^5*2^4  3^6*2^4
                                              3^0*2^5  3^1*2^5  3^2*2^5  3^3*2^5  3^4*2^5  3^5*2^5
                                                       3^0*2^6  3^1*2^6  3^2*2^6  3^3*2^6  3^4*2^6
                                                                3^0*2^7  3^1*2^7  3^2*2^7  3^3*2^7
                                                                         3^0*2^8  3^1*2^8  3^2*2^8
                                                                                  3^0*2^12 3^1*2^12
                                                                                           3^0*2^14

Depending on the context there are three definitions for K values.

Ki            Total number of even steps after each transition

KL  =  K      Total number of even steps in a run

Ko            Ko = ⌈log2( 3^L )⌉

1.2 Bounds On D_L

In this section we derive these upper and lower bounds on the D_L term.

3^L - 2^L   <=   DL   <=   L * 3^(L - 1)




The sum D_L depends on the values K_i; which are the total number of even steps following each odd step. Conway[1] showed they cannot be determined algebraically due to thier randomized behavior that creates the hailstone effect. However, it is possible to set bounds on D_L for a sequence with L Odd steps.

       L
DL  =  ∑  3^(L-j) * 2^Kj-1
      j=1




As the terms progress the powers of 3 are decremented in each step while the powers of two increase. Each of these values balance out so that all the terms are of the same magnitute. A balance is maintained because the powers of two are limited by K_i. Should K_i get too big, the corresponding value in the run dips below the horizon and it terminates.

A maximum bound for D_L is determined setting K_i values so they produce a large value. This is done by setting them to their maximum value early in the run. Since the powers of 3 are biggest early in the run, these terms get even larger with larger K_i values.

To stay above the horizon 3^j must remain greater than 2^K_j. Here is an algorithm that produces these maximum values of K_i. From them a maximum bound for D_L can be determined.

E = 0;                              Starting exponent for 2^Ei
K = 0;                              Starting sum of exponent values
Dmax = 3^(L-1);                      Power of 3 in the first term of DL 

DO J = 2  to  L:                    DO over terms up to the run length,
   E  = [log2( 3^(J-1) )] - K;         Maximum possible exponent
   K += E;                             Sum of exponents
 
   Dmax += 3^(L-J) * 2^K;              Sum of allowed maximum terms 
-




The first term of the series, 3^(L-1), is always the largest. In each step the power of 3 is reduced by 3^j. Since the value of 2^K_j has to remiain under 3^j we can derive an upper bound on D_L.

          3^j  >  2^Kj-1

3^(L-j) * 3^j  >  3^(L-j) * 2^Kj-1      previous  > current term

      3^(L-1)  >  3^(L-j) * 2^Kj-1      first term > any other term

   
       L
DL  =  ∑  3^(L-j) * 2^Kj-1  <=  L * 3^(L-1)
      j=1




The terms of the sum are close in magnitude so L*3^(L-1) turns out to be an accurate upper bound on D_L. Using the same approach, a lower bound for D_L can be made. In this case terms are minimized when all values of E_j are set to one. This means K_j = j giving us the following algorithm.

K = 0;                              Starting sum of exponent values
Dmin = 3^(L-1);                      Power of 3 in the first term of DL 

DO j = 2  to  L:                    DO over terms up to the run length,
   K += 1;                             Sum of exponents equal to one
 
   Dmin += 3^(L-j) * 2^K;               Sum of minimum terms
-




The lower bound produced by the algorithm can be calculated exactly as the sum of two parts. The first term, 3^(L-1), is the initial value. The remaining terms are calculated from the closed form of the geometric series.

Dmin  =  3^(L-1)                            Initial term

       + 3 * 2^(L-1) * (1.5^(L-2) - 1)      Geometric term




The sum of the remaining terms are evaluated in reverse order. The last term is 3*2^(L-1) and each prior term is 1.5 times as big.

  T  =  2^(L-1)                              Last term

Sum  =  T*1.5 + T*1.5^2 + T*1.5^3 +  ...  + T*1.5^(L-1)

Sum  =  T * {1 + 1.5 + 1.5^2 + 1.5^3 +  ...  + T*1.5^(L-1)}




The sum of the geometric series yield the lower bound on D_L.

L-1           1 - 1.5^(L-1)     1 - 1.5^(L-1)
 ∑  1.5^i  =  -------------  =  -------------  =  1.5^(L-1) * 2
i=0              1 - 1.5           -.5


Sum  =  T * 1.5^(L-1) * 2

     =  2^(L-1) * 1.5^(L-1) * 2

     =  { 3^(L-1) - 2^(L-1) } * 2

     =  2 * 3^(L-1) - 2^L


DL  >=  3^(L-1) + 2 * 3^(L-1) - 2^L

DL  >=  3^L - 2^L




Together the upper and lower bounds are:

3^L - 2^L   <=   DL   <=   L * 3^(L-1)




For verification these charts list bounds after running many Seeds that produced runs of a given length. The bounds were validated beyond this chart for Seeds up to 6*10^12.

                L * 3^(L-1)                        Observed
L              Maximum Bound                       Maximum DL

10                        #300de                           #169c9
15                      #446bc17                         #33e4817
20                    #5_69860d1c                     #4_069e6dd5
25                  #66b_f4ce0df9                   #499_7c31d84f
29                #25b62_218c688d                 #19582_9cf3badf
30                #75091_a5e8b73a                 #4b724_33ff27fd
35              #819b94b_3b36e8bb               #50c4ef4_133b9527
40           #8_c99eb99c_cefec1b8            #5_33af2189_7da9a539
41          #1b_0594e128_961c2d49            #f_b49c4be8_03b5a2cf
45         #962_4ddf75d3_8b4c1ddd          #59d_d56ec09e_ed78837f
50       #9e5ae_21ae451c_ea477f16        #5edd6_78b6ac73_a7ff33a1
55     #a5584b7_c4765d17_6ba6fedf      #563376f_74f8d091_54e81f4b
60  #a_b376e2a8_2a911fe3_79a731d4   #5_70b66f89_7c324334_70545e89


                 3^L - 2^L                         Observed
L              Minimum Bound                       Minimum DL
 
10                          #e2a9                          #18901
15                        #da726b                        #1f603b7
20                      #cfc41b91                     #1_f29d7af1
25                   #c5_44562aa3                   #28e_69d42f4f
29                 #3e6b_21437d93                  #b088_507802db
30                 #bb41_83ca78b9                 #2b9d1_6ab71fb1
35               #b1bf64_d930979b               #1a4445c_586dabe3
40             #a8b8b352_291fe821              #e28c7dbb_ac598c21
41           #1_fa2a1af6_7b5fb863            #1_ffdee34b_9a06b863          
45          #a0_275309fd_09495753           #a0_baeb3fce_b4355753
50        #9805_53ecdb2f_d09de3c9         #982B_32dba1a9_a4dde3c9
55      #904d0e_ad200e63_05df37cb       #911646_4dcfb2c2_6c9f37cb
60    #88f924ee_beeda7fe_92e1f5b1     #8a3b121e_a0239504_0bfef5b1