login
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), ...
1

%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