|
%I #25 Jul 01 2023 14:27:53
%S 1,2,3,4,9,19,44,94,194,294,394,494,594,694,794,894,994,1094,1194,
%T 1294,1394,1494,1594,1694,1794,1894,1994,2094,2194,2294,2394,2494,
%U 2594,2694,2794,2894,2994
%N The smallest number of cents which cannot be made with fewer than n American coins.
%C a(n) is the smallest amount (in cents) that cannot be made with fewer than n coins.
%C The coins included are those in common circulation in the USA: 1¢, 5¢, 10¢, 25¢, 50¢ and $1 (100 cents).
%H Matthew Scroggs, <a href="/A258274/b258274.txt">Table of n, a(n) for n = 1..10006</a>
%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (2, -1).
%F From _Robert Israel_, May 31 2015: (Start)
%F a(n) = 100*n - 706 for n >= 8.
%F G.f.: x*(1 + 4*x^4 + 5*x^5 + 15*x^6 + 25*x^7 + 50*x^8)/(1-x)^2. (End)
%e The smallest value that requires 5 coins is 9¢ (5¢, 1¢, 1¢, 1¢ and 1¢). Therefore a(5)=9.
%o (Python) #
%o coins = [1,5,10,25,50,100]
%o need = [0]
%o while True:
%o ....next = len(need)
%o ....n_need = next
%o ....for coin in coins:
%o ........if coin>next:
%o ............break
%o ........n_need = min(n_need,1+need[next-coin])
%o ....need.append(n_need)
%o ....if n_need == len(seq):
%o ........print(next)
%Y Cf. A258272.
%K nonn,easy
%O 1,2
%A _Matthew Scroggs_, May 25 2015
|
