A245588 -id:A245588 - cp's OEIS frontend

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

Yuriko Suwa, Aug 30 2017

nonn

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

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

Amiram Eldar, Table of n, a(n) for n = 1..10000

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

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

f[n_] := f[n] = Fibonacci[2*n]; a[n_] := Module[{s = 0, m = n, k}, While[m > 0, k = 1; While[m > f[k], k++]; If[m < f[k], k--]; If[m >= 2*f[k], s += 2; m -= 2*f[k], s++; m -= f[k]]]; s]; Array[a, 100] (* Amiram Eldar, Feb 28 2025 *)

mx = 20; fvec = vector(mx, i, fibonacci(2*i)); f(n) = if(n <= mx, fvec[n], fibonacci(2*n));
a(n) = {my(s = 0, m = n, k); while(m > 0, k = 1; while(m > f(k), k++); if(m < f(k), k--); if(m >= 2*f(k), s += 2; m -= 2*f(k), s++; m -= f(k))); s;} \\ Amiram Eldar, Feb 28 2025

a(n) = A007953(A381579(n)). - Amiram Eldar, Feb 28 2025

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula