A080897 -id:A080897 - cp's OEIS frontend

A108536 Maximal "digit" in position n from right of numbers in "base American money" representation (A080897).

4, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 4, 1, 4, 1, 9

Offset: 0

Rick L. Shepherd, Jun 08 2005

These are the largest numbers of pennies, nickels, dimes, etc. respectively, given in change determined by the usual method of giving as many of the largest denomination as possible before moving to the next smaller, etc. (application of greedy algorithm) in order to use the fewest total coins/bills - and assuming there is always an adequate supply of each denomination.
Beyond the 100-dollar denomination explicitly mentioned in A080897, this sequence's terms correspond to 500, 1000, 5000 and 10000-dollar denominations. This sequence considers the 100000-dollar denomination to be the largest (even though it was never designed for public use -- see the U.S. Treasury link for details); hence it doesn't have a corresponding limiting term. If this denomination is disregarded, so should be a(15) = 9.
As the four other largest denominations are no longer distributed (although still legal tender), a(11) through a(14) could also be disregarded. In considering a practical, general-purpose change-making algorithm/machine, more helpful might be variations of A080897 and this sequence that ignore infrequently-circulating denominations such as the 50-cent piece and two-dollar bill.

			a(6) = 2 as, say, A080897(1499) = 102011204, where the "digit" in position 6 (counting from the rightmost being position 0) is 2 (corresponding to two two-dollar bills) -- and no term of A080897 contains a value larger than 2 in position 6. A080897(1499) also exhibits maximal values in positions 0, 2, 3, 4 and 8.

U.S. Treasury, Denominations of Coins
U.S. Treasury, Denominations of Currency

Cf. A080897, A067997 (contains links to other coin denomination info).

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.

Original entry on oeis.org

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

Edward Minnix III, Nov 15 2015

nonn

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

Cf. A053344, A067997, A080897, A108536.

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

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

cp's OEIS Frontend

A108536 Maximal "digit" in position n from right of numbers in "base American money" representation (A080897).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Extensions