<p><a href="https://en.wikipedia.org/wiki/Floor_and_ceiling_functions" rel="nofollow noreferrer">Ceiling</a> of the <a href="https://en.wikipedia.org/wiki/Binary_logarithm" rel="nofollow noreferrer">binary logarithm</a>?</p>

<p><a href="https://i.sstatic.net/V2Sjz.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/V2Sjz.png" alt="enter image description here"></a></p>

CC BY-SA 4.0
2018-07-24T07:26:20.757Z
Cool!!! Would you mind explaining the what the ceiling is? Besides in a house.
Ben Stolman
CC BY-SA 4.0
2018-07-24T14:08:01.053Z
Ceiling means rounding up to the next integer.
Pieter Wuille
CC BY-SA 4.0
2018-07-24T14:10:35.123Z
@BenStolman: Did you see the word "ceiling" is a link to Wikipedia?
Nate Eldredge
CC BY-SA 4.0
2018-07-24T19:53:07.117Z
@NateEldredge: I did indeed, but my brain could not comprehend it.
Ben Stolman
CC BY-SA 4.0
2018-07-24T04:17:55.963Z
2018-07-24T04:17:55.963Z
Nate Eldredge
<p>Whenever you are interested in a mathematical function that you can give a sequence of integer examples for, search OEIS: <a href="https://oeis.org/A029837" rel="nofollow noreferrer">https://oeis.org/A029837</a></p>

CC BY-SA 4.0
2018-07-24T23:32:23.980Z
2018-07-24T23:32:23.980Z
G. Maxwell
<p>I want to know how I can express a phenomenon found in Merkle Trees mathematically. If I want to figure out which leaf node in a Merkle Tree has changed I can look at the authentication path to figure it out. Let's say there is one leaf node and one root node. If the root node changes you don't have to look at any other nodes (0) to determine which leaf node must have changed. In Figure 2 there is a 0 across from 1. If there are 2 leaf nodes and the Merkle  Root changes you only have to look at 1 node to determine which leaf node must have changed. As we increase the number of leaf nodes there is a relationship that exists with the total number of nodes you need to look at. I was wondering if there was a way I could express this mathematically in a clean way. Thanks!</p>

<p>Figure 1. </p>

<p>2*0 = 0  (1 zero)</p>

<p>2^0 = 1  (1 one)</p>

<p>2^1 = 2  (2 twos)</p>

<p>2^2 = 4  (4 threes)</p>

<p>2^3 = 8  (8 fours)</p>

<p>2^4 = 16 (16 fives)</p>

<p>2^5 = 32 (32 sixes)</p>

<p>2^6 = 64 (64 sevens)</p>

<p>Figure 2.</p>

<p>Leaf (Left Column)   &amp;   Total Nodes (Right Column)<br>
1         0</p>

<p>2         1</p>

<p>3         2</p>

<p>4         2</p>

<p>5         3</p>

<p>6         3</p>

<p>7         3</p>

<p>8         3</p>

<p>9         4</p>

<p>10        4</p>

<p>11        4</p>

<p>12        4</p>

<p>13        4</p>

<p>14        4</p>

<p>15        4</p>

<p>16        4</p>

<p>17        5</p>

<p>18        5</p>

<p>19        5</p>

<p>20        5</p>

<p>21        5</p>

<p>22        5</p>

<p>23        5</p>

<p>24        5</p>

<p>25        5</p>

<p>26        5</p>

<p>27        5</p>

<p>28        5</p>

<p>29        5</p>

<p>30        5</p>

<p>31        5</p>

<p>32        5</p>

<p>33        6</p>

<p>34        6</p>

<p>35        6</p>

<p>36        6</p>

<p>37        6</p>

<p>38        6</p>

<p>39        6</p>

<p>40        6</p>

<p>41        6</p>

<p>42        6</p>

<p>43        6</p>

<p>44        6</p>

<p>45        6</p>

<p>46        6</p>

<p>47        6</p>

<p>48        6</p>

<p>49        6</p>

<p>50        6</p>

<p>51        6</p>

<p>52        6</p>

<p>53        6</p>

<p>54        6</p>

<p>55        6</p>

<p>56        6</p>

<p>57        6</p>

<p>58        6</p>

<p>59        6</p>

<p>60        6</p>

<p>61        6</p>

<p>62        6</p>

<p>63        6</p>

<p>64        6</p>

<p>65        7</p>

<p>66        7</p>

<p>67        7</p>

<p>68        7</p>

<p>69        7</p>

<p>70        7</p>

<p>71        7</p>

<p>72        7</p>

<p>73        7</p>

<p>74        7</p>

<p>75        7</p>

<p>76        7</p>

<p>77        7</p>

<p>78        7</p>

<p>79        7</p>

<p>80        7</p>

<p>81        7</p>

<p>82        7</p>

<p>83        7</p>

<p>84        7</p>

<p>85        7</p>

<p>86        7</p>

<p>87        7</p>

<p>88        7</p>

<p>89        7</p>

<p>90        7</p>

<p>91        7</p>

<p>92        7</p>

<p>93        7</p>

<p>94        7</p>

<p>95        7</p>

<p>96        7</p>

<p>97        7</p>

<p>98        7</p>

<p>99        7</p>

<p>100       7</p>

<p>101       7</p>

<p>102       7</p>

<p>103       7</p>

<p>104       7</p>

<p>105       7</p>

<p>106       7</p>

<p>107       7</p>

<p>108       7</p>

<p>109       7</p>

<p>110       7</p>

<p>111       7</p>

<p>112       7</p>

<p>113       7</p>

<p>114       7</p>

<p>115       7</p>

<p>116       7</p>

<p>117       7</p>

<p>118       7</p>

<p>119       7</p>

<p>120       7</p>

<p>121       7</p>

<p>122       7</p>

<p>123       7</p>

<p>124       7</p>

<p>125       7</p>

<p>126       7</p>

<p>127       7</p>

<p>128       7</p>

<hash><merkle-tree><algorithms>
I want to know how I can express a phenomenon found in Merkle Trees mathematically
Ben Stolman
# I want to know how I can express a phenomenon found in Merkle Trees mathematically

(Asked by: username_0 on 2018-07-24)

I want to know how I can express a phenomenon found in Merkle Trees mathematically. If I want to figure out which leaf node in a Merkle Tree has changed I can look at the authentication path to figure it out. Let's say there is one leaf node and one root node. If the root node changes you don't have to look at any other nodes (0) to determine which leaf node must have changed. In Figure 2 there is a 0 across from 1. If there are 2 leaf nodes and the Merkle Root changes you only have to look at 1 node to determine which leaf node must have changed. As we increase the number of leaf nodes there is a relationship that exists with the total number of nodes you need to look at. I was wondering if there was a way I could express this mathematically in a clean way. Thanks!

Figure 1.

2\*0 = 0 (1 zero)

2^0 = 1 (1 one)

2^1 = 2 (2 twos)

2^2 = 4 (4 threes)

2^3 = 8 (8 fours)

2^4 = 16 (16 fives)

2^5 = 32 (32 sixes)

2^6 = 64 (64 sevens)

Figure 2.

Leaf (Left Column) & Total Nodes (Right Column)  
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

**Tags:** hash, merkle-tree, algorithms


---

## 2 answers

### Answer by username_1 on 2018-07-24. Score: 2 | Accepted answer

[Ceiling](https://en.wikipedia.org/wiki/Floor_and_ceiling_functions) of the [binary logarithm](https://en.wikipedia.org/wiki/Binary_logarithm)?

[![enter image description here](https://i.sstatic.net/V2Sjz.png)](https://i.sstatic.net/V2Sjz.png)

> **Comments:**
> **username_0**: Cool!!! Would you mind explaining the what the ceiling is? Besides in a house.  
> **username_2**: Ceiling means rounding up to the next integer.  
> **username_1**: @BenStolman: Did you see the word "ceiling" is a link to Wikipedia?  
> **username_0**: @NateEldredge: I did indeed, but my brain could not comprehend it.  

---

### Answer by username_3 on 2018-07-24. Score: 1

Whenever you are interested in a mathematical function that you can give a sequence of integer examples for, search OEIS: <https://oeis.org/A029837>


---

