Trees

655 days ago by calkin

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$
d = {0: [1,4,5], 1: [2,6], 2: [3,7], 3: [4,8], 4: [9], 5: [7, 8], 6: [8,9], 7: [9]} G = Graph(d) plot(G) 
       
show(G) 
       
G=Graph(d) 
       
G 
       
CollatzTree={} for i in srange(2,10): if i%3==1: CollatzTree.update({i:[(i-1)/3,2*i]}) else: CollatzTree.update({i:[2*i]}) 
       
print(CollatzTree) 
        
{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]}
CollatzTree.update({16:[5,8]}) CollatzTree.update( {3:[6,10] }) CollatzTree.update( {9:[18,28] }) CollatzTree.update({14:[28]}) 
       
T=Graph(CollatzTree) 
       
from sage.graphs.graph_plot import GraphPlot 
       
T.show(layout='tree', tree_root=1) 
       
T.is_tree() 
        
True
True
show(T) 
       
CollatzTree={} for i in srange(1,27): a=i while a>1: if is_even(a): #if a<50: CollatzTree.update({a:[a/2]}) a=a/2 else: #if a<50: CollatzTree.update({a:[3*a+1]}) a=3*a+1 
       
T=Graph(CollatzTree) 
       
show(T) 
       
x=T.graphplot(layout='tree', tree_root=1,tree_orientation='up') 
       
x.show(figsize=[25,20]) 
       
sage.graphs.graph_plot.DEFAULT_SHOW_OPTIONS['figsize'] = [10,10] 
       
plot(x,figsize=[8,8]) 
       

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$
n=16 n%6 == 4 
        
True
True
n=15 n%6==4 
        
False
False
L=[[1],[2],[4],[8]] level_sizes=[1,1,1,1] T={1:[2],2:[4],4:[8]} for j in srange(3,45): next_level=[] for v in L[j]: if v%6==4: T.update({v:[(v-1)/3,2*v]}) next_level+=[(v-1)/3,2*v] else: T.update({v:[2*v]}) next_level.append(2*v) L.append(next_level) level_sizes.append(len(next_level)) 
       
print(L) 
        
[[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]]
show(level_sizes) 
       
CollatzTree=Graph(T) x=CollatzTree.graphplot(layout='tree', tree_root=1,tree_orientation='up') plot(x,figsize=[8,8]) 
       
 
        
{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]}
list_plot(level_sizes) 
       
list_plot_semilogy(level_sizes) 
       
def collatz(n): counter=0 while n>1: if is_even(n): n=n/2 else: n=3*n+1 counter+=1 return(counter) 
       
collatz(4) 
        
2
2
collatz(1) 
        
0
0
collatz(3) 
        
7
7
collatz(9) 
        
19
19
collatz(15) 
        
17
17
collatz(21) 
        
7
7
collatz(27) 
        
111
111
collatz(33) 
        
26
26
threes=[] for i in srange(200): a=collatz(6*i+3) threes.append([6*i+3,a]) 
       
list_plot(threes) 
       
all_points=[] for j in srange(1,30000): all_points.append([j,collatz(j)]) 
       
list_plot(all_points) 
       
 
       
print(log(2.),log(3/2.)) 
        
(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.
Prob_List =[] n=400 for k in srange(n+1): Prob_List.append((binomial(n,k)*2^(-n)).n()) 
       
list_plot(Prob_List) 
       
def adjusted_collatz(n): counter=0 # Counts the number of steps for the modified g(n) to reach 1 if n==1: return(0) while n>1: counter+=1 if is_even(n): n=(n/2) else: n=((3*n+1)/2) return(counter) 
       
adjusted_collatz(4) 
        
2
2
adjusted_collatz(27) 
        
70
70
all_points=[] for j in srange(1,30000): all_points.append([j,adjusted_collatz(j)]) 
       
A=list_plot(all_points) 
       
B=plot(2*log(x)/log(4/3), x,1,30000,color='red') 
       
show(A+B)