A339333 - OEIS

The OEIS is supported by the many generous donors to the OEIS Foundation.

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give

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

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

OFFSET

1,2

COMMENTS

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

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

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

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

CROSSREFS

Cf. A000217, A001212, A322832, A339334.

Sequence in context: A360265 A123042 A121647 * A339334 A360259 A340873

Adjacent sequences: A339330 A339331 A339332 * A339334 A339335 A339336

KEYWORD

nonn,tabl

AUTHOR

Pontus von Brömssen, Nov 30 2020

STATUS

approved