Tuesday, March 10, 2020
By: Matthew Doucette

I discovered Leonardo numbers while playing around with Fibonacci numbers using a recursive algorithm.

 

Recursion:

The basic idea of recursion is that a method (aka function) is self-referential, as are many concepts in mathematics, such as Fibonacci numbers:

F(n) = F(n-2) + F(n-1)

...and is grounded with the definitions of the first two numbers:

F(0) = 0
F(1) = 1

Fibonacci Numbers:

The Fibonacci sequence is created by adding the previous two terms together. Starting at 0 and 1, you add them to get 1. Next, 1 plus 1 is 2. Next, 1 plus 2 is 3. And so on...

Here are the first 93 Fibonacci numbers:

0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1,597
2,584
4,181
6,765
10,946
17,711
28,657
46,368
75,025
121,393
196,418
317,811
514,229
832,040
1,346,269
2,178,309
3,524,578
5,702,887
9,227,465
14,930,352
24,157,817
39,088,169
63,245,986
102,334,155
165,580,141
267,914,296
433,494,437
701,408,733
1,134,903,170
1,836,311,903
2,971,215,073
4,807,526,976
7,778,742,049
12,586,269,025
20,365,011,074
32,951,280,099
53,316,291,173
86,267,571,272
139,583,862,445
225,851,433,717
365,435,296,162
591,286,729,879
956,722,026,041
1,548,008,755,920
2,504,730,781,961
4,052,739,537,881
6,557,470,319,842
10,610,209,857,723
17,167,680,177,565
27,777,890,035,288
44,945,570,212,853
72,723,460,248,141
117,669,030,460,994
190,392,490,709,135
308,061,521,170,129
498,454,011,879,264
806,515,533,049,393
1,304,969,544,928,657
2,111,485,077,978,050
3,416,454,622,906,707
5,527,939,700,884,757
8,944,394,323,791,464
14,472,334,024,676,221
23,416,728,348,467,685
37,889,062,373,143,906
61,305,790,721,611,591
99,194,853,094,755,497
160,500,643,816,367,088
259,695,496,911,122,585
420,196,140,727,489,673
679,891,637,638,612,258
1,100,087,778,366,101,931
1,779,979,416,004,714,189
2,880,067,194,370,816,120
4,660,046,610,375,530,309
7,540,113,804,746,346,429
12,200,160,415,121,876,738
...

Why stop at 93? This is the limit of the 64-bit unsigned integer type: 0..18,446,744,073,709,551,615. The 94th Fibonacci number is 19,740,274,219,868,223,167, and requires 65 bits to store.

Here are the first 2,000 Fibonacci numbers: https://oeis.org/A000045/b000045.txt

 

Leonardo Numbers:

Anyways, what is surprsing is the calculation time this takes. I created a recursive Fibonacci() method and counted how many times it was called to calculate each consecutive Fibonnaci number, and discovered it was the Leonardo numbers:

0: 0. Fibonacci() called 1 times.
1: 1. Fibonacci() called 1 times.
2: 1. Fibonacci() called 3 times.
3: 2. Fibonacci() called 5 times.
4: 3. Fibonacci() called 9 times.
5: 5. Fibonacci() called 15 times.
6: 8. Fibonacci() called 25 times.
7: 13. Fibonacci() called 41 times.
8: 21. Fibonacci() called 67 times.
9: 34. Fibonacci() called 109 times.
10: 55. Fibonacci() called 177 times.
11: 89. Fibonacci() called 287 times.
12: 144. Fibonacci() called 465 times.
13: 233. Fibonacci() called 753 times.
14: 377. Fibonacci() called 1,219 times.
15: 610. Fibonacci() called 1,973 times.
16: 987. Fibonacci() called 3,193 times.
17: 1,597. Fibonacci() called 5,167 times.
18: 2,584. Fibonacci() called 8,361 times.
19: 4,181. Fibonacci() called 13,529 times.
20: 6,765. Fibonacci() called 21,891 times.
21: 10,946. Fibonacci() called 35,421 times.
22: 17,711. Fibonacci() called 57,313 times.
23: 28,657. Fibonacci() called 92,735 times.
24: 46,368. Fibonacci() called 150,049 times.
25: 75,025. Fibonacci() called 242,785 times.
26: 121,393. Fibonacci() called 392,835 times.
27: 196,418. Fibonacci() called 635,621 times.
28: 317,811. Fibonacci() called 1,028,457 times.
29: 514,229. Fibonacci() called 1,664,079 times.
30: 832,040. Fibonacci() called 2,692,537 times.
31: 1,346,269. Fibonacci() called 4,356,617 times.
32: 2,178,309. Fibonacci() called 7,049,155 times.
33: 3,524,578. Fibonacci() called 11,405,773 times.
34: 5,702,887. Fibonacci() called 18,454,929 times.
35: 9,227,465. Fibonacci() called 29,860,703 times.
36: 14,930,352. Fibonacci() called 48,315,633 times.
37: 24,157,817. Fibonacci() called 78,176,337 times.
38: 39,088,169. Fibonacci() called 126,491,971 times.
39: 63,245,986. Fibonacci() called 204,668,309 times.
40: 102,334,155. Fibonacci() called 331,160,281 times.
41: 165,580,141. Fibonacci() called 535,828,591 times.
42: 267,914,296. Fibonacci() called 866,988,873 times.
43: 433,494,437. Fibonacci() called 1,402,817,465 times.
44: 701,408,733. Fibonacci() called 2,269,806,339 times.
45: 1,134,903,170. Fibonacci() called 3,672,623,805 times.
46: 1,836,311,903. Fibonacci() called 5,942,430,145 times.
47: 2,971,215,073. Fibonacci() called 9,615,053,951 times.
48: 4,807,526,976. Fibonacci() called 15,557,484,097 times.
49: 7,778,742,049. Fibonacci() called 25,172,538,049 times.
50: 12,586,269,025. Fibonacci() called 40,730,022,147 times.
51: 20,365,011,074. Fibonacci() called 65,902,560,197 times.
52: 32,951,280,099. Fibonacci() called 106,632,582,345 times.
53: 53,316,291,173. Fibonacci() called 172,535,142,543 times.
54: 86,267,571,272. Fibonacci() called 279,167,724,889 times.
55: 139,583,862,445. Fibonacci() called 451,702,867,433 times.
56: 225,851,433,717. Fibonacci() called 730,870,592,323 times.
57: 365,435,296,162. Fibonacci() called 1,182,573,459,757 times.
58: 591,286,729,879. Fibonacci() called 1,913,444,052,081 times.
59: 956,722,026,041. Fibonacci() called 3,096,017,511,839 times.
...

Why did I stop here? After 24 hours, it had only reached the 57th number. After 25 hours, the same. After 2 days (47.5 hours) it reached the 59th number! This is a lot of calculations. Over a trillion calls to the Fibonacci() method by the 57th number. The irony is it's only about 57 calculations without recursion (just adding up all the Fibonacci numbers in sequence). Further interesting notes is how to optimize such calculation with hash tables, that effectively reduce the number of method calls by storing previously calculated values. It's amazing effective, and the idea even works in chess engines.

As mentioned above, the amount of calls is the integer seqeuence known as Leonardo numbers!

Here is a list of the first 500 Leonardo numbers: https://oeis.org/A001595/b001595.txt

 

Other Math Theory:

See our math theory work.

 

That is all.

 

 

About the Author: I am Matthew Doucette of Xona Games, an award-winning indie game studio that I founded with my twin brother. We make intensified arcade-style retro games. Our business, our games, our technology, and we as competitive gamers have won prestigious awards and received worldwide press. Our business has won $190,000 in contests. Our games have ranked from #1 in Canada to #1 in Japan, have become #1 best sellers in multiple countries, have won game contests, and have held 3 of the top 5 rated spots in Japan of all Xbox LIVE indie games. Our game engines have been awarded for technical excellence. And we, the developers, have placed #1 in competitive gaming competitions -- relating to the games we make. Read about our story, our awards, our games, and view our blog.