Computing L(k,m) in the simpleminded way takes time exponential in k but for fixed k polynomial in m. Thus, it is fairly easy to compute the table rows for small k, but it takes more effort to compute the table columns for small m.
Let B(k,m) be the polytope (ball) defined by |m_1|+...+|m_k| <= m, and let V(k,m) = |B(k,m)| be its volume.
Clearly, the maximum number of distinct nonzero amounts that can be paid using at most m coin exchanges is at most (V(k,m)-1)/2, and a forteriori we have L(k,m) <= (V(k,m)-1)/2.
For V(k,m) we have the recurrence relation V(k,m) = V(k-1,m) + V(k-1,m-1) + V(k,m-1) (for k,m > 0) and V(k,0) = V(0,m) = 1.
For V(k,m) we have the formula V(k,m) = sum over i from 0 to min(k,m) of (k choose i).(m choose i).2^i.
While searching, an interesting detail is the question how far one has to search.
If we are to reach a bound L, and w_k <= 2L+1, then all residue classes mod w_k must be covered, so w_k cannot be larger than V(k-1,m).
If w_k >= 2L+1, then for each choice of m_1,...,m_{k-1} there is at most one choice for m_k such that m_1.w_1+...+m_k.w_k lies in the interval -L..L, so the total number of points in that interval is at most V(k-1,m) and L <= (V(k-1,m)-1)/2.
Proposition If L(k,m) > (V(k-1,m)-1)/2, then w_k <= V(k-1,m).
So, if the best value L found after searching up to V(k-1,m) satisfies L > (V(k-1,m)-1)/2, then L = L(k,m). This is the case for all values claimed to be exact in the above table for which k <= 5.
It is useful to sharpen this bound a bit. If, for some positive integer a, we have a.w_k <= 2L+1, then all residue classes mod a.w_k are covered. We find if a=2b+1 is odd, that a.w_k <= V(k-1,m) + 2V(k-1,m-1) + ... + 2V(k-1,m-b), and if a=2b is even, that a.w_k <= V(k-1,m) + 2V(k-1,m-1) + ... + 2V(k-1,m-b+1)+V(k-1,m-b). Let us call the right hand side of the inequality here E(k,m,a). If a.w_k >= 2L+1, then for each choice of m_1,...,m_{k-1} there are at most a choices for m_k such that m_1.w_1+...+m_k.w_k lies in the interval -L..L, so the total number of points in that interval is at most E = E(k,m,a), and L <= (E-1)/2.
Proposition If L(k,m) > (E(k,m,a)-1)/2, then w_k <= E(k,m,a)/a <= V(k-1,m).
Suppose we take all sums of coins and replace everywhere w_k by -w_{k-1}. Now the sums remain the same modulo w_{k-1}+w_k but there are no more than V(k-1,m) of them, so if w_{k-1}+w_k <= 2L+1 then all residue classes mod w_{k-1}+w_k are covered and w_{k-1}+w_k <= V(k-1,m). And if w_{k-1}+w_k >= 2L+1 then there is at most one multiple of w_{k-1}+w_k that can be added to bring a given sum into -L..L, so 2L+1 <= V(k-1,m). This proves:
Proposition If L(k,m) > (V(k-1,m)-1)/2, then w_{k-1}+w_k <= V(k-1,m).
Combining the last two ideas, consider things modulo a(w_{k-1}+w_k). If a(w_{k-1}+w_k) <= 2L+1 then all residue classes mod a(w_{k-1}+w_k) are covered so that a(w_{k-1}+w_k) <= E(k,m,a). If a(w_{k-1}+w_k) >= 2L+1, then 2L+1 <= E(k,m,a).
Proposition If L(k,m) > (E(k,m,a)-1)/2, then w_{k-1}+w_k <= E(k,m,a)/a <= V(k-1,m).
These propositions are fairly successful in case the hypothesis is satisfied. It seems much more difficult to bound w_k when L <= (V(k-1,m)-1)/2. For example, L(6,3) = 110 and (V(5,3)-1)/2 = 115. How far do we have to search in order to really prove that L(6,3) = 110?
However, the special case m=2 is easier, and it is possible to bound w_k.
For a given set W of coin values, let L(W) = L(W,m) be the corresponding maximum value L such that each integer in 1..L is representable.
For finding L(W) the two algorithms are: (i) For v=1,2,... find whether v is represented. As soon as some value v is not represented, L(W) = v-1. This has the disadvantage that many coin combinations are examined multiple (up to L+1) times. (ii) Initialize a boolean array to false, go over all coin combinations and set the represented values to true. Then find the smallest array element that is still set to false. This considers each coin combination at most once so is much better, except that if the array is large, the initialization takes a significant amount of time. The best strategy here is to pick length m*w_{max} so that no overflow can occur, but to initialize it only up to and including index L+1. This suffices, unless the present sequence is a record-breaking one, but there aren't many of those, so it doesn't matter that we have to redo the computation in that case.
In practice it turns out that both strategies are equally good on average when all possible sets W are generated. But this can only mean that very often already some very small number like 1 or 2 is not represented.
The most obvious strategy consists of generating all possible sets W = {w_1,...,w_k} lexicographically, say with w_k bounded by a prespecified w_{max}, perhaps as found in the above proposition, and determining for each set W the corresponding value L(W).
When k is large and m is small a better strategy is to pick the values one or two at a time, not in any lexicografic order, and make sure that each new value improves the current maximum. Keep track of a set of chosen values and a set of forbidden values, so that no set is considered twice.
Comments and improvements are welcome.
Andries Brouwer - aeb@cwi.nl