A258274 The smallest number of cents which cannot be made with fewer than n American coins.

1, 2, 3, 4, 9, 19, 44, 94, 194, 294, 394, 494, 594, 694, 794, 894, 994, 1094, 1194, 1294, 1394, 1494, 1594, 1694, 1794, 1894, 1994, 2094, 2194, 2294, 2394, 2494, 2594, 2694, 2794, 2894, 2994

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) #
coins = [1, 5, 10, 25, 50, 100]
need = [0]
while True:
....next = len(need)
....n_need = next
....for coin in coins:
........if coin>next:
............break
........n_need = min(n_need, 1+need[next-coin])
....need.append(n_need)
....if n_need == len(seq):
........print(next)

Crossrefs

Cf. A258272.

Sequence in context: A220364 A243902 A086865 * A228126 A352197 A192988

Adjacent sequences: A258271 A258272 A258273 * A258275 A258276 A258277

Keyword

nonn,easy

Author

Matthew Scroggs, May 25 2015

Status

approved