Skip to content

Instantly share code, notes, and snippets.

@jakelevi1996

jakelevi1996/diagram_fm.py

Last active July 31, 2023 22:35
Show Gist options
  • Save jakelevi1996/db0e307905aa5aab86f793227d2be597 to your computer and use it in GitHub Desktop.
Save jakelevi1996/db0e307905aa5aab86f793227d2be597 to your computer and use it in GitHub Desktop.
Download ZIP
Make tables and trees for recursive functions defined in Chapter 5 of GEB
Raw
diagram_fm.py
from jutility import util
import tree
def diagram_fm(n_max, printer):
table = util.Table(
util.Column("n", width=10, title="n"),
util.Column("f_n", width=10, title="F(n)"),
util.Column("m_n", width=10, title="M(n)"),
util.Column("m_f_n", width=10, title="M(F(n))"),
util.Column("f_m_n", width=10, title="F(M(n))"),
printer=printer,
)
f = {0: 1}
m = {0: 0}
table.update(n=0, f_n=f[0], m_n=m[0])
for n in range(1, n_max + 1):
m[n] = n - f[m[n - 1]]
f[n] = n - m[f[n - 1]]
table.update(n=n, f_n=f[n], m_n=m[n], m_f_n=m[f[n]], f_m_n=f[m[n]])
return table
if __name__ == "__main__":
printer = util.Printer("diagram_fm.txt", ".")
table = diagram_fm(100, printer)
tree_dict = tree.list_to_tree_dict(table.get_data("m_n"))
tree.print_tree_dict(tree_dict, 1, printer)
tree_dict = tree.list_to_tree_dict(table.get_data("f_n"))
tree.print_tree_dict(tree_dict, 2, printer)
Raw
diagram_fm.txt
n | F(n) | M(n) | M(F(n)) | F(M(n))
---------- | ---------- | ---------- | ---------- | ----------
0 | 1 | 0 | |
1 | 1 | 0 | 0 | 1
2 | 2 | 1 | 1 | 1
3 | 2 | 2 | 1 | 2
4 | 3 | 2 | 2 | 2
5 | 3 | 3 | 2 | 2
6 | 4 | 4 | 2 | 3
7 | 5 | 4 | 3 | 3
8 | 5 | 5 | 3 | 3
9 | 6 | 6 | 4 | 4
10 | 6 | 6 | 4 | 4
11 | 7 | 7 | 4 | 5
12 | 8 | 7 | 5 | 5
13 | 8 | 8 | 5 | 5
14 | 9 | 9 | 6 | 6
15 | 9 | 9 | 6 | 6
16 | 10 | 10 | 6 | 6
17 | 11 | 11 | 7 | 7
18 | 11 | 11 | 7 | 7
19 | 12 | 12 | 7 | 8
20 | 13 | 12 | 8 | 8
21 | 13 | 13 | 8 | 8
22 | 14 | 14 | 9 | 9
23 | 14 | 14 | 9 | 9
24 | 15 | 15 | 9 | 9
25 | 16 | 16 | 10 | 10
26 | 16 | 16 | 10 | 10
27 | 17 | 17 | 11 | 11
28 | 17 | 17 | 11 | 11
29 | 18 | 18 | 11 | 11
30 | 19 | 19 | 12 | 12
31 | 19 | 19 | 12 | 12
32 | 20 | 20 | 12 | 13
33 | 21 | 20 | 13 | 13
34 | 21 | 21 | 13 | 13
35 | 22 | 22 | 14 | 14
36 | 22 | 22 | 14 | 14
37 | 23 | 23 | 14 | 14
38 | 24 | 24 | 15 | 15
39 | 24 | 24 | 15 | 15
40 | 25 | 25 | 16 | 16
41 | 25 | 25 | 16 | 16
42 | 26 | 26 | 16 | 16
43 | 27 | 27 | 17 | 17
44 | 27 | 27 | 17 | 17
45 | 28 | 28 | 17 | 17
46 | 29 | 29 | 18 | 18
47 | 29 | 29 | 18 | 18
48 | 30 | 30 | 19 | 19
49 | 30 | 30 | 19 | 19
50 | 31 | 31 | 19 | 19
51 | 32 | 32 | 20 | 20
52 | 32 | 32 | 20 | 20
53 | 33 | 33 | 20 | 21
54 | 34 | 33 | 21 | 21
55 | 34 | 34 | 21 | 21
56 | 35 | 35 | 22 | 22
57 | 35 | 35 | 22 | 22
58 | 36 | 36 | 22 | 22
59 | 37 | 37 | 23 | 23
60 | 37 | 37 | 23 | 23
61 | 38 | 38 | 24 | 24
62 | 38 | 38 | 24 | 24
63 | 39 | 39 | 24 | 24
64 | 40 | 40 | 25 | 25
65 | 40 | 40 | 25 | 25
66 | 41 | 41 | 25 | 25
67 | 42 | 42 | 26 | 26
68 | 42 | 42 | 26 | 26
69 | 43 | 43 | 27 | 27
70 | 43 | 43 | 27 | 27
71 | 44 | 44 | 27 | 27
72 | 45 | 45 | 28 | 28
73 | 45 | 45 | 28 | 28
74 | 46 | 46 | 29 | 29
75 | 46 | 46 | 29 | 29
76 | 47 | 47 | 29 | 29
77 | 48 | 48 | 30 | 30
78 | 48 | 48 | 30 | 30
79 | 49 | 49 | 30 | 30
80 | 50 | 50 | 31 | 31
81 | 50 | 50 | 31 | 31
82 | 51 | 51 | 32 | 32
83 | 51 | 51 | 32 | 32
84 | 52 | 52 | 32 | 32
85 | 53 | 53 | 33 | 33
86 | 53 | 53 | 33 | 33
87 | 54 | 54 | 33 | 34
88 | 55 | 54 | 34 | 34
89 | 55 | 55 | 34 | 34
90 | 56 | 56 | 35 | 35
91 | 56 | 56 | 35 | 35
92 | 57 | 57 | 35 | 35
93 | 58 | 58 | 36 | 36
94 | 58 | 58 | 36 | 36
95 | 59 | 59 | 37 | 37
96 | 59 | 59 | 37 | 37
97 | 60 | 60 | 37 | 37
98 | 61 | 61 | 38 | 38
99 | 61 | 61 | 38 | 38
100 | 62 | 62 | 38 | 38
89 90 91 92 93 94 95 96 97 98 99 100
| | | | | | | | | | | |
| ------ | ------ ------ | ------ |
| | | | | | | |
55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| --------- | --------- --------- | ------ | ------ ------ | ------ ------ | ------ | ------ ------ | ------ ------
| | | | | | | | | | | | | | | | | | | | |
34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
| | | | | | | | | | | | | | | | | | | | |
| ------------ | ---------- --------- | --------- | --------- --------- | --------- -----------
| | | | | | | | | | | | |
21 22 23 24 25 26 27 28 29 30 31 32 33
| | | | | | | | | | | | |
| --------------------- | ------------ ------------ | ------------ -----------------
| | | | | | | |
13 14 15 16 17 18 19 20
| | | | | | | |
| ------------------------------ | --------------------- -----------------------------
| | | | |
8 9 10 11 12
| | | | |
| ------------------------------------- ---------------------------------------------
| | |
5 6 7
| | |
| ----------------------------------------------------------------------------
| |
3 4
| |
------------------------------------------------------------------------------------------------
|
2
|
|
|
1
|
90 91 92 93 94 95 96 97 98 99 100
| | | | | | | | | | |
------ | ------ ------ | ------ |
| | | | | | |
56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
--------- | --------- --------- | ------ | ------ ------ | ------ ------ | ------ | ------ ------ | ------ | ------
| | | | | | | | | | | | | | | | | | | | |
35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
| | | | | | | | | | | | | | | | | | | | |
------------ | ---------- --------- | --------- | --------- --------- | --------- | --------
| | | | | | | | | | | | |
22 23 24 25 26 27 28 29 30 31 32 33 34
| | | | | | | | | | | | |
--------------------- | ------------ ------------ | ------------ | ------------
| | | | | | | |
14 15 16 17 18 19 20 21
| | | | | | | |
------------------------------ | --------------------- | -----------------
| | | | |
9 10 11 12 13
| | | | |
------------------------------------- | -----------------------------
| | |
6 7 8
| | |
| ---------------------------------------------
| |
4 5
| |
----------------------------------------------------------------------------
|
3
|
|
|
2
|
Raw
diagram_g.py
from jutility import util
import tree
def diagram_g(n_max, printer):
table = util.Table(
util.Column("n", width=10, title="n"),
util.Column("t_n", width=10, title="Type(n)"),
util.Column("g_n", width=10, title="G(n)"),
util.Column("t_g_n", width=10, title="Type(G(n))"),
util.Column("g_g_n", width=10, title="G(G(n))"),
util.Column("t_g_g_n", width=10, title="Type(G(G(n)))"),
printer=printer,
)
g = {0: 0}
t = {0: "?", 1: "L"}
table.update(n=0, g_n=g[0], g_g_n=g[g[0]])
for n in range(1, n_max + 1):
g[n] = n - g[g[n - 1]]
if t[n - 1] == "L":
t[n] = "R"
elif t[g[n]] == "R":
t[n] = "M"
else:
t[n] = "L"
assert g[n] - g[n - 1] == (0 if (t[n - 1] == "L") else 1)
assert g[g[n]] - g[g[n - 1]] == (1 if (t[n] == "L") else 0)
table.update(
n=n,
t_n=t[n],
g_n=g[n],
t_g_n=t[g[n]],
g_g_n=g[g[n]],
t_g_g_n=t[g[g[n]]],
)
return table
if __name__ == "__main__":
printer = util.Printer("diagram_g.txt", ".")
table = diagram_g(100, printer)
tree_dict = tree.list_to_tree_dict(table.get_data("g_n"))
tree.print_tree_dict(tree_dict, 1, printer)
Raw
diagram_g.txt
n | Type(n) | G(n) | Type(G(n)) | G(G(n)) | Type(G(G(n)))
---------- | ---------- | ---------- | ---------- | ---------- | -------------
0 | | 0 | | 0 |
1 | L | 1 | L | 1 | L
2 | R | 1 | L | 1 | L
3 | M | 2 | R | 1 | L
4 | L | 3 | M | 2 | R
5 | R | 3 | M | 2 | R
6 | L | 4 | L | 3 | M
7 | R | 4 | L | 3 | M
8 | M | 5 | R | 3 | M
9 | L | 6 | L | 4 | L
10 | R | 6 | L | 4 | L
11 | M | 7 | R | 4 | L
12 | L | 8 | M | 5 | R
13 | R | 8 | M | 5 | R
14 | L | 9 | L | 6 | L
15 | R | 9 | L | 6 | L
16 | M | 10 | R | 6 | L
17 | L | 11 | M | 7 | R
18 | R | 11 | M | 7 | R
19 | L | 12 | L | 8 | M
20 | R | 12 | L | 8 | M
21 | M | 13 | R | 8 | M
22 | L | 14 | L | 9 | L
23 | R | 14 | L | 9 | L
24 | M | 15 | R | 9 | L
25 | L | 16 | M | 10 | R
26 | R | 16 | M | 10 | R
27 | L | 17 | L | 11 | M
28 | R | 17 | L | 11 | M
29 | M | 18 | R | 11 | M
30 | L | 19 | L | 12 | L
31 | R | 19 | L | 12 | L
32 | M | 20 | R | 12 | L
33 | L | 21 | M | 13 | R
34 | R | 21 | M | 13 | R
35 | L | 22 | L | 14 | L
36 | R | 22 | L | 14 | L
37 | M | 23 | R | 14 | L
38 | L | 24 | M | 15 | R
39 | R | 24 | M | 15 | R
40 | L | 25 | L | 16 | M
41 | R | 25 | L | 16 | M
42 | M | 26 | R | 16 | M
43 | L | 27 | L | 17 | L
44 | R | 27 | L | 17 | L
45 | M | 28 | R | 17 | L
46 | L | 29 | M | 18 | R
47 | R | 29 | M | 18 | R
48 | L | 30 | L | 19 | L
49 | R | 30 | L | 19 | L
50 | M | 31 | R | 19 | L
51 | L | 32 | M | 20 | R
52 | R | 32 | M | 20 | R
53 | L | 33 | L | 21 | M
54 | R | 33 | L | 21 | M
55 | M | 34 | R | 21 | M
56 | L | 35 | L | 22 | L
57 | R | 35 | L | 22 | L
58 | M | 36 | R | 22 | L
59 | L | 37 | M | 23 | R
60 | R | 37 | M | 23 | R
61 | L | 38 | L | 24 | M
62 | R | 38 | L | 24 | M
63 | M | 39 | R | 24 | M
64 | L | 40 | L | 25 | L
65 | R | 40 | L | 25 | L
66 | M | 41 | R | 25 | L
67 | L | 42 | M | 26 | R
68 | R | 42 | M | 26 | R
69 | L | 43 | L | 27 | L
70 | R | 43 | L | 27 | L
71 | M | 44 | R | 27 | L
72 | L | 45 | M | 28 | R
73 | R | 45 | M | 28 | R
74 | L | 46 | L | 29 | M
75 | R | 46 | L | 29 | M
76 | M | 47 | R | 29 | M
77 | L | 48 | L | 30 | L
78 | R | 48 | L | 30 | L
79 | M | 49 | R | 30 | L
80 | L | 50 | M | 31 | R
81 | R | 50 | M | 31 | R
82 | L | 51 | L | 32 | M
83 | R | 51 | L | 32 | M
84 | M | 52 | R | 32 | M
85 | L | 53 | L | 33 | L
86 | R | 53 | L | 33 | L
87 | M | 54 | R | 33 | L
88 | L | 55 | M | 34 | R
89 | R | 55 | M | 34 | R
90 | L | 56 | L | 35 | L
91 | R | 56 | L | 35 | L
92 | M | 57 | R | 35 | L
93 | L | 58 | M | 36 | R
94 | R | 58 | M | 36 | R
95 | L | 59 | L | 37 | M
96 | R | 59 | L | 37 | M
97 | M | 60 | R | 37 | M
98 | L | 61 | L | 38 | L
99 | R | 61 | L | 38 | L
100 | M | 62 | R | 38 | L
90 91 92 93 94 95 96 97 98 99 100
| | | | | | | | | | |
------ | ------ ------ | ------ |
| | | | | | |
56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
--------- | --------- --------- | ------ | ------ ------ | ------ ------ | ------ | ------ ------ | ------ | ------
| | | | | | | | | | | | | | | | | | | | |
35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
| | | | | | | | | | | | | | | | | | | | |
------------ | ---------- --------- | --------- | --------- --------- | --------- --------- |
| | | | | | | | | | | | |
22 23 24 25 26 27 28 29 30 31 32 33 34
| | | | | | | | | | | | |
--------------------- | ------------ ------------ | ------------ | ------------
| | | | | | | |
14 15 16 17 18 19 20 21
| | | | | | | |
------------------------------ | --------------------- --------------------- |
| | | | |
9 10 11 12 13
| | | | |
------------------------------------- | -------------------------------
| | |
6 7 8
| | |
------------------------------------------------------ |
| |
4 5
| |
-----------------------------------------------------------------------------------
|
3
|
|
|
2
|
|
|
1
|
Raw
diagram_g_flipped.py
from jutility import util
import tree
def diagram_g_flipped(n_max, printer):
table = util.Table(
util.Column("n", width=10, title="n"),
util.Column("t_n", width=10, title="Type(n)"),
util.Column("g_n", width=10, title="G(n)"),
util.Column("t_g_n", width=10, title="Type(G(n))"),
util.Column("g_g_n", width=10, title="G(G(n))"),
util.Column("t_g_g_n", width=10, title="Type(G(G(n)))"),
printer=printer,
)
g = {0: 0, 1: 1, 2: 1, 3: 2}
t = {2: "?", 3: "M"}
for n in range(4):
table.update(n=n, g_n=g[n], g_g_n=g[g[n]])
for n in range(4, n_max + 1):
g[n] = n + 1 - g[g[n - 1] + 1]
if t[n - 1] == "L":
t[n] = "R"
elif t[g[n]] == "L":
t[n] = "M"
else:
t[n] = "L"
if n > 4:
assert g[n] - g[n - 1] == (0 if (t[n - 1] == "L") else 1)
assert g[g[n]] - g[g[n - 1]] == (1 if (t[n - 1] == "R") else 0)
assert g[g[n]] - g[g[n - 1]] == (1 if (t[n - 2] == "L") else 0)
assert g[g[n]] - g[g[n - 1]] == 1 - (g[n - 1] - g[n - 2])
assert g[g[n]] + g[n - 1] - n == g[g[n - 1]] + g[n - 2] - (n - 1)
assert g[n - 1] == n - g[g[n]]
assert g[g[n]] == g[g[n - 2] + 1]
assert g[n] == n + 1 - g[g[n - 1] + 1]
table.update(
n=n,
t_n=t[n],
g_n=g[n],
t_g_n=t[g[n]],
g_g_n=g[g[n]],
t_g_g_n=t[g[g[n]]],
)
return table
if __name__ == "__main__":
printer = util.Printer("diagram_g_flipped.txt", ".")
table = diagram_g_flipped(100, printer)
tree_dict = tree.list_to_tree_dict(table.get_data("g_n"))
tree.print_tree_dict(tree_dict, 1, printer)
Raw
diagram_g_flipped.txt
n | Type(n) | G(n) | Type(G(n)) | G(G(n)) | Type(G(G(n)))
---------- | ---------- | ---------- | ---------- | ---------- | -------------
0 | | 0 | | 0 |
1 | | 1 | | 1 |
2 | | 1 | | 1 |
3 | | 2 | | 1 |
4 | L | 3 | M | 2 | ?
5 | R | 3 | M | 2 | ?
6 | M | 4 | L | 3 | M
7 | L | 5 | R | 3 | M
8 | R | 5 | R | 3 | M
9 | L | 6 | M | 4 | L
10 | R | 6 | M | 4 | L
11 | M | 7 | L | 5 | R
12 | L | 8 | R | 5 | R
13 | R | 8 | R | 5 | R
14 | M | 9 | L | 6 | M
15 | L | 10 | R | 6 | M
16 | R | 10 | R | 6 | M
17 | L | 11 | M | 7 | L
18 | R | 11 | M | 7 | L
19 | M | 12 | L | 8 | R
20 | L | 13 | R | 8 | R
21 | R | 13 | R | 8 | R
22 | L | 14 | M | 9 | L
23 | R | 14 | M | 9 | L
24 | M | 15 | L | 10 | R
25 | L | 16 | R | 10 | R
26 | R | 16 | R | 10 | R
27 | M | 17 | L | 11 | M
28 | L | 18 | R | 11 | M
29 | R | 18 | R | 11 | M
30 | L | 19 | M | 12 | L
31 | R | 19 | M | 12 | L
32 | M | 20 | L | 13 | R
33 | L | 21 | R | 13 | R
34 | R | 21 | R | 13 | R
35 | M | 22 | L | 14 | M
36 | L | 23 | R | 14 | M
37 | R | 23 | R | 14 | M
38 | L | 24 | M | 15 | L
39 | R | 24 | M | 15 | L
40 | M | 25 | L | 16 | R
41 | L | 26 | R | 16 | R
42 | R | 26 | R | 16 | R
43 | L | 27 | M | 17 | L
44 | R | 27 | M | 17 | L
45 | M | 28 | L | 18 | R
46 | L | 29 | R | 18 | R
47 | R | 29 | R | 18 | R
48 | M | 30 | L | 19 | M
49 | L | 31 | R | 19 | M
50 | R | 31 | R | 19 | M
51 | L | 32 | M | 20 | L
52 | R | 32 | M | 20 | L
53 | M | 33 | L | 21 | R
54 | L | 34 | R | 21 | R
55 | R | 34 | R | 21 | R
56 | L | 35 | M | 22 | L
57 | R | 35 | M | 22 | L
58 | M | 36 | L | 23 | R
59 | L | 37 | R | 23 | R
60 | R | 37 | R | 23 | R
61 | M | 38 | L | 24 | M
62 | L | 39 | R | 24 | M
63 | R | 39 | R | 24 | M
64 | L | 40 | M | 25 | L
65 | R | 40 | M | 25 | L
66 | M | 41 | L | 26 | R
67 | L | 42 | R | 26 | R
68 | R | 42 | R | 26 | R
69 | M | 43 | L | 27 | M
70 | L | 44 | R | 27 | M
71 | R | 44 | R | 27 | M
72 | L | 45 | M | 28 | L
73 | R | 45 | M | 28 | L
74 | M | 46 | L | 29 | R
75 | L | 47 | R | 29 | R
76 | R | 47 | R | 29 | R
77 | L | 48 | M | 30 | L
78 | R | 48 | M | 30 | L
79 | M | 49 | L | 31 | R
80 | L | 50 | R | 31 | R
81 | R | 50 | R | 31 | R
82 | M | 51 | L | 32 | M
83 | L | 52 | R | 32 | M
84 | R | 52 | R | 32 | M
85 | L | 53 | M | 33 | L
86 | R | 53 | M | 33 | L
87 | M | 54 | L | 34 | R
88 | L | 55 | R | 34 | R
89 | R | 55 | R | 34 | R
90 | M | 56 | L | 35 | M
91 | L | 57 | R | 35 | M
92 | R | 57 | R | 35 | M
93 | L | 58 | M | 36 | L
94 | R | 58 | M | 36 | L
95 | M | 59 | L | 37 | R
96 | L | 60 | R | 37 | R
97 | R | 60 | R | 37 | R
98 | L | 61 | M | 38 | L
99 | R | 61 | M | 38 | L
100 | M | 62 | L | 39 | R
90 91 92 93 94 95 96 97 98 99 100
| | | | | | | | | | |
| ------ ------ | ------ ------ |
| | | | | | |
56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
-------- | -------- | ------ ------ | ------ | ------ ------ | ------ ------ | ------ | ------ ------ | ------
| | | | | | | | | | | | | | | | | | | | |
35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
| | | | | | | | | | | | | | | | | | | | |
| ------------ ----------- | -------- -------- | -------- | -------- -------- | --------
| | | | | | | | | | | | |
22 23 24 25 26 27 28 29 30 31 32 33 34
| | | | | | | | | | | | |
-------------------- | ------------ | ------------ ------------ | ------------
| | | | | | | |
14 15 16 17 18 19 20 21
| | | | | | | |
| --------------------- -------------------- | --------------------
| | | | |
9 10 11 12 13
| | | | |
---------------------------------------------- | -------------------------------
| | |
6 7 8
| | |
| ---------------------------------------------------
| |
4 5
| |
-----------------------------------------------------------------------------------------
|
3
|
|
|
2
|
|
|
1
|
Raw
diagram_h.py
from jutility import util
import tree
def diagram_h(n_max, printer):
table = util.Table(
util.Column("n", width=10, title="n"),
util.Column("t_n", width=10, title="Type(n)"),
util.Column("h_n", width=10, title="H(n)"),
util.Column("t_h_n", width=10, title="Type(H(n))"),
util.Column("h_h_n", width=10, title="H(H(n))"),
util.Column("t_h_h_n", width=10, title="Type(H(H(n)))"),
util.Column("h_h_h_n", width=10, title="H(H(H(n)))"),
util.Column("t_h_h_h_n", width=10, title="Type(H(H(H(n))))"),
printer=printer,
)
h = {0: 0}
t = {0: "?", 1: "L"}
table.update(n=0, h_n=h[0], h_h_n=h[h[0]], h_h_h_n=h[h[h[0]]])
for n in range(1, n_max + 1):
h[n] = n - h[h[h[n - 1]]]
if t[n - 1] == "L":
t[n] = "R"
elif t[h[n]] == "R":
t[n] = "M"
elif t[h[n]] == "M":
t[n] = "N"
else:
t[n] = "L"
assert h[n] - h[n - 1] == (0 if (t[n - 1] == "L") else 1)
assert h[h[h[n]]] - h[h[h[n - 1]]] == (1 if (t[n] == "L") else 0)
table.update(
n=n,
t_n=t[n],
h_n=h[n],
t_h_n=t[h[n]],
h_h_n=h[h[n]],
t_h_h_n=t[h[h[n]]],
h_h_h_n=h[h[h[n]]],
t_h_h_h_n=t[h[h[h[n]]]],
)
return table
if __name__ == "__main__":
printer = util.Printer("diagram_h.txt", ".")
table = diagram_h(100, printer)
tree_dict = tree.list_to_tree_dict(table.get_data("h_n"))
tree.print_tree_dict(tree_dict, 1, printer)
Raw
diagram_h.txt
n | Type(n) | H(n) | Type(H(n)) | H(H(n)) | Type(H(H(n))) | H(H(H(n))) | Type(H(H(H(n))))
---------- | ---------- | ---------- | ---------- | ---------- | ------------- | ---------- | ----------------
0 | | 0 | | 0 | | 0 |
1 | L | 1 | L | 1 | L | 1 | L
2 | R | 1 | L | 1 | L | 1 | L
3 | M | 2 | R | 1 | L | 1 | L
4 | N | 3 | M | 2 | R | 1 | L
5 | L | 4 | N | 3 | M | 2 | R
6 | R | 4 | N | 3 | M | 2 | R
7 | L | 5 | L | 4 | N | 3 | M
8 | R | 5 | L | 4 | N | 3 | M
9 | M | 6 | R | 4 | N | 3 | M
10 | L | 7 | L | 5 | L | 4 | N
11 | R | 7 | L | 5 | L | 4 | N
12 | M | 8 | R | 5 | L | 4 | N
13 | N | 9 | M | 6 | R | 4 | N
14 | L | 10 | L | 7 | L | 5 | L
15 | R | 10 | L | 7 | L | 5 | L
16 | M | 11 | R | 7 | L | 5 | L
17 | N | 12 | M | 8 | R | 5 | L
18 | L | 13 | N | 9 | M | 6 | R
19 | R | 13 | N | 9 | M | 6 | R
20 | L | 14 | L | 10 | L | 7 | L
21 | R | 14 | L | 10 | L | 7 | L
22 | M | 15 | R | 10 | L | 7 | L
23 | N | 16 | M | 11 | R | 7 | L
24 | L | 17 | N | 12 | M | 8 | R
25 | R | 17 | N | 12 | M | 8 | R
26 | L | 18 | L | 13 | N | 9 | M
27 | R | 18 | L | 13 | N | 9 | M
28 | M | 19 | R | 13 | N | 9 | M
29 | L | 20 | L | 14 | L | 10 | L
30 | R | 20 | L | 14 | L | 10 | L
31 | M | 21 | R | 14 | L | 10 | L
32 | N | 22 | M | 15 | R | 10 | L
33 | L | 23 | N | 16 | M | 11 | R
34 | R | 23 | N | 16 | M | 11 | R
35 | L | 24 | L | 17 | N | 12 | M
36 | R | 24 | L | 17 | N | 12 | M
37 | M | 25 | R | 17 | N | 12 | M
38 | L | 26 | L | 18 | L | 13 | N
39 | R | 26 | L | 18 | L | 13 | N
40 | M | 27 | R | 18 | L | 13 | N
41 | N | 28 | M | 19 | R | 13 | N
42 | L | 29 | L | 20 | L | 14 | L
43 | R | 29 | L | 20 | L | 14 | L
44 | M | 30 | R | 20 | L | 14 | L
45 | N | 31 | M | 21 | R | 14 | L
46 | L | 32 | N | 22 | M | 15 | R
47 | R | 32 | N | 22 | M | 15 | R
48 | L | 33 | L | 23 | N | 16 | M
49 | R | 33 | L | 23 | N | 16 | M
50 | M | 34 | R | 23 | N | 16 | M
51 | L | 35 | L | 24 | L | 17 | N
52 | R | 35 | L | 24 | L | 17 | N
53 | M | 36 | R | 24 | L | 17 | N
54 | N | 37 | M | 25 | R | 17 | N
55 | L | 38 | L | 26 | L | 18 | L
56 | R | 38 | L | 26 | L | 18 | L
57 | M | 39 | R | 26 | L | 18 | L
58 | N | 40 | M | 27 | R | 18 | L
59 | L | 41 | N | 28 | M | 19 | R
60 | R | 41 | N | 28 | M | 19 | R
61 | L | 42 | L | 29 | L | 20 | L
62 | R | 42 | L | 29 | L | 20 | L
63 | M | 43 | R | 29 | L | 20 | L
64 | N | 44 | M | 30 | R | 20 | L
65 | L | 45 | N | 31 | M | 21 | R
66 | R | 45 | N | 31 | M | 21 | R
67 | L | 46 | L | 32 | N | 22 | M
68 | R | 46 | L | 32 | N | 22 | M
69 | M | 47 | R | 32 | N | 22 | M
70 | L | 48 | L | 33 | L | 23 | N
71 | R | 48 | L | 33 | L | 23 | N
72 | M | 49 | R | 33 | L | 23 | N
73 | N | 50 | M | 34 | R | 23 | N
74 | L | 51 | L | 35 | L | 24 | L
75 | R | 51 | L | 35 | L | 24 | L
76 | M | 52 | R | 35 | L | 24 | L
77 | N | 53 | M | 36 | R | 24 | L
78 | L | 54 | N | 37 | M | 25 | R
79 | R | 54 | N | 37 | M | 25 | R
80 | L | 55 | L | 38 | L | 26 | L
81 | R | 55 | L | 38 | L | 26 | L
82 | M | 56 | R | 38 | L | 26 | L
83 | N | 57 | M | 39 | R | 26 | L
84 | L | 58 | N | 40 | M | 27 | R
85 | R | 58 | N | 40 | M | 27 | R
86 | L | 59 | L | 41 | N | 28 | M
87 | R | 59 | L | 41 | N | 28 | M
88 | M | 60 | R | 41 | N | 28 | M
89 | L | 61 | L | 42 | L | 29 | L
90 | R | 61 | L | 42 | L | 29 | L
91 | M | 62 | R | 42 | L | 29 | L
92 | N | 63 | M | 43 | R | 29 | L
93 | L | 64 | N | 44 | M | 30 | R
94 | R | 64 | N | 44 | M | 30 | R
95 | L | 65 | L | 45 | N | 31 | M
96 | R | 65 | L | 45 | N | 31 | M
97 | M | 66 | R | 45 | N | 31 | M
98 | L | 67 | L | 46 | L | 32 | N
99 | R | 67 | L | 46 | L | 32 | N
100 | M | 68 | R | 46 | L | 32 | N
89 90 91 92 93 94 95 96 97 98 99 100
| | | | | | | | | | | |
------ | | ------ ------ | ------ |
| | | | | | | |
61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88
| | | | | | | | | | | | | | | | | | | | | | | | | | | |
--------- | | --------- --------- | ------ | | ------ | | ------ ------ | | ------ ------ |
| | | | | | | | | | | | | | | | | | |
42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
| | | | | | | | | | | | | | | | | | |
---------- | | ---------- --------- | --------- | | --------- | | ---------
| | | | | | | | | | | | |
29 30 31 32 33 34 35 36 37 38 39 40 41
| | | | | | | | | | | | |
------------- | | ---------- ---------- | ---------- | |
| | | | | | | | |
20 21 22 23 24 25 26 27 28
| | | | | | | | |
--------------------- | | ------------- ------------- |
| | | | | |
14 15 16 17 18 19
| | | | | |
------------------------------ | | ---------------------
| | | |
10 11 12 13
| | | |
------------------------------------ | |
| | |
7 8 9
| | |
--------------------------------------------- |
| |
5 6
| |
---------------------------------------------------------------
|
4
|
|
|
3
|
|
|
2
|
|
|
1
|
Raw
diagram_h_flipped.py
from jutility import util
import tree
def diagram_h_flipped(n_max, printer):
table = util.Table(
util.Column("n", width=10, title="n"),
util.Column("t_n", width=10, title="Type(n)"),
util.Column("h_n", width=10, title="H(n)"),
util.Column("t_h_n", width=10, title="Type(H(n))"),
util.Column("h_h_n", width=10, title="H(H(n))"),
util.Column("t_h_h_n", width=10, title="Type(H(H(n)))"),
util.Column("h_h_h_n", width=10, title="H(H(H(n)))"),
util.Column("t_h_h_h_n", width=10, title="Type(H(H(H(n))))"),
printer=printer,
)
h = {0: 0, 1: 1, 2: 1, 3: 2, 4: 3}
t = {2: "?", 3: "?", 4: "N"}
for n in range(5):
table.update(n=n, h_n=h[n], h_h_n=h[h[n]], h_h_h_n=h[h[h[n]]])
for n in range(5, n_max + 1):
h[n] = n + 1 - h[h[h[n - 1] + 1]]
if t[n - 1] == "L":
t[n] = "R"
elif t[h[n]] == "L":
t[n] = "M"
elif t[h[n]] == "M":
t[n] = "N"
else:
t[n] = "L"
if n > 5:
assert h[n] - h[n-1] == (0 if (t[n-1] == "L") else 1)
assert h[h[h[n]]] - h[h[h[n-1]]] == (1 if (t[n-1] == "R") else 0)
assert h[h[h[n]]] - h[h[h[n-1]]] == (1 if (t[n-2] == "L") else 0)
assert h[h[h[n]]] - h[h[h[n-1]]] == 1 - (h[n-1] - h[n-2])
assert h[h[h[n]]] + h[n-1] - n == h[h[h[n-1]]] + h[n-2] - (n-1)
assert h[n-1] == n - h[h[h[n]]]
assert h[h[h[n]]] == h[h[h[n-2] + 1]]
assert h[n] == n + 1 - h[h[h[n-1] + 1]]
table.update(
n=n,
t_n=t[n],
h_n=h[n],
t_h_n=t[h[n]],
h_h_n=h[h[n]],
t_h_h_n=t[h[h[n]]],
h_h_h_n=h[h[h[n]]],
t_h_h_h_n=t[h[h[h[n]]]],
)
return table
if __name__ == "__main__":
printer = util.Printer("diagram_h_flipped.txt", ".")
table = diagram_h_flipped(100, printer)
tree_dict = tree.list_to_tree_dict(table.get_data("h_n"))
tree.print_tree_dict(tree_dict, 1, printer)
Raw
diagram_h_flipped.txt
n | Type(n) | H(n) | Type(H(n)) | H(H(n)) | Type(H(H(n))) | H(H(H(n))) | Type(H(H(H(n))))
---------- | ---------- | ---------- | ---------- | ---------- | ------------- | ---------- | ----------------
0 | | 0 | | 0 | | 0 |
1 | | 1 | | 1 | | 1 |
2 | | 1 | | 1 | | 1 |
3 | | 2 | | 1 | | 1 |
4 | | 3 | | 2 | | 1 |
5 | L | 4 | N | 3 | ? | 2 | ?
6 | R | 4 | N | 3 | ? | 2 | ?
7 | M | 5 | L | 4 | N | 3 | ?
8 | L | 6 | R | 4 | N | 3 | ?
9 | R | 6 | R | 4 | N | 3 | ?
10 | N | 7 | M | 5 | L | 4 | N
11 | M | 8 | L | 6 | R | 4 | N
12 | L | 9 | R | 6 | R | 4 | N
13 | R | 9 | R | 6 | R | 4 | N
14 | L | 10 | N | 7 | M | 5 | L
15 | R | 10 | N | 7 | M | 5 | L
16 | N | 11 | M | 8 | L | 6 | R
17 | M | 12 | L | 9 | R | 6 | R
18 | L | 13 | R | 9 | R | 6 | R
19 | R | 13 | R | 9 | R | 6 | R
20 | M | 14 | L | 10 | N | 7 | M
21 | L | 15 | R | 10 | N | 7 | M
22 | R | 15 | R | 10 | N | 7 | M
23 | L | 16 | N | 11 | M | 8 | L
24 | R | 16 | N | 11 | M | 8 | L
25 | N | 17 | M | 12 | L | 9 | R
26 | M | 18 | L | 13 | R | 9 | R
27 | L | 19 | R | 13 | R | 9 | R
28 | R | 19 | R | 13 | R | 9 | R
29 | N | 20 | M | 14 | L | 10 | N
30 | M | 21 | L | 15 | R | 10 | N
31 | L | 22 | R | 15 | R | 10 | N
32 | R | 22 | R | 15 | R | 10 | N
33 | M | 23 | L | 16 | N | 11 | M
34 | L | 24 | R | 16 | N | 11 | M
35 | R | 24 | R | 16 | N | 11 | M
36 | L | 25 | N | 17 | M | 12 | L
37 | R | 25 | N | 17 | M | 12 | L
38 | N | 26 | M | 18 | L | 13 | R
39 | M | 27 | L | 19 | R | 13 | R
40 | L | 28 | R | 19 | R | 13 | R
41 | R | 28 | R | 19 | R | 13 | R
42 | L | 29 | N | 20 | M | 14 | L
43 | R | 29 | N | 20 | M | 14 | L
44 | N | 30 | M | 21 | L | 15 | R
45 | M | 31 | L | 22 | R | 15 | R
46 | L | 32 | R | 22 | R | 15 | R
47 | R | 32 | R | 22 | R | 15 | R
48 | N | 33 | M | 23 | L | 16 | N
49 | M | 34 | L | 24 | R | 16 | N
50 | L | 35 | R | 24 | R | 16 | N
51 | R | 35 | R | 24 | R | 16 | N
52 | M | 36 | L | 25 | N | 17 | M
53 | L | 37 | R | 25 | N | 17 | M
54 | R | 37 | R | 25 | N | 17 | M
55 | L | 38 | N | 26 | M | 18 | L
56 | R | 38 | N | 26 | M | 18 | L
57 | N | 39 | M | 27 | L | 19 | R
58 | M | 40 | L | 28 | R | 19 | R
59 | L | 41 | R | 28 | R | 19 | R
60 | R | 41 | R | 28 | R | 19 | R
61 | M | 42 | L | 29 | N | 20 | M
62 | L | 43 | R | 29 | N | 20 | M
63 | R | 43 | R | 29 | N | 20 | M
64 | L | 44 | N | 30 | M | 21 | L
65 | R | 44 | N | 30 | M | 21 | L
66 | N | 45 | M | 31 | L | 22 | R
67 | M | 46 | L | 32 | R | 22 | R
68 | L | 47 | R | 32 | R | 22 | R
69 | R | 47 | R | 32 | R | 22 | R
70 | L | 48 | N | 33 | M | 23 | L
71 | R | 48 | N | 33 | M | 23 | L
72 | N | 49 | M | 34 | L | 24 | R
73 | M | 50 | L | 35 | R | 24 | R
74 | L | 51 | R | 35 | R | 24 | R
75 | R | 51 | R | 35 | R | 24 | R
76 | N | 52 | M | 36 | L | 25 | N
77 | M | 53 | L | 37 | R | 25 | N
78 | L | 54 | R | 37 | R | 25 | N
79 | R | 54 | R | 37 | R | 25 | N
80 | M | 55 | L | 38 | N | 26 | M
81 | L | 56 | R | 38 | N | 26 | M
82 | R | 56 | R | 38 | N | 26 | M
83 | L | 57 | N | 39 | M | 27 | L
84 | R | 57 | N | 39 | M | 27 | L
85 | N | 58 | M | 40 | L | 28 | R
86 | M | 59 | L | 41 | R | 28 | R
87 | L | 60 | R | 41 | R | 28 | R
88 | R | 60 | R | 41 | R | 28 | R
89 | N | 61 | M | 42 | L | 29 | N
90 | M | 62 | L | 43 | R | 29 | N
91 | L | 63 | R | 43 | R | 29 | N
92 | R | 63 | R | 43 | R | 29 | N
93 | M | 64 | L | 44 | N | 30 | M
94 | L | 65 | R | 44 | N | 30 | M
95 | R | 65 | R | 44 | N | 30 | M
96 | L | 66 | N | 45 | M | 31 | L
97 | R | 66 | N | 45 | M | 31 | L
98 | N | 67 | M | 46 | L | 32 | R
99 | M | 68 | L | 47 | R | 32 | R
100 | L | 69 | R | 47 | R | 32 | R
89 90 91 92 93 94 95 96 97 98 99 100
| | | | | | | | | | | |
| | ------ | ------ ------ | | |
| | | | | | | | |
61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88
| | | | | | | | | | | | | | | | | | | | | | | | | | | |
| -------- -------- | | ------ ------ | | ------ | | ------ | ------ ------ | | ------
| | | | | | | | | | | | | | | | | | |
42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
| | | | | | | | | | | | | | | | | | |
--------- | | -------- | | -------- | -------- -------- | | --------
| | | | | | | | | | | | |
29 30 31 32 33 34 35 36 37 38 39 40 41
| | | | | | | | | | | | |
| | ------------ | --------- --------- | | ---------
| | | | | | | | |
20 21 22 23 24 25 26 27 28
| | | | | | | | |
| -------------------- ------------- | | -------------
| | | | | |
14 15 16 17 18 19
| | | | | |
----------------------------- | | ---------------------
| | | |
10 11 12 13
| | | |
| | ------------------------------
| | |
7 8 9
| | |
| -----------------------------------------
| |
5 6
| |
-----------------------------------------------------------------------
|
4
|
|
|
3
|
|
|
2
|
|
|
1
|
Raw
diagram_j.py
from jutility import util
import tree
def diagram_j(n_max, printer):
table = util.Table(
util.Column("n", width=10, title="n"),
util.Column("j_n", width=10, title="J(n)"),
util.Column("j_j_n", width=10, title="J(J(n))"),
util.Column("j_j_j_n", width=10, title="J(J(J(n)))"),
util.Column("j_j_j_j_n", width=10, title="J(J(J(J(n))))"),
printer=printer,
)
j = {0: 0}
table.update(
n=0,
j_n=j[0],
j_j_n=j[j[0]],
j_j_j_n=j[j[j[0]]],
j_j_j_j_n=j[j[j[j[0]]]],
)
for n in range(1, n_max + 1):
j[n] = n - j[j[j[j[n - 1]]]]
table.update(
n=n,
j_n=j[n],
j_j_n=j[j[n]],
j_j_j_n=j[j[j[n]]],
j_j_j_j_n=j[j[j[j[n]]]],
)
return table
if __name__ == "__main__":
printer = util.Printer("diagram_j.txt", ".")
table = diagram_j(100, printer)
tree_dict = tree.list_to_tree_dict(table.get_data("j_n"))
tree.print_tree_dict(tree_dict, 1, printer)
Raw
diagram_j.txt
n | J(n) | J(J(n)) | J(J(J(n))) | J(J(J(J(n))))
---------- | ---------- | ---------- | ---------- | -------------
0 | 0 | 0 | 0 | 0
1 | 1 | 1 | 1 | 1
2 | 1 | 1 | 1 | 1
3 | 2 | 1 | 1 | 1
4 | 3 | 2 | 1 | 1
5 | 4 | 3 | 2 | 1
6 | 5 | 4 | 3 | 2
7 | 5 | 4 | 3 | 2
8 | 6 | 5 | 4 | 3
9 | 6 | 5 | 4 | 3
10 | 7 | 5 | 4 | 3
11 | 8 | 6 | 5 | 4
12 | 8 | 6 | 5 | 4
13 | 9 | 6 | 5 | 4
14 | 10 | 7 | 5 | 4
15 | 11 | 8 | 6 | 5
16 | 11 | 8 | 6 | 5
17 | 12 | 8 | 6 | 5
18 | 13 | 9 | 6 | 5
19 | 14 | 10 | 7 | 5
20 | 15 | 11 | 8 | 6
21 | 15 | 11 | 8 | 6
22 | 16 | 11 | 8 | 6
23 | 17 | 12 | 8 | 6
24 | 18 | 13 | 9 | 6
25 | 19 | 14 | 10 | 7
26 | 19 | 14 | 10 | 7
27 | 20 | 15 | 11 | 8
28 | 20 | 15 | 11 | 8
29 | 21 | 15 | 11 | 8
30 | 22 | 16 | 11 | 8
31 | 23 | 17 | 12 | 8
32 | 24 | 18 | 13 | 9
33 | 24 | 18 | 13 | 9
34 | 25 | 19 | 14 | 10
35 | 25 | 19 | 14 | 10
36 | 26 | 19 | 14 | 10
37 | 27 | 20 | 15 | 11
38 | 27 | 20 | 15 | 11
39 | 28 | 20 | 15 | 11
40 | 29 | 21 | 15 | 11
41 | 30 | 22 | 16 | 11
42 | 31 | 23 | 17 | 12
43 | 31 | 23 | 17 | 12
44 | 32 | 24 | 18 | 13
45 | 32 | 24 | 18 | 13
46 | 33 | 24 | 18 | 13
47 | 34 | 25 | 19 | 14
48 | 34 | 25 | 19 | 14
49 | 35 | 25 | 19 | 14
50 | 36 | 26 | 19 | 14
51 | 37 | 27 | 20 | 15
52 | 37 | 27 | 20 | 15
53 | 38 | 27 | 20 | 15
54 | 39 | 28 | 20 | 15
55 | 40 | 29 | 21 | 15
56 | 41 | 30 | 22 | 16
57 | 41 | 30 | 22 | 16
58 | 42 | 31 | 23 | 17
59 | 42 | 31 | 23 | 17
60 | 43 | 31 | 23 | 17
61 | 44 | 32 | 24 | 18
62 | 44 | 32 | 24 | 18
63 | 45 | 32 | 24 | 18
64 | 46 | 33 | 24 | 18
65 | 47 | 34 | 25 | 19
66 | 47 | 34 | 25 | 19
67 | 48 | 34 | 25 | 19
68 | 49 | 35 | 25 | 19
69 | 50 | 36 | 26 | 19
70 | 51 | 37 | 27 | 20
71 | 51 | 37 | 27 | 20
72 | 52 | 37 | 27 | 20
73 | 53 | 38 | 27 | 20
74 | 54 | 39 | 28 | 20
75 | 55 | 40 | 29 | 21
76 | 55 | 40 | 29 | 21
77 | 56 | 41 | 30 | 22
78 | 56 | 41 | 30 | 22
79 | 57 | 41 | 30 | 22
80 | 58 | 42 | 31 | 23
81 | 58 | 42 | 31 | 23
82 | 59 | 42 | 31 | 23
83 | 60 | 43 | 31 | 23
84 | 61 | 44 | 32 | 24
85 | 61 | 44 | 32 | 24
86 | 62 | 44 | 32 | 24
87 | 63 | 45 | 32 | 24
88 | 64 | 46 | 33 | 24
89 | 65 | 47 | 34 | 25
90 | 65 | 47 | 34 | 25
91 | 66 | 47 | 34 | 25
92 | 67 | 48 | 34 | 25
93 | 68 | 49 | 35 | 25
94 | 69 | 50 | 36 | 26
95 | 69 | 50 | 36 | 26
96 | 70 | 51 | 37 | 27
97 | 70 | 51 | 37 | 27
98 | 71 | 51 | 37 | 27
99 | 72 | 52 | 37 | 27
100 | 73 | 53 | 38 | 27
96 97 98 99 100
| | | | |
------ | | |
| | | |
70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95
| | | | | | | | | | | | | | | | | | | | | | | | | |
--------- | | | ------ ------ | ------ | | ------ | | | ------ | | | ------
| | | | | | | | | | | | | | | | | | |
51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
| | | | | | | | | | | | | | | | | | |
---------- | | | --------- --------- | --------- | | --------- | | |
| | | | | | | | | | | | | |
37 38 39 40 41 42 43 44 45 46 47 48 49 50
| | | | | | | | | | | | | |
----------- | | | ---------- ---------- | ---------- | |
| | | | | | | | | |
27 28 29 30 31 32 33 34 35 36
| | | | | | | | | |
----------- | | | ----------- ----------- |
| | | | | | |
20 21 22 23 24 25 26
| | | | | | |
------------- | | | -------------
| | | | |
15 16 17 18 19
| | | | |
--------------------- | | |
| | | |
11 12 13 14
| | | |
------------------------------ | |
| | |
8 9 10
| | |
----------------------------------------- |
| |
6 7
| |
----------------------------------------------------
|
5
|
|
|
4
|
|
|
3
|
|
|
2
|
|
|
1
|
Raw
diagram_j_flipped.py
from jutility import util
import tree
def diagram_j_flipped(n_max, printer):
table = util.Table(
util.Column("n", width=10, title="n"),
util.Column("j_n", width=10, title="J(n)"),
util.Column("j_j_n", width=10, title="J(J(n))"),
util.Column("j_j_j_n", width=10, title="J(J(J(n)))"),
util.Column("j_j_j_j_n", width=10, title="J(J(J(J(n))))"),
printer=printer,
)
j = {0: 0, 1: 1, 2: 1, 3: 2, 4: 3, 5: 4}
for n in range(6):
table.update(
n=n,
j_n=j[n],
j_j_n=j[j[n]],
j_j_j_n=j[j[j[n]]],
j_j_j_j_n=j[j[j[j[n]]]],
)
for n in range(6, n_max + 1):
j[n] = n + 1 - j[j[j[j[n - 1] + 1]]]
table.update(
n=n,
j_n=j[n],
j_j_n=j[j[n]],
j_j_j_n=j[j[j[n]]],
j_j_j_j_n=j[j[j[j[n]]]],
)
return table
if __name__ == "__main__":
printer = util.Printer("diagram_j_flipped.txt", ".")
table = diagram_j_flipped(100, printer)
tree_dict = tree.list_to_tree_dict(table.get_data("j_n"))
tree.print_tree_dict(tree_dict, 1, printer)
Raw
diagram_j_flipped.txt
n | J(n) | J(J(n)) | J(J(J(n))) | J(J(J(J(n))))
---------- | ---------- | ---------- | ---------- | -------------
0 | 0 | 0 | 0 | 0
1 | 1 | 1 | 1 | 1
2 | 1 | 1 | 1 | 1
3 | 2 | 1 | 1 | 1
4 | 3 | 2 | 1 | 1
5 | 4 | 3 | 2 | 1
6 | 5 | 4 | 3 | 2
7 | 5 | 4 | 3 | 2
8 | 6 | 5 | 4 | 3
9 | 7 | 5 | 4 | 3
10 | 7 | 5 | 4 | 3
11 | 8 | 6 | 5 | 4
12 | 9 | 7 | 5 | 4
13 | 10 | 7 | 5 | 4
14 | 10 | 7 | 5 | 4
15 | 11 | 8 | 6 | 5
16 | 12 | 9 | 7 | 5
17 | 13 | 10 | 7 | 5
18 | 14 | 10 | 7 | 5
19 | 14 | 10 | 7 | 5
20 | 15 | 11 | 8 | 6
21 | 15 | 11 | 8 | 6
22 | 16 | 12 | 9 | 7
23 | 17 | 13 | 10 | 7
24 | 18 | 14 | 10 | 7
25 | 19 | 14 | 10 | 7
26 | 19 | 14 | 10 | 7
27 | 20 | 15 | 11 | 8
28 | 21 | 15 | 11 | 8
29 | 21 | 15 | 11 | 8
30 | 22 | 16 | 12 | 9
31 | 22 | 16 | 12 | 9
32 | 23 | 17 | 13 | 10
33 | 24 | 18 | 14 | 10
34 | 25 | 19 | 14 | 10
35 | 26 | 19 | 14 | 10
36 | 26 | 19 | 14 | 10
37 | 27 | 20 | 15 | 11
38 | 28 | 21 | 15 | 11
39 | 29 | 21 | 15 | 11
40 | 29 | 21 | 15 | 11
41 | 30 | 22 | 16 | 12
42 | 31 | 22 | 16 | 12
43 | 31 | 22 | 16 | 12
44 | 32 | 23 | 17 | 13
45 | 32 | 23 | 17 | 13
46 | 33 | 24 | 18 | 14
47 | 34 | 25 | 19 | 14
48 | 35 | 26 | 19 | 14
49 | 36 | 26 | 19 | 14
50 | 36 | 26 | 19 | 14
51 | 37 | 27 | 20 | 15
52 | 38 | 28 | 21 | 15
53 | 39 | 29 | 21 | 15
54 | 40 | 29 | 21 | 15
55 | 40 | 29 | 21 | 15
56 | 41 | 30 | 22 | 16
57 | 42 | 31 | 22 | 16
58 | 43 | 31 | 22 | 16
59 | 43 | 31 | 22 | 16
60 | 44 | 32 | 23 | 17
61 | 45 | 32 | 23 | 17
62 | 45 | 32 | 23 | 17
63 | 46 | 33 | 24 | 18
64 | 46 | 33 | 24 | 18
65 | 47 | 34 | 25 | 19
66 | 48 | 35 | 26 | 19
67 | 49 | 36 | 26 | 19
68 | 50 | 36 | 26 | 19
69 | 50 | 36 | 26 | 19
70 | 51 | 37 | 27 | 20
71 | 51 | 37 | 27 | 20
72 | 52 | 38 | 28 | 21
73 | 53 | 39 | 29 | 21
74 | 54 | 40 | 29 | 21
75 | 55 | 40 | 29 | 21
76 | 55 | 40 | 29 | 21
77 | 56 | 41 | 30 | 22
78 | 57 | 42 | 31 | 22
79 | 58 | 43 | 31 | 22
80 | 59 | 43 | 31 | 22
81 | 59 | 43 | 31 | 22
82 | 60 | 44 | 32 | 23
83 | 61 | 45 | 32 | 23
84 | 62 | 45 | 32 | 23
85 | 62 | 45 | 32 | 23
86 | 63 | 46 | 33 | 24
87 | 64 | 46 | 33 | 24
88 | 64 | 46 | 33 | 24
89 | 65 | 47 | 34 | 25
90 | 65 | 47 | 34 | 25
91 | 66 | 48 | 35 | 26
92 | 67 | 49 | 36 | 26
93 | 68 | 50 | 36 | 26
94 | 69 | 50 | 36 | 26
95 | 69 | 50 | 36 | 26
96 | 70 | 51 | 37 | 27
97 | 71 | 51 | 37 | 27
98 | 71 | 51 | 37 | 27
99 | 72 | 52 | 38 | 28
100 | 72 | 52 | 38 | 28
96 97 98 99 100
| | | | |
| ------ ------
| | |
70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95
| | | | | | | | | | | | | | | | | | | | | | | | | |
-------- | | | ------ | | | ------ | | ------ | ------ ------ | | | ------
| | | | | | | | | | | | | | | | | | |
51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
| | | | | | | | | | | | | | | | | | |
| | | -------- | | -------- | -------- -------- | | | --------
| | | | | | | | | | | | | |
37 38 39 40 41 42 43 44 45 46 47 48 49 50
| | | | | | | | | | | | | |
| | --------- | --------- --------- | | | ---------
| | | | | | | | | |
27 28 29 30 31 32 33 34 35 36
| | | | | | | | | |
| ------------- ---------- | | | ----------
| | | | | | |
20 21 22 23 24 25 26
| | | | | | |
--------------------- | | | -------------
| | | | |
15 16 17 18 19
| | | | |
| | | ---------------------
| | | |
11 12 13 14
| | | |
| | ------------------------------
| | |
8 9 10
| | |
| ----------------------------------------
| |
6 7
| |
--------------------------------------------------------
|
5
|
|
|
4
|
|
|
3
|
|
|
2
|
|
|
1
|
Raw
diagram_recursive_chaos.py
from jutility import util, plotting
import tree
def diagram_recursive_chaos(n_max, printer):
table = util.Table(
util.Column("n", width=10, title="n"),
util.Column("q_n", width=10, title="Q(n)"),
util.Column("dq", width=10, title="Q(n) - Q(n-1)"),
util.Column("rq", ".3f", width=10, title="n / Q(n)"),
printer=printer,
)
q = {0: 1, 1: 1}
table.update(n=0, q_n=q[0])
table.update(n=1, q_n=q[1])
for n in range(2, n_max + 1):
q[n] = q[n - q[n - 1]] + q[n - q[n - 2]]
table.update(n=n, q_n=q[n], dq=(q[n] - q[n - 1]), rq=(n / q[n]))
return table
if __name__ == "__main__":
printer = util.Printer("diagram_recursive_chaos.txt", ".")
table = diagram_recursive_chaos(100, printer)
tree_dict = tree.list_to_tree_dict(table.get_data("q_n"))
tree.print_tree_dict(tree_dict, 3, printer)
plotting.plot(
plotting.Line(*table.get_data("n", "rq"), c="b"),
plot_name="n/Q(n) in chaotic sequence",
dir_name=".",
)
Raw
diagram_recursive_chaos.txt
n | Q(n) | Q(n) - Q(n-1) | n / Q(n)
---------- | ---------- | ------------- | ----------
0 | 1 | |
1 | 1 | |
2 | 2 | 1 | 1.000
3 | 3 | 1 | 1.000
4 | 3 | 0 | 1.333
5 | 4 | 1 | 1.250
6 | 5 | 1 | 1.200
7 | 5 | 0 | 1.400
8 | 6 | 1 | 1.333
9 | 6 | 0 | 1.500
10 | 6 | 0 | 1.667
11 | 8 | 2 | 1.375
12 | 8 | 0 | 1.500
13 | 8 | 0 | 1.625
14 | 10 | 2 | 1.400
15 | 9 | -1 | 1.667
16 | 10 | 1 | 1.600
17 | 11 | 1 | 1.545
18 | 11 | 0 | 1.636
19 | 12 | 1 | 1.583
20 | 12 | 0 | 1.667
21 | 12 | 0 | 1.750
22 | 12 | 0 | 1.833
23 | 16 | 4 | 1.438
24 | 14 | -2 | 1.714
25 | 14 | 0 | 1.786
26 | 16 | 2 | 1.625
27 | 16 | 0 | 1.688
28 | 16 | 0 | 1.750
29 | 16 | 0 | 1.812
30 | 20 | 4 | 1.500
31 | 17 | -3 | 1.824
32 | 17 | 0 | 1.882
33 | 20 | 3 | 1.650
34 | 21 | 1 | 1.619
35 | 19 | -2 | 1.842
36 | 20 | 1 | 1.800
37 | 22 | 2 | 1.682
38 | 21 | -1 | 1.810
39 | 22 | 1 | 1.773
40 | 23 | 1 | 1.739
41 | 23 | 0 | 1.783
42 | 24 | 1 | 1.750
43 | 24 | 0 | 1.792
44 | 24 | 0 | 1.833
45 | 24 | 0 | 1.875
46 | 24 | 0 | 1.917
47 | 32 | 8 | 1.469
48 | 24 | -8 | 2.000
49 | 25 | 1 | 1.960
50 | 30 | 5 | 1.667
51 | 28 | -2 | 1.821
52 | 26 | -2 | 2.000
53 | 30 | 4 | 1.767
54 | 30 | 0 | 1.800
55 | 28 | -2 | 1.964
56 | 32 | 4 | 1.750
57 | 30 | -2 | 1.900
58 | 32 | 2 | 1.812
59 | 32 | 0 | 1.844
60 | 32 | 0 | 1.875
61 | 32 | 0 | 1.906
62 | 40 | 8 | 1.550
63 | 33 | -7 | 1.909
64 | 31 | -2 | 2.065
65 | 38 | 7 | 1.711
66 | 35 | -3 | 1.886
67 | 33 | -2 | 2.030
68 | 39 | 6 | 1.744
69 | 40 | 1 | 1.725
70 | 37 | -3 | 1.892
71 | 38 | 1 | 1.868
72 | 40 | 2 | 1.800
73 | 39 | -1 | 1.872
74 | 40 | 1 | 1.850
75 | 39 | -1 | 1.923
76 | 42 | 3 | 1.810
77 | 40 | -2 | 1.925
78 | 41 | 1 | 1.902
79 | 43 | 2 | 1.837
80 | 44 | 1 | 1.818
81 | 43 | -1 | 1.884
82 | 43 | 0 | 1.907
83 | 46 | 3 | 1.804
84 | 44 | -2 | 1.909
85 | 45 | 1 | 1.889
86 | 47 | 2 | 1.830
87 | 47 | 0 | 1.851
88 | 46 | -1 | 1.913
89 | 48 | 2 | 1.854
90 | 48 | 0 | 1.875
91 | 48 | 0 | 1.896
92 | 48 | 0 | 1.917
93 | 48 | 0 | 1.938
94 | 48 | 0 | 1.958
95 | 64 | 16 | 1.484
96 | 41 | -23 | 2.341
97 | 52 | 11 | 1.865
98 | 54 | 2 | 1.815
99 | 56 | 2 | 1.768
100 | 48 | -8 | 2.083
95 86 87 99 98
| | | | |
| ------ | |
| | | |
64 47 56 58 59 60 61 66 50 53 54 57 63 67 65 71 70 68 73 75 76 79 81 82 80 84 85 83 88 89 90 91 92 93 94 100 62 69 72 74 77 78 96 97
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| ----------------------------- | ---------------- ------ ------ | ----------- | ----------- ------ | ------ ------------------------------- --------------------- ------ |
| | | | | | | | | | | | | | | | |
31 32 35 30 33 36 34 38 37 39 42 43 44 45 46 48 49 40 41 52 51 55
| | | | | | | | | | | | | | | | | | | | | |
---------------------- | ------------------------ -------- ----------- ------------------------------------------------------------- | ------------------ | ------
| | | | | | | | | |
17 18 19 20 21 22 24 25 23 26 27 28 29
| | | | | | | | | | | | |
------------------------------- ------------------------------------------------------------- --------------------------------------------------- --------------------------------------
| | | |
11 12 13 15 14 16
| | | | | |
------------------------------------------------------------------------------------------------ | -------------------------------------------------------------------
| | |
8 9 10
| | |
---------------------------------------------------------------------------------------------------------------------------------------------------
|
6 7
| |
-----------------------------------------------------------------------------------------------------------------------------------
|
5
|
|
|
4
|
|
|
3
|
Raw
tree.py
def list_to_tree_dict(data_list):
tree_dict = {i: data for i, data in enumerate(data_list)}
return tree_dict
class Node:
def __init__(self, value, parent_node=None):
self.value = value
self.parent_node = parent_node
if parent_node is not None:
parent_node.children.append(self)
self.children = []
self.pre_space = 0
def is_leaf(self):
return (len(self.children) == 0)
def min_subtree_pos(self):
if self.is_leaf():
bound = self.pre_space
else:
bound = min(child.min_subtree_pos() for child in self.children)
return bound
def max_subtree_pos(self):
if self.is_leaf():
bound = self.pre_space
else:
bound = max(child.max_subtree_pos() for child in self.children)
return bound
def min_child_pos(self):
return min(child.pre_space for child in self.children)
def max_child_pos(self):
return max(child.pre_space for child in self.children)
def shift_subtree_pos(self, n):
self.pre_space += n
for child in self.children:
child.shift_subtree_pos(n)
def __repr__(self):
return "%s -> %s" % (self.parent_node.value, self.value)
def print_tree_dict(tree_dict, root, printer, num_space=2):
max_len = max(len(str(data)) for data in tree_dict.keys())
item_width = max_len + num_space
reverse_dict = {v: [] for v in tree_dict.values()}
for k, v in tree_dict.items():
reverse_dict[v].append(k)
root_node = Node(root, Node(None, None))
level_list_list = [[root_node]]
leaf_list = [
Node(leaf, root_node)
for leaf in reverse_dict[root]
if leaf != root
]
while len(leaf_list) > 0:
level_list_list.append(leaf_list)
leaf_list = [
Node(leaf, parent)
for parent in leaf_list
if parent.value in reverse_dict
for leaf in reverse_dict[parent.value]
]
for level_list in reversed(level_list_list):
pre_space = 0
for node in level_list:
subtree_min_pos = node.min_subtree_pos()
subtree_width = node.max_subtree_pos() - subtree_min_pos
if subtree_min_pos < pre_space:
node.shift_subtree_pos(pre_space - subtree_min_pos)
if not node.is_leaf():
min_child_pos = node.min_child_pos()
max_child_pos = node.max_child_pos()
node.pre_space = (min_child_pos + max_child_pos) // 2
pre_space += subtree_width + item_width
for i, level_list in enumerate(reversed(level_list_list)):
for line_type in ["-", "|1", "v", "|2"]:
pos = 0
for node in level_list:
if line_type in ["-", "|1"] and node.is_leaf():
continue
if line_type in ["|1", "|2", "v"]:
s = str(node.value) if (line_type == "v") else "|"
s_pos = node.pre_space
else:
min_child_pos = node.min_child_pos()
max_child_pos = node.max_child_pos()
c = "-" if (len(node.children) > 1) else "|"
s = c * (max_child_pos - min_child_pos + 1)
s_pos = min_child_pos
pad_len = s_pos - pos
s = s.ljust(item_width)
s = s.rjust(pad_len + len(s))
printer(s, end="")
pos += len(s)
printer(end="\n")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment