A258274 - OEIS

%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