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

Author

Edward Minnix III, Nov 15 2015

Keywords

• nonn

Links

• US Treasury, Denominations of Coins
• US Treasury, Denominations of Paper Currency

Crossrefs

Cf. A053344, A067997, A080897, A108536.

Programs

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()))

Extensions

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