A366013 Irregular triangle read by rows where each row lists coin denominations which make amounts 1 to 99 using the smallest total number of coins.

1, 1, 10, 1, 11, 1, 12, 19, 1, 5, 18, 25, 1, 5, 18, 29, 1, 5, 16, 23, 33, 1, 4, 6, 21, 30, 37, 1, 5, 8, 20, 31, 33, 1, 4, 9, 11, 26, 38, 44, 1, 3, 8, 9, 20, 30, 44, 48, 1, 3, 4, 9, 16, 27, 37, 44, 49, 1, 3, 4, 10, 17, 25, 37, 43, 48, 1, 3, 4, 10, 18, 22, 31, 42, 47

Offset: 1

Author

Kevin Ryde, Sep 28 2023

Keywords

• nonn
• tabf
• fini

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.

Examples

			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.
		

Links

• Kevin Ryde, Table of n, a(n) for rows 1..600 (lengths d=1..16 and some d=17), 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 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).

Crossrefs

Cf. A339333, A364607 (row n=5).

Programs

C

/* See links */