login
Number of function evaluations in a recursive calculation of Fibonacci(n).
2

%I #43 Mar 06 2020 06:34:19

%S 1,1,1,3,6,5,11,10,15,12,23,17,27,22,37,26,38,28,51,36,53,41,68,45,67,

%T 50,87,60,86,64,102,65,93,67,118,80,116,88,141,90,131,95,163,110,155,

%U 114,181,113,163,118,205,138,198,148,234,147,211,151,253,167

%N Number of function evaluations in a recursive calculation of Fibonacci(n).

%C One way to calculate the Fibonacci numbers recursively is to use:

%C - F(0) = 0,

%C - F(1) = 1,

%C - F(2) = 1,

%C - F(n) = F((n + 1)/2)^2 + F((n - 1)/2)^2 for odd n,

%C - F(n) = F(n/2) * (F(n/2 - 1) + F(n/2 + 1)) for even n.

%C Proof: it is known that F(i) * F(j) + F(i + 1) * F(j + 1) = F(i + j + 1) (see formula section of A000045):

%C - for even n, let i = n/2 and j = n/2 - 1,

%C - for odd n, let i = j = (n + 1)/2.

%C This sequence gives the number of evaluations of F for calculating F(n). It is assumed that F needs to be evaluated more than once even if it has been evaluated before (no caching).

%C Conjecture: for large n, this sequence is bounded by a small constant times n^(4/3).

%H Rémy Sigrist, <a href="/A331124/b331124.txt">Table of n, a(n) for n = 0..10000</a>

%H GeeksforGeeks, <a href="https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/">Program for Fibonacci numbers</a>, see method 6, but erroneously states to take O(log n) operations.

%H Rémy Sigrist, <a href="/A331124/a331124.gp.txt">PARI program for A331124</a>

%F a(0) = 1,

%F a(1) = 1,

%F a(2) = 1,

%F a(n) = a((n + 1)/2) + a((n - 1)/2) + 1, n odd and n > 2,

%F a(n) = a(n/2) + a(n/2 - 1) + a(n/2 + 1) + 1, n even.

%e a(5) = a(3) + a(2) + 1 = (a(2) + a(1) + 1) + a(2) + 1 = 5.

%o (Fortran)

%o program main

%o implicit none

%o integer, parameter :: pmax = 100

%o integer :: r, n

%o logical, dimension(0:pmax) :: cache

%o do n = 0, pmax

%o cache (0:2) = .true.

%o cache (3:pmax) = .false.

%o r = a(n)

%o write (*,fmt="(I0,', ')", advance="no") r

%o end do

%o write (*,fmt="()")

%o contains

%o recursive function a (n) result(r)

%o integer, intent(in) :: n

%o integer :: r

%o if (cache(n)) then

%o r = 1

%o return

%o else if (mod(n, 2) == 1) then

%o r = a ((n + 1)/2) + a ((n - 1)/2) + 1

%o else

%o r = a (n/2) + a(n/2 - 1) + a(n/2 + 1) + 1

%o end if

%o cache (n) = .false.

%o end function a

%o end program main

%o (PARI) \\ See Links section.

%Y Cf. A000045; see A331164 for the number of function evaluations with caching.

%K nonn,easy,look

%O 0,4

%A _Thomas König_, Jan 10 2020