A339334 Triangle read by rows, 1 <= k <= n: T(n,k) is the sum of the minimal number of coins needed for amounts 1..n with an optimal greedy k-coin system of denominations.

1, 3, 2, 6, 4, 3, 10, 6, 5, 4, 15, 9, 7, 6, 5, 21, 11, 9, 8, 7, 6, 28, 14, 11, 10, 9, 8, 7, 36, 18, 14, 12, 11, 10, 9, 8, 45, 21, 17, 14, 13, 12, 11, 10, 9, 55, 25, 19, 16, 15, 14, 13, 12, 11, 10, 66, 30, 22, 19, 17, 16, 15, 14, 13, 12, 11

Offset: 1

Author

Pontus von Brömssen, Nov 30 2020

Keywords

• nonn
• tabl

Comments

An optimal greedy k-coin system of denominations for amounts 1..n is a set of k coin denominations such that the sum of the number of coins needed for each of the amounts 1, ..., n is as small as possible when the coins are chosen greedily, i.e., the largest coin value less than or equal to the remaining amount is always chosen.

Examples

			Triangle begins:
  n\k|  1  2  3  4  5  6  7  8  9 10 11 12
  ---|-------------------------------------
   1 |  1
   2 |  3  2
   3 |  6  4  3
   4 | 10  6  5  4
   5 | 15  9  7  6  5
   6 | 21 11  9  8  7  6
   7 | 28 14 11 10  9  8  7
   8 | 36 18 14 12 11 10  9  8
   9 | 45 21 17 14 13 12 11 10  9
  10 | 55 25 19 16 15 14 13 12 11 10
  11 | 66 30 22 19 17 16 15 14 13 12 11
  12 | 78 33 25 22 19 18 17 16 15 14 13 12
For n = 8, one of the optimal greedy 3-coin systems is (1,2,4), with the representations
  1 = 1
  2 = 2
  3 = 2 + 1
  4 = 4
  5 = 4 + 1
  6 = 4 + 2
  7 = 4 + 2 + 1
  8 = 4 + 4
with a total of 14 = T(8,3) terms.
Shallit (2003) shows that T(99,k) is 4950, 900, 526, 410, 346, 313, 286 for k = 1..7.
		

Links

• Pontus von Brömssen, Rows n = 1..40, flattened
• Jeffrey Shallit, What this country needs is an 18¢ piece, The Mathematical Intelligencer 25 (2003), issue 2, 20-23.
• Jeffrey Shallit, What this country needs is an 18¢ piece.
• Wikipedia, Change-making problem.

Crossrefs

Cf. A014616, A339333.

Formula

T(n,k) = A339333(n,k) for all k when 1 <= n <= 7 or n = 10.

T(n,k) = A339333(n,k) for all n when k = 1 or k = 2.

T(n,k) >= A339333(n,k).

T(n,k) >= 2n - k, with equality if and only if n <= A014616(k).