A339334 -id:A339334 - cp's OEIS frontend

A339333 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 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, 13, 12, 11, 10, 9, 8, 45, 21, 16, 14, 13, 12, 11, 10, 9, 55, 25, 19, 16, 15, 14, 13, 12, 11, 10, 66, 30, 22, 18, 17, 16, 15, 14, 13, 12, 11

Offset: 1

Pontus von Brömssen, Nov 30 2020

T(n,k) <= A339334(n,k).

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

			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 13 12 11 10  9  8
   9 | 45 21 16 14 13 12 11 10  9
  10 | 55 25 19 16 15 14 13 12 11 10
  11 | 66 30 22 18 17 16 15 14 13 12 11
  12 | 78 33 24 20 19 18 17 16 15 14 13 12
For n = 8, there is a unique optimal 3-coin system (1,3,4), with the representations
  1 = 1
  2 = 1 + 1
  3 = 3
  4 = 4
  5 = 4 + 1
  6 = 3 + 3
  7 = 4 + 3
  8 = 4 + 4
with a total of 13 = T(8,3) terms.
Shallit (2003) shows that T(99,k) is 4950, 900, 515, 389, 329, 292, 265 for k = 1..7.

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

Cf. A000217, A001212, A322832, A339334.

T(n,1) = A000217(n).
It appears that T(n,2) - T(n-1,2) = A322832(n).
T(n,k) = A339334(n,k) for all k when 1 <= n <= 7 or n = 10.
T(n,k) = A339334(n,k) for all n when k = 1 or k = 2.

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.

Original entry on oeis.org

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

Kevin Ryde, Oct 10 2023

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.

			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.

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.

Cf. A339334.

Cf. A366013 (amounts any way).

C
```
/* See links */
```

cp's OEIS Frontend

A339333 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 k-coin system of denominations.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula