OFFSET
1,2
COMMENTS
a(n) is the smallest amount (in cents) that cannot be made with fewer than n coins.
The coins included are those in common circulation in the USA: 1¢, 5¢, 10¢, 25¢, 50¢ and $1 (100 cents).
LINKS
Matthew Scroggs, Table of n, a(n) for n = 1..10006
Index entries for linear recurrences with constant coefficients, signature (2,-1).
FORMULA
From Robert Israel, May 31 2015: (Start)
a(n) = 100*n - 706 for n >= 8.
G.f.: x*(1 + 4*x^4 + 5*x^5 + 15*x^6 + 25*x^7 + 50*x^8)/(1-x)^2. (End)
EXAMPLE
The smallest value that requires 5 coins is 9¢ (5¢, 1¢, 1¢, 1¢ and 1¢). Therefore a(5)=9.
PROG
(Python)
from math import inf
def A258274_list(up_to=3000, coins=(1, 5, 10, 25, 50, 100)):
terms = []
coins_needed = [0] + [inf] * up_to
for c in coins:
for i in range(c, up_to + 1):
coins_needed[i] = min(coins_needed[i], coins_needed[i - c] + 1)
record = 0
return [n for n, x in enumerate(coins_needed) if x > record and (record := x)]
# David Radcliffe, Jun 22 2025
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Matthew Scroggs, May 25 2015
STATUS
approved
