%I #13 Dec 07 2017 15:34:45
%S 1,2,1,2,3,2,3,1,2,3,2,3,4,3,4,2,3,4,3,4,1,2,3,2,3,4,3,4,2,3,4,3,4,5,
%T 4,5,3,4,5,4,5,2,3,4,3,4,5,4,5,3,4,5,4,5,1,2,3,2,3,4,3,4,2,3,4,3,4,5,
%U 4,5,3,4,5,4,5,2,3,4,3,4,5,4,5,3,4,5,4,5,6,5,6,4,5,6
%N The minimum number of coins needed to pay for n units in the currency system of values 1, 3, 8, 21, 55, 144, ..., Fibonacci(2k), ...
%C It has been proved that there is a unique way to pay any price n with a(n) coins having values of the form Fibonacci(2k).
%e a(7)=3 because 7 =3 + 3 + 1 is a minimal sum using 3 coins.
%p x1:=1: x2:=3: L:=[x1,x2]: nn:=12: LS:=[]: for k from 1 to nn-2 do:z:=3*x2-x1: L:=[op(L),z]: x1:=x2: x2:=z: od:
%p for n from 1 to 200 do: m:=n: ct:=0: for s from 1 to nn while m>0 do:
%p for j from 1 to nn-1 do:if m<L[j+1] and not m<L[j] then q:=trunc(m/L[j]): m:=m-q*L[j]: ct:=ct+q:fi: od: od:LS:=[op(LS),ct]:od:print(LS);
%p # alternative program
%p # compute index of largest Fibonacci number not larger than n.
%p fibIdx := proc(n)
%p local i;
%p for i from 1 do
%p if combinat[fibonacci](i) > n then
%p return i-1 ;
%p end if;
%p end do:
%p end proc:
%p A291711 := proc(n)
%p local fibm,gf,e,gfe ;
%p fibm := fibIdx(n) ;
%p gf := add( x^combinat[fibonacci](2*m),m=1..fibm/2) ;
%p gfe := gf ;
%p for e from 1 do
%p expand(coeftayl(gfe,x=0,n)) ;
%p if % > 0 then
%p return e ;
%p end if;
%p gfe := expand(gfe*gf) ;
%p end do:
%p end proc:
%p seq(A291711(n),n=1..100) ; # _R. J. Mathar_, Nov 11 2017
%Y Cf. A007895 for Fibonacci(k), A245588 for Fibonacci(2k-1).
%K nonn
%O 1,2
%A _Yuriko Suwa_, Aug 30 2017