OFFSET
1,3
COMMENTS
A row of length d makes amounts 1 to 99 using a total of A339333(99,d) coins, which is the minimum possible for d denominations.
Denominations within a row are in ascending order and rows are ordered by length and then lexicographically.
Each row starts with denomination 1 since 1 is the only way to make amount 1.
This is a finite sequence, ending with a row of all denominations 1 to 99 which make all amounts using a single coin each.
Amounts 1 to 99 are based on making change in a decimal currency which uses coins for 1 to 99 cents, and notes for whole dollar parts.
Minimizing the total number of coins minimizes the average number of coins given as change, assuming each of 1 to 99 are equally likely amounts to be given.
LINKS
Kevin Ryde, C Code
Jeffrey Shallit, What This Country Needs is an 18ยข Piece, The Mathematical Intelligencer, 25-2, pages 20-23, 2003, figure 1 rows to d=7, and also author's copy, 2002.
Thomas Young, Change the Dime, not the Dollar, 1995, first set of denominations d=4 (see A364607).
EXAMPLE
Triangle begins:
k=1 2 3 4 5 6
n=1: 1
n=2: 1, 10
n=3: 1, 11
n=4: 1, 12, 19
n=5: 1, 5, 18, 25
n=6: 1, 5, 18, 29
n=7: 1, 5, 16, 23, 33
n=8: 1, 4, 6, 21, 30, 37
n=9: 1, 5, 8, 20, 31, 33
Rows n=5 and n=6 are of length d=4 and are the two sets of denominations which can make amounts 1 to 99 using the minimum total of A339333(99,4) = 389 coins.
PROG
(C) See links.
CROSSREFS
KEYWORD
nonn,tabf,fini
AUTHOR
Kevin Ryde, Sep 28 2023
STATUS
approved