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, 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

Author

Kevin Ryde, Oct 10 2023

Keywords

• nonn
• fini
• tabf

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.

Examples

			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.
		

Links

• Kevin Ryde, Table of n, a(n) for rows 1..1000 (row lengths d=1..10 and some of d=11), flattened
• 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.

Crossrefs

Cf. A339334.

Cf. A366013 (amounts any way).

Programs

C

/* See links */