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.