VOOZH about

URL: https://oeis.org/A366360

⇱ A366360 - OEIS

login
A366360
Irregular triangle read by rows where each row is coin denominations which make amounts 1 to 99 using the smallest total number of coins by the greedy algorithm.
1
1, 1, 10, 1, 11, 1, 5, 22, 1, 5, 23, 1, 3, 11, 37, 1, 3, 11, 38, 1, 3, 7, 16, 40, 1, 3, 7, 16, 41, 1, 3, 7, 18, 44, 1, 3, 7, 18, 45, 1, 3, 8, 20, 44, 1, 3, 8, 20, 45, 1, 2, 5, 11, 25, 62, 1, 2, 5, 11, 25, 63, 1, 2, 5, 13, 29, 64, 1, 2, 5, 13, 29, 65, 1, 2, 5, 8, 17, 27, 63
OFFSET
1,3
COMMENTS
The greedy algorithm makes a given amount by as many as possible of the largest coin, then as many as possible of the second largest towards the remainder, and so on.
A row of length d makes amounts 1 to 99 using total A339334(99,d) coins which is the minimum possible for d denominations by the greedy algorithm.
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 makes every amount with a single coin each.
Amounts 1 to 99 are based on making change in a decimal currency with coins for 1 to 99 cents, and with the greedy algorithm being an easy way to make amounts by successively taking the largest possible coin.
Minimizing the total coins minimizes the average number of coins given as change assuming each of 1 to 99 are equally likely.
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 2 rows to d=7, and also author's copy, 2002.
EXAMPLE
Triangle begins:
k=1 2 3 4 5
n=1: 1
n=2: 1, 10
n=3: 1, 11
n=4: 1, 5, 22
n=5: 1, 5, 23
n=6: 1, 3, 11, 37
n=7: 1, 3, 11, 38
n=8: 1, 3, 7, 16, 40
Rows n=6 and n=7 have length d=4 and are the two sets of denominations which, with the greedy algorithm, make amounts 1 to 99 using the minimum total A339334(99,4) = 410 coins.
PROG
(C) /* See links */
CROSSREFS
Cf. A339334.
Cf. A366013 (amounts any way).
Sequence in context: A288194 A143970 A093645 * A182620 A366013 A317330
KEYWORD
nonn,fini,tabf
AUTHOR
Kevin Ryde, Oct 10 2023
STATUS
approved