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

Links

Table of n, a(n) for n=0..99.

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. A067997, A080897, A108536.

Sequence in context: A053840 A010883 A011542 * A053344 A092196 A100878

Adjacent sequences: A260685 A260686 A260687 * A260689 A260690 A260691

Keyword

nonn

Author

Edward Minnix III, Nov 15 2015

Extensions

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

Status

approved