login
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.
3
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,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.
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
Sequence in context: A123042 A121647 A339333 * A360259 A340873 A033940
KEYWORD
nonn,tabl
AUTHOR
STATUS
approved