A067997 -id:A067997 - cp's OEIS frontend

A067996 Number of ways of making change for n cents using coins of 1, 2, 3, 5, 10, 20, 25, 50, 100 cents (all historical U.S.A. coinage from 1 to 100 cents).

1, 1, 2, 3, 4, 6, 8, 10, 13, 16, 21, 25, 31, 37, 44, 53, 62, 72, 84, 96, 113, 128, 147, 167, 189, 216, 243, 273, 307, 342, 386, 428, 477, 529, 585, 650, 716, 788, 867, 949, 1046, 1141, 1248, 1361, 1481, 1617, 1755, 1904, 2065, 2232, 2424, 2614, 2824, 3045, 3278

Offset: 0

Rick L. Shepherd, Feb 07 2002

The U.S.A. issued the following unusual denomination coins during the 19th century: 2-cent pieces, 1864-1873; 3-cent pieces, 1851-1889; and 20-cent pieces, 1875-1878.

			a(5)=6 because change can be made for 5 cents in these 6 ways: (1) 5 1-cent coins, (2) 3 1-cent, 1 2-cent, (3) 2 1-cent, 1 3-cent, (4) 1 1-cent, 2 2-cent, (5) 1 2-cent, 1 3-cent, (6) 1 5-cent coin.

R. S. Yeoman, A Guide Book of United States Coins, Ed. Kenneth Bressett, 53rd Edition (2000). New York: St. Martin's Press, 1999. pp. 104-106, 135. (also known as The Official Red Book of United States Coins)

Cf. A067995, A067997, A000008.

CoefficientList[ Series[1/((1 - x)(1 - x^2)(1 - x^3)(1 - x^5)(1 - x^10)(1 - x^20)(1 - x^25)(1 - x^50)(1 - x^100)), {x, 0, 55} ], x ]

a(n)=polcoeff(1/((1-x)*(1-x^2)*(1-x^3)*(1-x^5)*(1-x^10)*(1-x^20)*(1-x^25)*(1-x^50)*(1-x^100)+x*O(x^n)), n)

G.f.: 1/((1-x)*(1-x^2)*(1-x^3)*(1-x^5)*(1-x^10)*(1-x^20)*(1-x^25)*(1-x^50)*(1-x^100))

Offset corrected to 0 by Ray Chandler, Dec 04 2023

A067995 Minimal number of coins needed to pay exactly n cents using coins of sizes 1, 2, 3, 5, 10, 20, 25, 50, 100 cents (all historical U.S.A. coinage from 1 to 100 cents).

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 2, 2, 3, 1, 2, 2, 2, 3, 2, 3, 3, 3, 4, 1, 2, 2, 2, 3, 1, 2, 2, 2, 3, 2, 3, 3, 3, 4, 2, 3, 3, 3, 4, 2, 3, 3, 3, 4, 2, 3, 3, 3, 4, 1, 2, 2, 2, 3, 2, 3, 3, 3, 4, 2, 3, 3, 3, 4, 3, 4, 4, 4, 5, 2, 3, 3, 3, 4, 2, 3, 3, 3, 4, 3, 4, 4, 4, 5, 3, 4, 4, 4, 5, 3, 4, 4, 4, 5, 3, 4, 4, 4, 5, 1, 2, 2, 2, 3, 2

Offset: 1

Rick L. Shepherd, Feb 06 2002

The U.S.A. issued the following unusual denomination coins during the 19th century: 2-cent pieces, 1864-1873; 3-cent pieces, 1851-1889; and 20-cent pieces, 1875-1878.

			a(69) = 5 because to pay exactly 69 cents at least 5 coins are needed: e.g. 1 of 50 cents, 1 of 10 cents, 1 of 5 cents and 2 of 2 cents.

R. S. Yeoman, A Guide Book of United States Coins, Ed. Kenneth Bressett, 53rd Edition (2000). New York: St. Martin's Press, 1999. pp. 104-106, 135. (also known as The Official Red Book of United States Coins)

Ray Chandler, Table of n, a(n) for n = 1..1000
Jean-Paul Delahaye, Quelles pièces pour faire l'appoint ?, French edition of the Scientific American, Pour la Science, N°335, septembre 2005.
Jeffrey Shallit, What this country needs is an 18c piece, The Mathematical Intelligencer, June 2003, Volume 25, Issue 2, pp 20-23.
Index entries for sequences related to making change.
Index entries for linear recurrences with constant coefficients, signature (1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1).

Cf. A053344, A067996, A067997.

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

Original entry on oeis.org

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

A339094 Number of (unordered) ways of making change for n US Dollars using the current US denominations of $1, $2, $5, $10, $20, $50 and $100 bills.

Original entry on oeis.org

1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 11, 12, 15, 16, 19, 22, 25, 28, 31, 34, 41, 44, 51, 54, 61, 68, 75, 82, 89, 96, 109, 116, 129, 136, 149, 162, 175, 188, 201, 214, 236, 249, 271, 284, 306, 328, 350, 372, 394, 416, 451, 473, 508, 530, 565, 600, 635, 670, 705, 740, 793, 828, 881, 916

Offset: 0

Robert G. Wilson v, Nov 25 2020

Not the same as A001313. First difference appears at A001313(100) being 4562, whereas a(100) is 4563; obviously one more than A001313(100).
Not the same as A057537.
Number of partitions of n into parts 1, 2, 5, 10, 20, 50 and 100.

			a(5) is 4 because 1+1+1+1+1 = 2+1+1+1 = 2+2+1 = 5.

Cf. A000008, A001299, A001300, A001301, A001306, A001302, A001306, A001310, A001312, A001313, A001314, A001319, A001343, A001362, A001364, A057537, A067996, A067997, A073031, A085502, A112024, A124146, A160551, A169718, A181934, A187243.

f[n_] := Length@ IntegerPartitions[n, All, {1, 2, 5, 10, 20, 50, 100}]; Array[f, 75, 0] (* or *)
CoefficientList[ Series[1/((1 - x) (1 - x^2) (1 - x^5) (1 - x^10) (1 - x^20) (1 - x^50) (1 - x^100)), {x, 0, 75}], x] (* or *)
Table[ Length@ FrobeniusSolve[{1, 2, 5, 10, 20, 50, 100}, n], {n, 0, 75}] (* much slower *)

coins(v[..])=my(x='x); prod(i=1, #v, 1/(1-x^v[i]))
Vec(coins(1, 2, 5, 10, 20, 50, 100)+O(x^99)) \\ Charles R Greathouse IV, Jan 24 2022

G.f.: 1/((1-x)*(1-x^2)*(1-x^5)*(1-x^10)*(1-x^20)*(1-x^50)*(1-x^100)).

cp's OEIS Frontend

A067996 Number of ways of making change for n cents using coins of 1, 2, 3, 5, 10, 20, 25, 50, 100 cents (all historical U.S.A. coinage from 1 to 100 cents).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A067995 Minimal number of coins needed to pay exactly n cents using coins of sizes 1, 2, 3, 5, 10, 20, 25, 50, 100 cents (all historical U.S.A. coinage from 1 to 100 cents).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

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

A339094 Number of (unordered) ways of making change for n US Dollars using the current US denominations of $1, $2, $5, $10, $20, $50 and $100 bills.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula