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

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

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

Sequence in context: A093645 A366360 A182620 * A317330 A238880 A340138

Adjacent sequences: A366010 A366011 A366012 * A366014 A366015 A366016

Keyword

nonn,tabf,fini

Author

Kevin Ryde, Sep 28 2023

Status

approved