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

%I A291711 #20 Feb 28 2025 12:07:50
%S A291711 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 A291711 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 A291711 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 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), ...
%C A291711 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).
%H A291711 Amiram Eldar, <a href="/A291711/b291711.txt">Table of n, a(n) for n = 1..10000</a>
%F A291711 a(n) = A007953(A381579(n)). - _Amiram Eldar_, Feb 28 2025
%e A291711 a(7) = 3 because 7 = 3 + 3 + 1 is a minimal sum using 3 coins.
%p A291711 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 A291711 for n from 1 to 200 do: m:=n: ct:=0: for s from 1 to nn while m>0 do:
%p A291711 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 A291711 # alternative program
%p A291711 # compute index of largest Fibonacci number not larger than n.
%p A291711 fibIdx := proc(n)
%p A291711     local i;
%p A291711     for i from 1 do
%p A291711         if combinat[fibonacci](i) > n then
%p A291711             return i-1 ;
%p A291711         end if;
%p A291711     end do:
%p A291711 end proc:
%p A291711 A291711 := proc(n)
%p A291711     local fibm,gf,e,gfe ;
%p A291711     fibm := fibIdx(n) ;
%p A291711     gf := add( x^combinat[fibonacci](2*m),m=1..fibm/2) ;
%p A291711     gfe := gf ;
%p A291711     for e from 1 do
%p A291711         expand(coeftayl(gfe,x=0,n)) ;
%p A291711         if % > 0 then
%p A291711             return e ;
%p A291711         end if;
%p A291711         gfe := expand(gfe*gf) ;
%p A291711     end do:
%p A291711 end proc:
%p A291711 seq(A291711(n),n=1..100) ; # _R. J. Mathar_, Nov 11 2017
%t A291711 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 *)
%o A291711 (PARI) mx = 20; fvec = vector(mx, i, fibonacci(2*i)); f(n) = if(n <= mx, fvec[n], fibonacci(2*n));
%o A291711 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
%Y A291711 Cf. A007895 (for Fibonacci(k)), A245588 (for Fibonacci(2k-1)), A007953, A381579.
%K A291711 nonn
%O A291711 1,2
%A A291711 _Yuriko Suwa_, Aug 30 2017