Collatz Conjecture      Bradley Berg            November 21, 2018
                                                Edited November 28, 2018


This is a work in progress.  It explores using a revised Collatz Conjecture
where node values are:   N % 3 = 2


I. Collatz Conjecture

     even S:  S' = S / 2
      odd S:  S' = S * 3 + 1

   The sequence eventually reduces to 1.


A. Rewritten Conjecture

      notation:   %   modulus


   The original sequence is rewritten to produce only values where:  N % 3 = 2
   This eliminates 2/3 of the values produced in order to simplify analysis.

   Combine two or three iterations in each step.
   The result for odd numbers is always even so we can take 2 steps:

      N' = {N * 3 + 1} / 2


   On an even number apply one of these two transitions:

      When N % 4 = 0 then:  N' = N / 4
      When N % 4 = 2 then:  N' = ([N / 2] * 3 + 1) / 2 = {N * 3 + 2} / 4


   The first even case takes 2 steps and the second takes 3.

   If the starting value does not meet the condition N % 3 = 2, apply the
   original transitions until it does.  Then repeatedly apply the rewritten
   transitions.  Eventually they reduce to two; which is trivially reduced
   to one using the original series.

    original:  13 => 40 => 20 => 10 => 5 => 16 => 8 => 4 => 2 => 1  terminate

     revised:  13  advance 20    =>    5    =>    8    =>   2  terminate => 1



B. N % 3 = 2

   The revised transitions consume and produce values where:  N % 3 = 2

       If N is odd  and  N = 6 * k + 5  then  N % 3 = 2
          N' = {3 * N + 1} / 2
             =  3 * {[6 * k + 5] + 1} / 2
             =      [18 * k + 16] / 2
             =        9 * k + 8  then  N' % 3 = 2


       If N is even  and  N = 12 * k + 8  then  N % 4 = 0  and  N % 3 = 2  
          N' = N / 4
             = [12 * k + 8] / 4
             =   3 * k + 2  then  N' % 3 = 2


       If N is even  and  N = 12 * k + 2  then  N % 4 = 2  and  N % 3 = 2  
          N' = (3 * N + 2) / 4
             = (3 * [12 * k + 2] + 2) / 4
             =      [36 * k + 8] / 4
             =        9 * k + 2  then  N' % 3 = 2


   The number of possible values between transitions is reduced by 2/3.


II. Advance the Initial Value

       notation:  /\   bitwise and


A. When N % 3 = 0

      DO until N /\ 1:           DO until the number is odd,
         N = N / 2;                 Advance one even transition.
      -

      N = (3 * N + 1) / 2;       Advance one odd transition.


B. When N % 3 = 1

      IF N /\ 1                  IF N is odd,
         N = (3 * N + 1) / 2;       Advance one odd transition.

      ELSE:                      ELSE N is even,
         N = N / 2;                 Advance one even transition.
      .


III. Graph transitions, the number of columns shifted, and the next row.

     The table below shows the first elements for the three transitions.
     In the first column reading down:  5 => 8   8 => 2   2 => 2

     The labels in the bottom row designate the location of the next node.
     The number denotes the number of columns to move left or right.
     Positive numbers move right and negatives move left.  The letter
     denotes the next case.  In the first column all cases stay in the
     first column.

     The 2x tag in the upper row denotes a fan in of 2.  This means there
     are two cases that can reach that node.


A. Odd N     delta      2x  2x      2x  2x      2x  2x      2x  2x      2x  2x
               6     5  11  17  23  29  35  41  47  53  59  65  71  77  83  89
   (3n+1)/2    9     8  17  26  35  44  53  62  71  80  89  98 107 116 125 134
   Shift:Row        0B  1A  0C  2A -1B  3A -1C  4A -2B  5A -2C  6A -3B  7A -3C
                  
                  
B. N % 4 = 0        2x  2x      2x  2x      2x  2x      2x  2x      2x  2x
              12     8  20  32  44  56  68  80  92 104 116 128 140 152 164 176
     n/4       3     2   5   8  11  14  17  20  23  26  29  32  35  38  41  44
   Shift:Row        0C -1A -2B -2A -3C -3A -5B -4A -6C -5A -8B -6A -9C -7A -11B
                  
                  
C. N % 4 = 2        2x      2x  2x      2x  2x      2x  2x      2x  2x      2x
              12     2  14  26  38  50  62  74  86  98 110 122 134 146 158 170
   (3n+2)/4    9     2  11  20  29  38  47  56  65  74  83  92 101 110 119 128
   Shift:Row        0C  0A -1B  1A -1C  2A -2B  3A -2C  4A -3B  5A -3C  6A -4B


               Example:  35 => 53 => 80 => 20 => 5 => 8 => 2
                         3A   -2B   -5B   -1A  -0B   0C   0C


IV. Shifts Per Column

   In this section the trend of transitions moving to the left is
   illustrated.  The shifts per column are computed by adding the shift
   counts for the three cases.  Nodes with fan ins of 2 count as 2 nodes.
   Their shift count is doubled as there are two instances where they are
   reached.

   The cumulative count is the running sum of the column counts.  The
   cumulative shift count over the graph is always negative (to the left).
   It also leans more to the left as the graph is extended to larger
   numbers.  Traversals eventually move left to the first column and
   terminate at 2.

         Per Column  0   0  -4   0  -9   7 -15   3 -14   3 -23  16 -27   6 -25

         Cumulative  0   0  -4  -4 -13  -6 -21 -18 -32 -29 -52 -36 -63 -57 -82


V. Traverse in Reverse

   The table in section II can be inverted so that the tree can be walked
   in either direction.  It also lays out individual nodes in the tree in
   sequence.


A. Map Outputs to Inputs

   This table lists the first few values from outputs to inputs.  It is then
   used to construct a graph covering all possible sequences.

      Output          2   5   8  11  14  17  20  23  26  29  32  35  38  41  44

     (Output*2-1)/3           5          11          17          23          29
      Output*4        8  20  32  44  56  68  80  92 104 116 128 140 152 164 176
     (Output*4-2)/3   2          14          26          38          50


   Inputs are the one or two numbers listed under the outputs.
   They correspond to values such that:

         [ (Output*2-1)/3 ] % 3 = 2     True 1 out of 4 times.
               [ Output*4 ] % 3 = 2     True for all Outputs.
         [ (Output*4-2)/3 ] % 3 = 2     True 1 out of 4 times.


B. Construct a Tree

   Each column in section A represents a node in the graph.
   Outputs include every number such that:  n % 3 = 2

   Collectively inputs also cover all numbers where:  n % 3 = 2
   There is one edge per number.

   Each of the three transitions has a corresponding graphical feature.


   1. Odd Number Chain

      An odd number chain has one even output and multiple even inputs.
      The chain can have many odd numbers, but are always finite in length.
      In this example the output is 26 and the inputs are {44, 68, 26}

                       44    68
                        |     |
                        V     V
                 14 => 11 => 17 => 26


      Eliding the odd numbers yields a n-ary node of even numbers:

                         
                 14 =>|
                 44 =>|=> 26
                 68 =>|


      The first odd number in a chain is:  N % 18 = 5 | 11
                                        => {5, 11, 23, 29, ...}


      The length of the chain is determined by the first odd bit pattern.
      The number of consecutive low order 1 bits determines the chain length.
      The bit pattern for 11 is 1011 so there are 2 elements in the chain.

      Outputs have the form:  18 * k + 8 => {8, 26, 44, 62, 80, 98, ...}

              8 <=   5 <= 20
             26 <=  17 <= 11 <= {14, 44}
             44 <=  29 <= {38, 116}
             62 <=  41 <= 164
             80 <=  53 <= 35 <= 23 <= 92
             98 <=  65 <= {86, 260}
            116 <=  77 <= 308
            134 <=  89 <= 59 <= 236
            152 <= 101 <= 134
            170 <= 113 <= 452
            188 <= 125 <= 83 <= {110, 332}
            206 <= 137 <= {182, 548}
            224 <= 149 <= 596
            242 <= 161 <= 107 <= 71 <= 47 <= {62, 188}

      
   2. By-Four Chain

      The first element is any number such that:  N % 8 ~= 0

          => {2, 5, 11, 14, 17, 23, 26, 29, 35, 38, 41, 50, ...}


      Each element in a By-Four chain is:  F' = 4 * F  or  First * 4^k

      By-Four chains have infinite length.


   3. Bridge Nodes

      The remaining elements have inputs with the form:  24 * k + 2
          => {26, 50, 74, 98, 122, 146, 170, 194, 218, 242, ...}


      Outputs have the form:  18 * k + 2
          => {20, 38, 56, 74, 92, 110, 128, 146, 187, ...}


      They bridge the other two features to form a complete graph.

         20 <=  26 <=  17 <= 11 <= {14, 44}
         38 <=  50 <= 200 <= x4 ...
         56 <=  74 <= 296 <= x4 ...
         74 <=  98 <=  65 <= {86, 260}
         92 <= 122 <= 488 <= x4 ... 
        110 <= 146 <= 584 <= x4 ...
        128 <= 170 <= 113 <= 452
        146 <= 194 <= 776 <= x4 ...
        164 <= 218 <= 872 <= x4 ...
        182 <= 242 <= 161 <= 107 <= 71 <= 47 <= {62, 188}
     

C. Acyclic Graph

   In order for the graph to converge it needs to be shown that it is acyclic.
   This section describes what is required to build an acyclic tree.

      notation:  |S| = Number of elements in a set, S.
   

   from:  James Aspnes on Graph Theory
   also:  Notes on Discrete Mathematics

      A graph is a tree if and only if there is exactly one simple path
      between any two distinct vertices.

      Graphs are represented as ordered pairs G = (V,E), where V is a set of
      vertices and E a set of edges.

      A tree is an acyclic connected graph. We can show by induction on
      the number of vertices in G that G is a tree if and only if it is
      connected and has exactly |V|-1 edges.

      Any connected graph G = (V,E) has |E| = |V|-1.


   When construction the tree the root has:
 
      8 ==> 2 ==> 1                3 vertices and 2 edges


   Each node that is added has either 1 or 2 unique descendants.

      Adding a node with one descendant adds 1 vertex and 1 edge.
      Adding a node with two descendant adds 2 vertices and 2 edges.


   Consequently:  |E| = |V|-1


VI. Complete Tree

   If a tree can constructed covering all possible transition paths then the
   the root value, two, is always reachable.  A proof requires that each step
   in the construction is provably correct.


A. Bridge Four-By Chains To The Root Path

   In order to build an initial framework a subtree can be constructed
   consisting of Four-By chains attached by bridge nodes.


1. Root Path

   The root path chains edges with:  2*4^k  where integer k >= 0
     As a recursive series this is:  S0 = 2; S' = S * 4

         2 <= 8 <= 32 <= 128 <= 512 <= 2048 <=  8_192 <= 32_768

   Lemma:  The series representing the root path converges to two.


2. Bridge Four-By chains

   Every third node in the root path (2*64^k; k>0) can be bridged to a
   Four-By chain to form a tree:

                   170 - 680 - 2720 - 10_880 - 43_520 - 174_080 - 696_320 ...
                    |
      2 - 8 - 32 - 128 - 512 - 2048 -  8_192 - 32_768 - 131_072 - 524_288 ...
                                         |                           |
                                         |                        699_050 ...
                                         |
                                      10_922 - 43_688 - 174_752 - 699_008 ...


   The input value of the bridge node is:  (Output*4-2)/3
                             or with k>0:  [(2*64^k)*4-2]/3 = [8*64^k-2]/3

   The series for each chain is:  S0 = [8*64^k-2]/3; S' = S * 4


3. Recusively Bridge Four-By chains

   Within each of the bridged chains are values that can be bridged to
   additional Four-By chains.  A partial tree is:

                                                                  1_650_218 ...
                                                                     |
                                               77_354 - 309_416 - 1_237_664 ...
                                                 |
                               3626 - 14_504 - 58_016 - 232_064 - 928_256 ...
                                 |
                                 |                              2_200_706 ...
                                 |                                   |
                                 |                              1_650_530 ...
                                 |                                   |
                                 |                              1_237_898 ...
                                 |                                   |
                                 |                      232_106 - 928_424 ...
                                 |                         |
                   170 - 680 - 2720 - 10_880 - 43_520 - 174_080 - 696_320 ...
                    |
      2 - 8 - 32 - 128 - 512 - 2048 -  8_192 - 32_768 - 131_072 - 524_288 ...
                                         |                           |
                                         |                        699_050 ...
                                         |                           |
                                         |                        932_066 ...
                                         |
                                      10_922 - 43_688 - 174_752 - 699_008 ...
                                                 |
                                               58_250 - 233_000 - 932_000 ...
                                                 |
                                               77_666 - 310_664 - 1_242_656 ...
                                                           |
                                                        414_218 - 1_656_872 ...
                                                           |
                                                        552_290 - 2_209_160 ...


   Bridgable outputs meet the condition:  [ (Output*4-2)/3 ] % 3 = 2
   These are added recursively to complete the subtree.


B. Things To Do

   This section on completeness is incomplete.
   It needs to be proven that the tree in the previous section converges to 2.
   It remains to be shown that all numbers n % 3 = 2 form a connected tree.

   The tree that results from the original series is very irregular.
   This makes it difficult to show completeness.

   The tree that is generated with the revised series has a more regular
   graph with fewer nodes.  Success or failure depends on how it is formally
   constructed.  Given past efforts this is always a very long shot.


ADDENDUM.  Original Series in Reverse
 
   For reference, using the original series the reverse mapping is:

     Output       1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16

    (Output-1)/3              1                       3                       5 
     Output*2     2   4   6   8  10  12  14  16  18  20  22  24  26  28  30  32


                           / 1
                           | 2
                           \ 4
                             8
         ------------------ 16 --------------------
         5                                       32
     -- 10 --------------              --------- 64 ----
     3                 20              21            128
     6       --------- 40 ----         42       ---- 256 ---------
    12       13             80         84       85             512
    24       26        --- 160 ----   168      170       ---- 1024 -------
    48       52        53       320   336      340       341          2048
    96      104   --- 106 ---   640   672      680   --- 682 ---  --- 4096 ----
   192      208   35      212  1280  1344     1360   227    1364  1365     8192


   This tree has a less regular structure that makes it difficult to manipulate.
   Consequently it is difficult to show that all numbers are included in the
   tree.