Я хочу знать, как я могу математически выразить явление, обнаруженное в деревьях Меркла. Если я хочу выяснить, какой листовой узел в дереве Меркла изменился, я могу посмотреть на путь аутентификации, чтобы понять это. Допустим, есть один конечный узел и один корневой узел. Если корневой узел изменяется, вам не нужно смотреть на какие-либо другие узлы (0), чтобы определить, какой конечный узел должен был измениться. На рисунке 2 напротив 1 стоит 0. Если есть 2 листовых узла и изменения корня Меркла, вам нужно посмотреть только на 1 узел, чтобы определить, какой листовой узел должен был измениться. По мере того, как мы увеличиваем количество листовых узлов, существует связь с общим количеством узлов, на которые вам нужно обратить внимание. Мне было интересно, есть ли способ, которым я мог бы выразить это математически в чистом виде. Спасибо!
Рисунок 1.
2*0 = 0 (1 ноль)
2^0 = 1 (1 единица)
2^1 = 2 (2 двойки)
2^2 = 4 (4 тройки)
2^3 = 8 (8 четверок)
2^4 = 16 (16 пятерок)
2^5 = 32 (32 шестерки)
2^6 = 64 (64 семерки)
Фигура 2.
Лист (левый столбец) и общее количество узлов (правый столбец)
1 0
2 1
3 2
4 2
5 3
6 3
7 3
8 3
9 4
10 4
11 4
12 4
13 4
14 4
15 4
16 4
17 5
18 5
19 5
20 5
21 5
22 5
23 5
24 5
25 5
26 5
27 5
28 5
29 5
30 5
31 5
32 5
33 6
34 6
35 6
36 6
37 6
38 6
39 6
40 6
41 6
42 6
43 6
44 6
45 6
46 6
47 6
48 6
49 6
50 6
51 6
52 6
53 6
54 6
55 6
56 6
57 6
58 6
59 6
60 6
61 6
62 6
63 6
64 6
65 7
66 7
67 7
68 7
69 7
70 7
71 7
72 7
73 7
74 7
75 7
76 7
77 7
78 7
79 7
80 7
81 7
82 7
83 7
84 7
85 7
86 7
87 7
88 7
89 7
90 7
91 7
92 7
93 7
94 7
95 7
96 7
97 7
98 7
99 7
100 7
101 7
102 7
103 7
104 7
105 7
106 7
107 7
108 7
109 7
110 7
111 7
112 7
113 7
114 7
115 7
116 7
117 7
118 7
119 7
120 7
121 7
122 7
123 7
124 7
125 7
126 7
127 7
128 7
Всякий раз, когда вас интересует математическая функция, для которой вы можете привести последовательность целочисленных примеров, выполните поиск OEIS: https://oeis.org/A029837 .
Бен Столман
Питер Уилле
Нейт Элдридж
Бен Столман