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.