|
%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
|
