A260688 a(n) = the least number of pieces of currency of denominations .01, .05, .10, .25, 1, 5, 10, 20, 50, 100 that the greedy algorithm uses to make n times .01 (n "cents") in change.

0, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 3, 4, 5, 6, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 2, 3, 4, 5, 6, 2, 3, 4, 5, 6, 3, 4, 5, 6, 7, 3, 4, 5, 6, 7, 2, 3, 4, 5, 6, 3, 4, 5, 6, 7, 3, 4, 5, 6, 7, 4, 5, 6, 7, 8, 4, 5, 6, 7, 8, 3, 4, 5, 6, 7, 4, 5, 6, 7, 8, 4, 5, 6, 7, 8, 5, 6, 7, 8, 9, 5, 6, 7, 8, 9

Offset

0,3

Comments

The coin system defined by these values is canonical (the greedy algorithm always yields the minimal number of coins). This has been verified for all amounts less than $150, which is sufficient. Please refer to Kozen and Zaks (1994). - Adam Reichert, Jun 25 2026

Links

Adam Reichert, Table of n, a(n) for n = 0..10000

D. Kozen and S. Zaks, Optimal Bounds for the Change-Making Problem, Theoretical Computer Science, 123 (1994), 377-388.

Adam Reichert, Python program for verifying if a coin system is canonical

US Treasury, Denominations of Coins

US Treasury, Denominations of Paper Currency

Prog

(Python)
def how_many(cents):
    #d = denominations
    d = ['$0.01', '$0.05', '$0.10', '$0.25',
         '$1', '$5', '$10', '$20', '$50', '$100']
    coins = {coin: 100*float(str(coin)[1:]) for coin in d}
    how_many = {d[i]: 0 for i in range(10)}
    while len(d) != 0:
        how_many[d[-1]] = cents // coins[d[-1]]
        cents %= coins[d[-1]]
        d.pop()
    return int(sum(how_many.values()))

Crossrefs

Cf. A053344, A067997, A080897, A108536.

Sequence in context: A053840 A010883 A011542 * A053344 A092196 A100878

Adjacent sequences: A260685 A260686 A260687 * A260689 A260690 A260691

Keyword

nonn,easy

Author

Edward Minnix III, Nov 15 2015

Extensions

Edited by N. J. A. Sloane, Apr 24 2016

Status

approved