BOWD

Leonardo numbers and Math I wish I knew

February 15, 2019 • ☕️☕️ 8 min read

A couple of weeks ago I ended up on this page about smoothsort, thanks hackernews you faithful time sync. Smoothsort is widely considered to be the greatest of the greats when it comes to both execution time and memory. It manages O(n lg n)O(n\ lg\ n) optimized for O(n)O(n) best case and O(n)O(n) memory.

The short story is that it uses an in-place heap sort to achieve this but instead of a boring old binary heap it uses a mighty Leonardo heap.

I will not go in depth about Leonardo heaps or smoothsort as I want to follow up with a post about implementing all of this in Rust as my hello world, instead I will talk about the math behind this wonderfully quirky data structure.

The lesser known Leonardo numbers

Everybody knows about Fibonacci, but the Leonardo numbers have one up on them… Sorry couldn’t help myself.

L0=1L1=1Li=Li2+Li1+1\displaystyle L_0 = 1 \newline L_1 = 1 \newline L_i = L_{i-2} + L_{i-1} + 1

Which means that the first few Leonardo numbers are:

{1,1,3,5,9,15,25,41,67,109...}\displaystyle \{ 1, 1, 3, 5, 9, 15, 25, 41, 67, 109... \}

A Leonardo heap consists of one or more binary trees such that the number of nodes in each tree is a Leonardo number. Now in order for Leonardo heaps to work we must prove that:

  1. Any number nn can be written as a sum of distinct Leonardo numbers. Thus we can take any set of nn numbers and arrange them into kk binary trees each having si,0i<k{s_i, 0 \le i \lt k} nodes, such that sis_i is a Leonardo number.
  2. For any nn, the number of binary trees needed to form the heap (kk) is at most lg nlg\ n. Knowing how many binary trees our Leonardo heap contains will help when calculating the asymptotic complexity of the push and pop operations.

I really wanted to prove these two conjectures myself so I stopped reading Keith’s explanation and picked up a pencil. I have to say it was harder than it should have been.

The proof

Caveat: I’m pretty rusty when it comes to math so pretty please let me know if I get stuff wrong. There’s a “Did I get something wrong?” link at the end that points to the GitHub page where you can open an issue or submit a pull-request for this very article.

nN,xk such that 0ikLxi=n and xi<xi+1\displaystyle \forall n \in ℕ, \exist x_k \textrm{ such that } \sum_{\mathclap{0\le i\le k}} L_{x_i} = n \textrm{ and } x_i < x_{i+1}

That’s the gist of what we want to prove. In English, we need to prove that for any natural number nn there exists a sequence of kk numbers denoted xkx_k such that the sum of the xix_i-th Leonardo numbers (LxiL_{x_i}) for 0<i<k0\lt i\lt k is nn, also we restrict the sequence to be of distinct monotonically increasing numbers by adding the condition xi<xi+1x_i < x_{i+1}.

I stared at these equations for a while. I knew there was some sort of induction proof out there. The Leonardo sequence formula hinted at that especially hard with the plus one in Li=Li1+Li2+1L_i = L_{i-1}+L_{i-2} +1. But I couldn’t figure it out. It felt like you transition from nn to n+1n+1 by collapsing two consecutive Leonardo numbers into the next one, but there was one piece of the puzzle missing.

Finally I started to do what every computer scientist knows best, actually build the sets of numbers manually and look for patterns. I did that on my notebook first but then I thought to myself, you know javascript!

With a little help from React I built this nifty widget that computes the desired sequence xkx_k for consecutive nn. The first column is nn, the next are the members of the set. You can use the toggle at the top to switch between the actual Leonardo numbers or the Leonardo sequence indices.

Showing: Leonardo numbers / indices
n =
1 1
2 11
3 3
4 13
5 5
6 15
7 115
8 35
9 9
10 19
11 119
12 39
13 139
14 59
15 15
16 115
17 1115
18 315
19 1315
20 515
21 1515
22 11515
23 3515
24 915
25 25
26 125
27 1125
28 325
29 1325
30 525
31 1525
32 11525
33 3525
34 925
35 1925
36 11925
37 3925
38 13925
39 5925
40 1525
41 41
42 141
43 1141
44 341
45 1341
46 541
47 1541
48 11541
49 3541
50 941
51 1941
52 11941
53 3941
54 13941
55 5941
56 1541
57 11541
58 111541
59 31541
60 131541
61 51541
62 151541
63 1151541
64 351541
65 91541
66 2541
67 67
68 167
69 1167
70 367
71 1367
72 567
73 1567
74 11567
75 3567
76 967
77 1967
78 11967
79 3967
80 13967
81 5967
82 1567
83 11567
84 111567
85 31567
86 131567
87 51567
88 151567
89 1151567
90 351567
91 91567
92 2567
93 12567
94 112567
95 32567
96 132567
97 52567
98 152567
99 1152567
100 352567
101 92567
102 192567
103 1192567
104 392567
105 1392567
106 592567
107 152567
108 4167
109 109
110 1109
111 11109
112 3109
113 13109
114 5109
115 15109
116 115109
117 35109
118 9109
119 19109
120 119109
121 39109
122 139109
123 59109
124 15109
125 115109
126 1115109
127 315109
128 1315109
129 515109
130 1515109
131 11515109
132 3515109
133 915109
134 25109
135 125109
136 1125109
137 325109
138 1325109
139 525109
140 1525109
141 11525109
142 3525109
143 925109
144 1925109
145 11925109
146 3925109
147 13925109
148 5925109
149 1525109
150 41109
151 141109
152 1141109
153 341109
154 1341109
155 541109
156 1541109
157 11541109
158 3541109
159 941109
160 1941109
161 11941109
162 3941109
163 13941109
164 5941109
165 1541109
166 11541109
167 111541109
168 31541109
169 131541109
170 51541109
171 151541109
172 1151541109
173 351541109
174 91541109
175 2541109
176 67109
177 177
178 1177
179 11177
180 3177
181 13177
182 5177
183 15177
184 115177
185 35177
186 9177
187 19177
188 119177
189 39177
190 139177
191 59177
192 15177
193 115177
194 1115177
195 315177
196 1315177
197 515177
198 1515177
199 11515177
200 3515177
201 915177
202 25177
203 125177
204 1125177
205 325177
206 1325177
207 525177
208 1525177
209 11525177
210 3525177
211 925177
212 1925177
213 11925177
214 3925177
215 13925177
216 5925177
217 1525177
218 41177
219 141177
220 1141177
221 341177
222 1341177
223 541177
224 1541177
225 11541177
226 3541177
227 941177
228 1941177
229 11941177
230 3941177
231 13941177
232 5941177
233 1541177
234 11541177
235 111541177
236 31541177
237 131541177
238 51541177
239 151541177
240 1151541177
241 351541177
242 91541177
243 2541177
244 67177
245 167177
246 1167177
247 367177
248 1367177
249 567177
250 1567177
251 11567177
252 3567177
253 967177
254 1967177
255 11967177
256 3967177
257 13967177
258 5967177
259 1567177
260 11567177
261 111567177
262 31567177
263 131567177
264 51567177
265 151567177
266 1151567177
267 351567177
268 91567177
269 2567177
270 12567177
271 112567177
272 32567177
273 132567177
274 52567177
275 152567177
276 1152567177
277 352567177
278 92567177
279 192567177
280 1192567177
281 392567177
282 1392567177
283 592567177
284 152567177
285 4167177
286 109177
287 287
288 1287
289 11287
290 3287
291 13287
292 5287
293 15287
294 115287
295 35287
296 9287
297 19287
298 119287
299 39287
300 139287
301 59287
302 15287
303 115287
304 1115287
305 315287
306 1315287
307 515287
308 1515287
309 11515287
310 3515287
311 915287
312 25287
313 125287
314 1125287
315 325287
316 1325287
317 525287
318 1525287
319 11525287
320 3525287
321 925287
322 1925287
323 11925287
324 3925287
325 13925287
326 5925287
327 1525287
328 41287
329 141287
330 1141287
331 341287
332 1341287
333 541287
334 1541287
335 11541287
336 3541287
337 941287
338 1941287
339 11941287
340 3941287
341 13941287
342 5941287
343 1541287
344 11541287
345 111541287
346 31541287
347 131541287
348 51541287
349 151541287
350 1151541287
351 351541287
352 91541287
353 2541287
354 67287
355 167287
356 1167287
357 367287
358 1367287
359 567287
360 1567287
361 11567287
362 3567287
363 967287
364 1967287
365 11967287
366 3967287
367 13967287
368 5967287
369 1567287
370 11567287
371 111567287
372 31567287
373 131567287
374 51567287
375 151567287
376 1151567287
377 351567287
378 91567287
379 2567287
380 12567287
381 112567287
382 32567287
383 132567287
384 52567287
385 152567287
386 1152567287
387 352567287
388 92567287
389 192567287
390 1192567287
391 392567287
392 1392567287
393 592567287
394 152567287
395 4167287
396 109287
397 1109287
398 11109287
399 3109287
400 13109287
401 5109287
402 15109287
403 115109287
404 35109287
405 9109287
406 19109287
407 119109287
408 39109287
409 139109287
410 59109287
411 15109287
412 115109287
413 1115109287
414 315109287
415 1315109287
416 515109287
417 1515109287
418 11515109287
419 3515109287
420 915109287
421 25109287
422 125109287
423 1125109287
424 325109287
425 1325109287
426 525109287
427 1525109287
428 11525109287
429 3525109287
430 925109287
431 1925109287
432 11925109287
433 3925109287
434 13925109287
435 5925109287
436 1525109287
437 41109287
438 141109287
439 1141109287
440 341109287
441 1341109287
442 541109287
443 1541109287
444 11541109287
445 3541109287
446 941109287
447 1941109287
448 11941109287
449 3941109287
450 13941109287
451 5941109287
452 1541109287
453 11541109287
454 111541109287
455 31541109287
456 131541109287
457 51541109287
458 151541109287
459 1151541109287
460 351541109287
461 91541109287
462 2541109287
463 67109287
464 177287
465 465
466 1465
467 11465
468 3465
469 13465
470 5465
471 15465
472 115465
473 35465
474 9465
475 19465
476 119465
477 39465
478 139465
479 59465
480 15465
481 115465
482 1115465
483 315465
484 1315465
485 515465
486 1515465
487 11515465
488 3515465
489 915465
490 25465
491 125465
492 1125465
493 325465
494 1325465
495 525465
496 1525465
497 11525465
498 3525465
499 925465
500 1925465

Source on github.

You might have noticed that for the n=1n=1 I actually use L1L_1 instead of L0L_0 this is intentional and actually part of the nifty solution. You can already start to see some pretty clear patterns and recursion emerge. If you look closely at the numbers you’ll see that between any two consecutive nn only one of two things happens:

  1. x1x_1 = x0+1x_0 + 1, aka the first to indices are consecutive and they collapse into the next Leonardo number, because if we have two consecutive indices there Lx0+Lx1+1=Lx1+1L_{x_0} + L_{x_1} + 1 = L_{x_1+1}

  2. We add L0L_0 or L1L_1 at the front of the sequence, if both were already there that would fall into (1).

The first situation isn’t intuitively true because, when trying to transition from nn to n+1n+1, collapsing two consecutive Leonardo numbers might give you another number that’s already in the sequence. But that’s actually the missing piece. If you look at all the numbers in the box you’ll notice that we only ever get consecutive Leonardo numbers in the first two positions of the sequence, check it out. Thus we can prove the conjecture by further restricting its conditions:

nN,xk such that (1) 0ikLxi=n(2) x0<x1(3) xi+1<xi+1,for i>0(4) x0=0    x1=1\displaystyle \forall n \in ℕ, \exist x_k \textrm{ such that }\newline \textrm{(1) } \sum_{\mathclap{0\le i\le k}} L_{x_i} = n \newline \textrm{(2) } x_0 < x_1 \newline \textrm{(3) } x_i + 1 < x_{i+1}, \textrm{for } i > 0 \newline \textrm{(4) } x_0 = 0 \iff x_1 = 1

Let’s break it down. The first condition stays the same as before. The 2nd and 3rd ensure not only that the sequence is monotonically increasing but that two consecutive indices will only occur at the beginning of the sequence. The 4th is a little helper condition that enforces 00 to be part of the sequence only if 11 already is. It helps us have a single valid transition when neither 0,L0=10, L_0 = 1 or 1,L1=11, L_1 = 1 are part of the sequence for nn and we’re transitioning to n+1n+1.

For the induction part we say that for n=0n=0, the empty sequence fulfils all conditions. Now we need to prove that for any nn with a sequence xkx_k, fulfilling the conditions, there’s a sequence yly_l fulfilling the same conditions for n+1n+1. This becomes trivial after the observations I made above, when looking at the changes in structure between consecutive values of nn. We have these cases:

  1. x1x_1 = x0x_0 + 1, the first two elements of xx are consecutive

If that’s the case we can defined a sequence yy with k1k-1 elements. y0=x1+1y_0 = x_1 + 1 and yi=xi+1,i>0y_i = x_i+1, i > 0. It follows that:

0ik1Lyi=Lx1+1+2ikLxi=Lx1+Lx11+1+2ikLxi=0ikLxi+1=n+1\displaystyle \sum_{\mathclap{0\le i\le k-1}} L_{y_i} = L_{x_1 + 1} + \sum_{\mathclap{2\le i\le k}} L_{x_i}= L_{x_1} +L_{x_1-1} + 1 + \sum_{\mathclap{2\le i\le k}} L_{x_i} = \sum_{\mathclap{0\le i\le k}} L_{x_i} + 1 = n + 1

  1. x0x_0 = 1 and case (1) does not apply, which means that we can define yy with k+1k+1 elements such that y0=0y_0 = 0 and yi=xi1,i>0y_i = x_{i-1}, i > 0, it follows that:

0ik1Lyi=L0+0ik=1+0ikLxi=n+1\displaystyle \sum_{\mathclap{0\le i\le k-1}} L_{y_i} = L_{0} + \sum_{\mathclap{0\le i\le k}} = 1 + \sum_{\mathclap{0\le i\le k}} L_{x_i}= n + 1

  1. x0x_011, from that follows that x0x_000 otherwise the 4th condition would imply x1=1x_1 = 1 and case (1) would apply. So let there be a sequence yy with k+1k+1 elements such that y0=1y_0 = 1 and yi=xi1,i>0y_i = x_{i-1}, i > 0, it follows that:

0ik1Lyi=L1+0ik=1+0ikLxi=n+1\displaystyle \sum_{\mathclap{0\le i\le k-1}} L_{y_i} = L_{1} + \sum_{\mathclap{0\le i\le k}} = 1 + \sum_{\mathclap{0\le i\le k}} L_{x_i}= n + 1

Which wraps up our proof nicely. All that’s left now is to figure out if for the series xk,k<=lg nx_k, k <= lg\ n, but I’ll leave this as an exercise to the reader1.

Tune in next time when I take all this further and talk about the Leonardo heap and how that’s used in implementing the elusive smoothsort.


  1. Hint: write Leonardo numbers as a function of Fibonacci numbers.