In this worksheet we'll explore creating the tree from the $3n+1$ conjecture.
A graph is a dictionary containing pairs: $v$: L where $v$ is a vertex, and L is a list of vertices adjacent to $v$
|
![]() |
|
![]() |
|
{2: [4], 3: [6], 4: [1, 8], 5: [10], 6: [12], 7: [2, 14], 8: [16], 9: [18]} {2: [4], 3: [6], 4: [1, 8], 5: [10], 6: [12], 7: [2, 14], 8: [16], 9: [18]} |
|
|
|
![]() |
True True |
![]() |
|
|
![]() |
|
![]() |
|
![]() |
We will create a tree structure, a dictionary of the vertices and their children, level by level.
We'll keep track of which vertices are on which level by a list of lists, L=[[1],[2],[4],[8],[16],[5,32],...]
As we traverse the current level, we'll examine each vertex and see whether it has one child or two,
and update the edges of the tree appropriately.
How to check if $n \equiv 4 \mod 6$
True True |
False False |
|
[[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, 17, 104, 106, 640, 672, 113, 680, 682, 4096], [192, 34, 208, 35, 212, 213, 1280, 1344, 226, 1360, 227, 1364, 1365, 8192], [384, 11, 68, 69, 416, 70, 424, 426, 2560, 2688, 75, 452, 453, 2720, 454, 2728, 2730, 16384], [768, 22, 136, 138, 832, 23, 140, 141, 848, 852, 853, 5120, 5376, 150, 904, 906, 5440, 151, 908, 909, 5456, 5460, 5461, 32768]] [[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, 17, 104, 106, 640, 672, 113, 680, 682, 4096], [192, 34, 208, 35, 212, 213, 1280, 1344, 226, 1360, 227, 1364, 1365, 8192], [384, 11, 68, 69, 416, 70, 424, 426, 2560, 2688, 75, 452, 453, 2720, 454, 2728, 2730, 16384], [768, 22, 136, 138, 832, 23, 140, 141, 848, 852, 853, 5120, 5376, 150, 904, 906, 5440, 151, 908, 909, 5456, 5460, 5461, 32768]] |
|
![]() |
{3: [6], 5: [10], 6: [12], 8: [16], 10: [3, 20], 12: [24], 13: [26], 16: [5, 32], 20: [40], 21: [42], 32: [64], 40: [13, 80], 42: [84], 64: [21, 128], 80: [160], 84: [168], 85: [170], 128: [256], 256: [85, 512], 512: [1024]} {3: [6], 5: [10], 6: [12], 8: [16], 10: [3, 20], 12: [24], 13: [26], 16: [5, 32], 20: [40], 21: [42], 32: [64], 40: [13, 80], 42: [84], 64: [21, 128], 80: [160], 84: [168], 85: [170], 128: [256], 256: [85, 512], 512: [1024]} |
![]() |
![]() |
|
2 2 |
0 0 |
7 7 |
19 19 |
17 17 |
7 7 |
111 111 |
26 26 |
|
![]() |
|
![]() |
|
(0.693147180559945, 0.405465108108164) (0.693147180559945, 0.405465108108164) |
Define the function $g(n)$ to be $n/2$ if $n$ is even, and $(3n+1)/2$ if $n$ is odd.
We can model the behaviour of $\log(g(n))$ by a random walk $X$ where $X(t)$ is increased by $\log(2.)$ or decreased by $\log(3/2)$ at each step. How long until $X$ reaches 0?
On average, each step decreases $X$ by $\log(2)-\log(3/2) = $\log(4/3)$,
so the number of steps should be around $\log(n)/\log(4/3)$.
Toss a fair coin $n$ times; let $Y=$ number of heads. $$ Pr(Y=k) =\binom{n}{k} 2^{-n} $$
Let's try some $Pr(Y=k) =\binom{n}{k} 2^{-n}$ mode.
|
![]() |
|
2 2 |
70 70 |
|
|
|
![]() |
|