A291711 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, 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, 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, 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

Offset

1,2

Comments

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).

Links

Table of n, a(n) for n=1..94.

Example

a(7)=3 because 7 =3 + 3 + 1 is a minimal sum using 3 coins.

Maple

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:
for n from 1 to 200 do: m:=n: ct:=0: for s from 1 to nn while m>0 do:
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);
# alternative program
# compute index of largest Fibonacci number not larger than n.
fibIdx := proc(n)
    local i;
    for i from 1 do
        if combinat[fibonacci](i) > n then
            return i-1 ;
        end if;
    end do:
end proc:
A291711 := proc(n)
    local fibm, gf, e, gfe ;
    fibm := fibIdx(n) ;
    gf := add( x^combinat[fibonacci](2*m), m=1..fibm/2) ;
    gfe := gf ;
    for e from 1 do
        expand(coeftayl(gfe, x=0, n)) ;
        if % > 0 then
            return e ;
        end if;
        gfe := expand(gfe*gf) ;
    end do:
end proc:
seq(A291711(n), n=1..100) ; # R. J. Mathar, Nov 11 2017

Crossrefs

Cf. A007895 for Fibonacci(k), A245588 for Fibonacci(2k-1).

Sequence in context: A147784 A249388 A051329 * A173964 A358134 A205710

Adjacent sequences: A291708 A291709 A291710 * A291712 A291713 A291714

Keyword

nonn

Author

Yuriko Suwa, Aug 30 2017

Status

approved