A339334 - OEIS

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

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,2

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.

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.

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

EXAMPLE

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.

CROSSREFS

Cf. A014616, A339333.

Sequence in context: A123042 A121647 A339333 * A360259 A340873 A033940

Adjacent sequences: A339331 A339332 A339333 * A339335 A339336 A339337

KEYWORD

nonn,tabl

AUTHOR

Pontus von Brömssen, Nov 30 2020

STATUS

approved