Some Extremal Postage Stamp Bases

Michael F. Challis Hempnall House Lundy Green Hempnall Norwich NR15 2NU United Kingdom

               mike@hempnallhouse.co.uk

John P. Robinson Center for Bioinformatics and Computational Biology University of Iowa Iowa City, IA 52242 USA

                john-robinson@uiowa.edu

Abstract

A set of k positive integers is a postage stamp basis for n if every positive integer up to n can be expressed as the sum of no more than h values from the set. An extremal basis is one for which n is as large as possible. For the case h = k = 8, the unique extremal basis is A = {1, 8, 13, 58, 169, 295, 831, 1036}, with n = 3485. Several other new extremal bases are presented, along with corrections to a previous article.

1 Introduction

The global postage-stamp problem consists of determining, for given positive integers h and k, a set of k positive integers

A_{k} = {a_{1} = 1 < a_{2} < ⋯ < a_{k}}

such that

(a) sums of h or fewer of these a_{j} can realize the numbers 1, 2, …, n, and (b) the value of n is as large as possible.

The h-range for a particular set A_{k} is denoted by n_{h}(A_{k}) and the extremal value by n_{h}(k). Mossige [3] presented efficient search algorithms for determining n_{h}(k), which Shallit [8] has shown to be NP hard in k. Various techniques (e.g., Challis [2]) have been used to reduce the effort to compute n_{h}(k), and a further improvement is described below.

The most recent results are presented in an appendix. Corrections and improvements to Robinson [6] are also given.

2 Tree representation

A set A_{k} is said to be admissible (strictly, h-admissible) if n_{h}(A_{k}) ≥ a_{k}; clearly inadmissible sets are of no interest when searching for the extremal value n_{h}(k).

The natural tree representation for all admissible postage stamp sets associates a_{1} = 1 with the root. The root branches out to h admissible nodes at the second level for the a_{2} values 2, 3, …, h + 1. At level three and beyond, the number of successor states for a particular state can vary. For any given admissible denomination vector A there is a path.

For the diagonal case h = k, all possible admissible sets were examined for the cases h = 6, 7, 8 and about 100 million random admissible sets for h = 9. Table 1 summarizes these experiments. The average fan-out is over all admissible sets. Note that the average fan-out increases down the tree and for the same level grows slowly with h. The number of admissible sets for h = 9 is an estimate based on the experimental average values.

Admissible  Average fan-out by level
h cases 1 2 3 4 5 6 7 8
6 5.2 × 10^{6} 6 11.8 23.9 43.2 71.6
7 5.6 × 10^{9} 7 15.0 32.5 64.0 114 234
8 2.5 × 10^{13} 8 18.5 42.8 90.8 174 307 525
9^{1} 3.7 × 10^{17} 9 22.3 54.7 125 256 472 860 1502

Table 1: Cases and fan-out

3 Algorithm for case h = k = 8

The number of admissible postage stamp sets grows rapidly for the diagonal case (Table 1). Level k − 1 has the largest average fan-out; e.g., over 500 for h = 8. We extend the method of Challis [2] wherein a set A can be rejected if it can be shown that a particular needed total x cannot be represented by A. Whereas Challis uses a software cache to speed up his generate(x) procedure, we use look-up tables. We next outline this speed-up for h = 8.

1Estimates.

For each preamble of a_{1} = 1 to a_{7}, eight intermediate look-up tables are calculated. Each table lists all totals of a_{1} to a_{7} using len denominations or less, for 1 ≤ len ≤ 8. These calculations are amortized over all the admissible values of a_{8}. Next, the target total x is checked, in one look-up step in the table len = 8, to determine if some combination of a_{1} to a_{7} totals to x. If not, then the table len = 7 is checked for the total x − a_{8}; if it exists, this yields a combination totaling x using one copy of x_{8}. If not, another a_{8} is subtracted, and the len = 6 table is checked for a combination using two copies of x_{8}. Continue down to len = 1, finally checking whether 8a_{8} = x. When a combination for x is found, the scan down the eight tables is exited and the entire process is repeated with another target x. If no combination equal to x is found in these nine steps, A with a_{8} is rejected, and another value for a_{8} is tested.

The set of target values for x are the totals needed to equal the current best A. If we generate all these totals, then n_{8}(A) is computed, and the target set is updated. This process yielded a net speed-up factor of more than 20 over the unoptimized procedure for h = 8.

There are more than 10^{13} admissible sets in the (8, 8) case. The unique extremal basis A = {1, 8, 13, 58, 169, 295, 831, 1036} with n = 3485 was determined in 2002 by the first author and independently in 2009 by the second using the program described above. Challis [2] describes two different algorithms (the K-program and H-program) and the 2002 result was obtained using the K-program, whereas the 2009 result was obtained using an independent algorithm based on the H-program.

4 New extremal sets

Many other new results have been obtained by Challis, and a complete table of extremal bases known to him at the time of writing (September 2009) is included as Appendix A to this paper.

These results have been obtained using the algorithms described in Challis [2], but with one further improvement made to the H-program which enables a number of candidate sets A_{k} to be rejected as a group.

Suppose that we have already determined a reasonably good lower bound T for n_{h}(k). In [2] we show that the following value X < T is a “difficult” target for A_{k}: that is, in almost all cases (provided h ≫ k) there is no generation of X as the sum of no more than h values from A_{k}:

X = (C_{k} − 1)a_{k} + (C_{k−1} − 1)a_{k−1} + … + (C_{2} − 1)a_{2} + (a_{2} − 1)  (1)

where

T = C_{k}a_{k} + R_{k} for 0 ≤ R_{k} < a_{k},

and

a_{i} = C_{i−1}a_{i−1} + R_{i−1} for 0 ≤ R_{i−1} < a_{i−1}, 3 ≤ i < k.

We now suppose that we can find a value x such that

x ≤ X and x > (C_{k} − 2)a_{k} + (h − C_{k} + 2)a_{k−1},

where the second condition above means that if x is to have a valid generation as the sum of no more than h values from A_{k}, then it will require at least (C_{k} − 1) values a_{k}. Of course there is no guarantee that we can find such values for given T and A_{k}, but in practice it turns out often to be the case.

Suppose further that x cannot be generated by A_{k} at all. We now show how under certain conditions it is possible to derive a value x′ which cannot be generated by A′_{k} where a′_{k} = a_{k} − r, r > 0, a′_{i} = a_{i}, 1 ≤ i < k. As a_{k} decreases, so C_{k} may increase and C_{k−1} may decrease; other values C_{i} will remain unchanged. One extra condition that we require is that C_{k−1} also remains unchanged. So we have:

a′_{k} = a_{k} − r, C′_{k} = C_{k} + j, r > 0, j ≥ 0

with

C′_{(k−1)} = C_{k−1}  (2)

Now consider

x′ = x + j(a_{k} − r) − r(C_{k} − 1)

and suppose further (our second condition) that x′, in analogy with x, satisfies

x′ > (C′_{k} − 2)a′_{k} + (h − C′_{k} + 2)a_{k−1}.  (3)

We show that A′_{k} cannot generate x′ by contradiction. Suppose that such a generation exists. Then it must include exactly (C′_{k} − 1) values a′_{k} and so will be of the form:

x′ = (C′_{k} − 1)a′_{k} + f_{k−1}a_{k−1} + … + f_{2}a_{2} + f_{1}

with

(C′_{k} − 1) + f_{k−1} + … + f_{1} ≤ h

Substituting for x′, C′_{k} and a′_{k} we have

x + j(a_{k} − r) − r(C_{k} − 1) = (C_{k} + j − 1)(a_{k} − r) + f_{k−1}a_{k−1} + … + f_{2}a_{2} + f_{1}

or

x = (C_{k} − 1)a_{k} + f_{k−1}a_{k−1} + … + f_{2}a_{2} + f_{1} with (C′_{k} − 1) + f_{k−1} + … + f_{1} ≤ h.

But since C′_{k} ≤ C_{k} this means that x can be generated by A_{k}, which is contrary to hypothesis.

We now know that x′ cannot be generated by A′_{k}, but in order to reject A′_{k} we must also show that x′ is less than T. If we write

x = (C_{k} − 1)a_{k} + F,

we have

x′ = (C_{k} − 1)a_{k} + F + j(a_{k} − r) − r(C_{k} − 1) = (C′_{k} − 1)a′_{k} + F.

From (1) we know that F ≤ (C_{k−1} − 1)a_{k−1} + … + (C_{2} − 1)a_{2} + (a_{2} − 1), and so

x′ ≤ (C′_{k} − 1)a′_{k} + (C_{k−1} − 1)a_{k−1} + … + (C_{2} − 1)a_{2} + (a_{2} − 1) = X′

where X′ is the difficult target for A′_{k}, so x′ < T.

Once we have discovered a suitable value x we can reject all sets A′_{k} for r = 0, 1, … without further ado so long as the two conditions (2) and (3) are met. It is not difficult to calculate when these conditions will fail, and as the average length of the “chain” of rejected sets is quite substantial for large h, the extra cost of the requisite book-keeping code is more than offset by the savings made. This is illustrated in the following table:

k h Average chain length Speed increase
4 150  1088  7%
5 35  395  11%
6 14  124  9%

5 Corrections to “Some extremal postage stamp 2bases”

Of minor importance are the following corrections to Table 1 of the original article [6]:

Stride s Original value Correct value
13  1,654  1,658
17  246,196  246,169
21  69,076,273  69,075,740

A counting bug was found in the original program which was most serious for s = 21. The type of 2-bases investigated by Robinson [6] were also investigated by Mossige [5],

who first describes preambles PA(s, a_{s}) and then describes a property extensibility. Consider the following family of bases derived from PA(s, a_{s}):

A_{p+s} = {1, a_{2}, …, a_{s} = b_{0}, a_{s} + s = b_{1}, a_{s} + 2s = b_{2}, …, a_{s} + ps = b_{p}}

We say PA(s, a_{s}) is extensible if A_{p+s} is admissible for all p.

Next we say that an extensible preamble PA(s, a_{s}) is symmetricizable if the family of the symmetric bases A_{k} derived from it in the obvious way (see Robinson [6]) are admissible for all k ≥ k_{0} for some k_{0}. It is straightforward to show that PA(s, a_{s}) is extensible if A_{p+s} is admissible for some p such that b_{p−1} ≥ 2b_{0}, and that it is symmetricizable if the derived symmetric basis is admissible for some p such that b_{p} ≥ 2b_{0}. These facts were used by Challis when coding his algorithm to determine optimal preambles PA(s, a_{s}).

What is perhaps surprising is that an extensible preamble is not necessarily symmetricizable, and this is the reason for the two errors in Table 2 of the original article: the preambles for s = 16 and s = 24, although extensible, are not symmetricizable. As an example, consider the 2-basis for k = 52 derived from PA(16, 61); it is easy to show that the value 415 cannot be generated by this basis.

Let us call a preamble that is extensible but not symmetricizable anomalous; then there are no anomalous preambles for s < 14. Even afterwards, there are very few, although the proportion increases slightly as s increases. For s = 21, just 1.3% of extensible preambles are anomalous.

Here are corrected versions of Table 2 and Table 3 from Robinson [6]:

Table 2: Most efficient PAs for s = 11, …, 26

\begin{matrix}s & A \\ 11 & \{1, 3, 4, 7, 8, 9, 16, 17, 21, 24, 35\} \\ 13 & \{1, 2, 5, 7, 10, 11, 19, 21, 22, 25, 29, 30, 43\} \\ 15 & \{1, 2, 5, 6, 8, 9, 13, 19, 22, 27, 29, 33, 40, 41, 56\} \\ 16 & \{1, 2, 3, 7, 8, 9, 12, 15, 22, 26, 30, 36, 37, 43, 45, 61\} \\ 17 & \{1, 2, 5, 6, 7, 12, 13, 16, 26, 28, 31, 37, 38, 42, 44, 49, 66\} \\ 19 & \{1, 2, 3, 6, 9, 11, 12, 15, 16, 27, 32, 37, 45, 48, 52, 55, 61, 62, 80\} \\ 20 & \{1, 2, 4, 5, 11, 13, 14, 19, 29, 35, 37, 43, 46, 47, 50, 52, 56, 58, 68, 88\} \\ 21 & \{1, 2, 3, 6, 10, 14, 17, 19, 26, 29, 36, 41, 49, 51, 54, 55, 58, 60, 67, 74, 95\} \\ 22 & \{1, 3, 5, 7, 8, 12, 14, 18, 26, 32, 33, 42, 43, 50, 60, 63, 68, 79, 81, 83, 97, 105\} \\ 24 & \{1, 3, 5, 6, 13, 15, 16, 18, 22, 38, 41, 44, 47, 52, 55, 58, 59, 60, 74, 80, 81, 91, 93, 117\} \\ 26 & \{1, 3, 4, 6, 7, 14, 16, 19, 20, 28, 36, 38, 39, 48, 49, 60, 61, 70, 76, 77, 89, 93, 95, 99, 109, 135\} \end{matrix}

The changes are an alternative PA(16, 61) that is symmetricizable, a new PA(17, 66) that gives rise to an optimal basis for k = 57, a replacement for PA(24, 118), and the addition of PA(26, 135).

Table 3: Best n_{2}(A_{k}) for the symmetric bases

\begin{matrix}s & a_{s} & k-range & n_{2}(A_{k}) \\ 11 & 35 & 30-40 & 22k − 344 \\ 13 & 43 & 40-43 & 26k − 504 \\ 15 & 56 & 43-52 & 30k − 676 \\ 16 & 61 & 52-56 & 32k − 780 \\ 17 & 66 & 56-58 & 34k − 892 \\ 19 & 80 & 58-62 & 38k − 1124 \\ 20 & 88 & 62-67 & 40k − 1248 \\ 22 & 105 & 67-80 & 44k − 1516 \\ 24 & 117 & 80-82 & 48k − 1836 \\ 26 & 135 & 82-? & 52k − 2164 \end{matrix}

Interestingly, Mossige missed PA(16, 61) and noted that for 9 ≤ s ≤ 19 all of the best bases were derived from preambles with odd s, so although he calculated as far as s = 23 he omitted s = 20 and s = 22.

Recently (see section 7), an exhaustive search for optimal 2-bases for k = 21 found the following to be extremal:

k n(2, k) A
21 164  {1, 3, 4, 6, 10, 13, 15, 21, 29, 37, 45, 53, 61, 69, 73, 75, 78, 79, 82, 84, 88}
{1, 3, 4, 6, 10, 13, 15, 21, 29, 37, 45, 53, 61, 69, 73, 75, 78, 79, 80, 82, 84}
{1, 3, 4, 6, 10, 13, 15, 21, 29, 37, 45, 53, 61, 67, 69, 72, 76, 78, 79, 81, 82}
{1, 3, 4, 5, 8, 14, 20, 26, 32, 38, 44, 50, 56, 62, 68, 74, 77, 78, 79, 81, 82}

This is the first example for k > 14 where there are non-symmetric extremal solutions in addition to the expected symmetric bases.

6 Discussion

It was found that n(8) = 3485 is 40 larger than the next best (8, 8) set with n_{8}(A) = 3445. The improved rejection factor technique presented in this note, when applied to the h = 9 case, appears to be about 50. Our estimate of more than 10^{17} admissible cases indicates that this approach is insufficient for h = 9 with the current computer technology. In the random experiments it was found that n(9) ≥ 9338, which is more than twice the Fibonacci lower bound of 4180 [1].

7 Appendix A: Table of extremal ranges n(h, k) with corresponding h-bases A_{k}

Note that the smaller values in the following table were previously published by the first author [2].

h = 2

k n(2, k) a_{i}
3  8  1 3 4
4  12  1 3 5 6
5  16  1 3 5 7 8
6  20  1 2 5 8 9 10
6  20  1 3 4 8 9 11
6  20  1 3 4 9 11 16
6  20  1 3 5 6 13 14
6  20  1 3 5 7 9 10
7  26  1 2 5 8 11 12 13
7  26  1 3 4 9 10 12 13
7  26  1 3 5 7 8 17 18

h = 2 (continued)

k n(2, k) a_{i}
8  32  1 2 5 8 11 14 15 16
8  32  1 3 5 7 9 10 21 22
9  40  1 3 4 9 11 16 17 19 20
10  46  1 2 3 7 11 15 19 21 22 24
10  46  1 2 5 7 11 15 19 21 22 24
11  54  1 2 3 7 11 15 19 23 25 26 28
11  54  1 2 5 7 11 15 19 23 25 26 28
11  54  1 3 4 9 11 16 18 23 24 26 27
11  54  1 3 5 6 13 14 21 22 24 26 27
12  64  1 3 4 9 11 16 21 23 28 29 31 32
13  72  1 3 4 9 11 16 20 25 27 32 33 35 36
14  80  1 2 5 8 11 14 17 20 23 24 25 51 53 55
14  80  1 3 4 5 8 14 20 26 32 35 36 37 39 40
14  80  1 3 4 9 10 15 16 21 22 24 25 51 53 55
15  92  1 3 4 5 8 14 20 26 32 38 41 42 43 45 46
16  104  1 3 4 5 8 14 20 26 32 38 44 47 48 49 51 52
17  116  1 3 4 5 8 14 20 26 32 38 44 50 53 54 55 57 58
18  128  1 3 4 5 8 14 20 26 32 38 44 50 56 59 60 61 63 64
19  140  1 3 4 5 8 14 20 26 32 38 44 50 56 62 65 66 67 69 70
20  152  1 3 4 5 8 14 20 26 32 38 44 50 56 62 68 71 72 73 75 76
21  164  1 3 4 6 10 13 15 21 29 37 45 53 61 69 73 75 78 79 82 84 88
21  164  1 3 4 6 10 13 15 21 29 37 45 53 61 69 73 75 78 79 80 82 84
21  164  1 3 4 6 10 13 15 21 29 37 45 53 61 67 69 72 76 78 79 81 82
21  164  1 3 4 5 8 14 20 26 32 38 44 50 56 62 68 74 77 78 79 81 82
22  180  1 3 4 6 10 13 15 21 29 37 45 53 61 69 77 81 83 86 87 90 92 96
22  180  1 3 4 6 10 13 15 21 29 37 45 53 61 69 77 81 83 86 87 88 90 92
22  180  1 3 4 6 10 13 15 21 29 37 45 53 61 69 75 77 80 84 86 87 89 90

8 h = 3

k n(3, k) a_{i}
3  15  1 4 5
4  24  1 4 7 8
5  36  1 4 6 14 15
6  52  1 3 7 9 19 24
6  52  1 4 6 14 17 29
7  70  1 4 5 15 18 27 34
8  93  1 3 6 10 24 26 39 41
9  121  1 3 8 9 14 32 36 51 53
10  154  1 2 6 8 19 28 40 43 91 103
11  186  1 2 3 8 11 26 38 56 69 85 89
11  186  1 4 6 13 16 27 44 49 73 81 91
12  225  1 3 8 13 15 16 49 53 84 88 108 114
13  271  1 4 6 14 16 20 39 56 79 100 113 122 131
14  323  1 2 4 9 15 27 38 43 46 97 107 127 147 157

h = 4

k n(4, k) a_{i}
3  26  1 5 8
4  44  1 3 11 18
5  70  1 3 11 15 32
6  108  1 4 9 16 38 49
6  108  1 5 8 27 29 44
7  162  1 4 9 24 35 49 51
7  162  1 4 10 15 37 50 71
7  162  1 5 8 25 31 52 71
8  228  1 3 8 19 33 39 92 102
9  310  1 4 10 11 28 33 78 118 143
9  310  1 5 7 22 31 36 83 117 133
10  422  1 4 9 24 26 42 104 115 174 185
11  550  1 4 9 20 34 52 62 137 149 229 242

h = 5

k n(5, k) a_{i}
3  35  1 6 7
4  71  1 4 12 21
4  71  1 5 12 28
5  126  1 4 9 31 51
6  211  1 4 13 24 56 61
6  211  1 5 8 33 54 67
7  336  1 4 13 24 30 87 106
8  524  1 6 8 33 48 77 183 236
9  726  1 4 13 18 51 92 163 208 223
10 1016  1 6 8 21 60 93 104 154 378 414

h = 6

k n(6, k) a_{i}
3  52  1 7 12
4  114  1 4 19 33
5  216  1 7 12 43 52
6  388  1 7 11 48 83 115
7  638  1 4 18 31 104 145 170
8 1007  1 5 18 29 97 170 219 308
9 1545  1 6 10 32 77 114 284 447 471

k = 2

Separate formulae are given for h even and h odd:

n(2t, 2) = t(t + 3)  with a_{2} = t + 1 or t + 2
n(2t + 1, 2) = t(t + 4) + 2 with a_{2} = t + 2

k = 3

\begin{matrix}h & n(h, 3) & a_{1} & a_{2} & a_{3} \\ 7 & 69 & 1 & 8 & 13 \\ 8 & 89 & 1 & 9 & 14 \\ 9 & 112 & 1 & 9 & 20 \\ 10 & 146 & 1 & 10 & 26 \\ 11 & 172 & 1 & 9 & 30 \\ 11 & 172 & 1 & 10 & 26 \\ 12 & 212 & 1 & 11 & 37 \\ 13 & 259 & 1 & 13 & 34 \\ 14 & 302 & 1 & 12 & 52 \end{matrix}  \begin{matrix}h & n(h, 3) & a_{1} & a_{2} & a_{3} \\ 15 & 354 & 1 & 12 & 52 \\ 16 & 418 & 1 & 15 & 54 \\ 17 & 476 & 1 & 14 & 61 \\ 18 & 548 & 1 & 15 & 80 \\ 19 & 633 & 1 & 18 & 65 \\ 20 & 714 & 1 & 17 & 91 \\ 21 & 805 & 1 & 17 & 91 \\ 22 & 902 & 1 & 19 & 102 \\ 22 & 902 & 1 & 20 & 92 \end{matrix}

For h ≥ 23, n(h, 3) and a_{i} are given by the formulae:

a_{2} = (6t + c_{21})
a_{3} = (2t + c_{31}) + (2t + c_{32})a_{2}
n(h, 3) = (4t + c_{41}) + (2t + c_{42})a_{2}
+(3t + c_{43})a_{3}

where h = 9t + r, 0 ≤ r ≤ 8, and c_{ij} are given by:

\begin{matrix}r & c_{21} & c_{31} & c_{32} & c_{41} & c_{42} & c_{43} \\ 0 & 3 & 1 & 1 & 0 & 0 & 0 \\ 1 & 3 & 1 & 1 & 0 & 0 & 1 \\ 2 & 5 & 2 & 1 & 1 & 0 & 1 \\ 3 & 5 & 2 & 1 & 1 & 0 & 2 \\ 4 & 7 & 3 & 1 & 2 & 0 & 2 \\ 5 & 6 & 2 & 2 & 2 & 1 & 2 \\ 6 & 8 & 3 & 2 & 3 & 1 & 2 \\ 7 & 8 & 3 & 2 & 3 & 1 & 3 \\ 8 & 10 & 4 & 2 & 4 & 1 & 3 \end{matrix}

k = 4

\begin{matrix}h & n(h, 4) & a_{1} & a_{2} & a_{3} & a_{4} \\ 7 & 165 & 1 & 5 & 24 & 37 \\ 8 & 234 & 1 & 6 & 25 & 65 \\ 9 & 326 & 1 & 5 & 34 & 60 \\ 10 & 427 & 1 & 6 & 41 & 67 \\ 11 & 547 & 1 & 7 & 48 & 85 \\ 12 & 708 & 1 & 7 & 48 & 126 \\ 13 & 873 & 1 & 9 & 56 & 155 \\ 14 & 1094 & 1 & 8 & 61 & 164 \\ 15 & 1383 & 1 & 12 & 65 & 240 \\ 16 & 1650 & 1 & 11 & 78 & 216 \\ 17 & 1935 & 1 & 11 & 90 & 252 \\ 18 & 2304 & 1 & 16 & 73 & 338 \\ 19 & 2782 & 1 & 10 & 99 & 360 \\ 20 & 3324 & 1 & 16 & 103 & 488 \\ 21 & 3812 & 1 & 16 & 103 & 488 \\ 22 & 4368 & 1 & 12 & 121 & 561 \\ 23 & 5130 & 1 & 14 & 142 & 659 \\ 24 & 5892 & 1 & 16 & 163 & 757 \\ 25 & 6745 & 1 & 20 & 149 & 860 \\ 26 & 7880 & 1 & 16 & 194 & 734 \\ 27 & 8913 & 1 & 21 & 177 & 1006 \\ 28 & 9919 & 1 & 21 & 177 & 1006 \\ 29 & 11081 & 1 & 19 & 230 & 870 \\ 30 & 12376 & 1 & 18 & 254 & 969 \\ 31 & 13932 & 1 & 25 & 211 & 1410 \end{matrix}  \begin{matrix}h & n(h, 4) & a_{1} & a_{2} & a_{3} & a_{4} \\ 32 & 15657 & 1 & 25 & 236 & 1585 \\ 33 & 17242 & 1 & 25 & 236 & 1585 \\ 34 & 18892 & 1 & 24 & 225 & 1734 \\ 35 & 21061 & 1 & 28 & 264 & 1773 \\ 36 & 23445 & 1 & 22 & 355 & 1700 \\ 37 & 25553 & 1 & 29 & 303 & 2346 \\ 38 & 27978 & 1 & 22 & 355 & 2361 \\ 39 & 31347 & 1 & 30 & 343 & 2634 \\ 40 & 33981 & 1 & 30 & 343 & 2634 \\ 41 & 36806 & 1 & 31 & 353 & 3092 \\ 42 & 39914 & 1 & 27 & 465 & 2692 \\ 43 & 43592 & 1 & 34 & 389 & 3376 \\ 44 & 47536 & 1 & 34 & 423 & 3682 \\ 45 & 51218 & 1 & 34 & 423 & 3682 \\ 46 & 54900 & 1 & 28 & 564 & 3261 \\ 46 & 54900 & 1 & 34 & 423 & 3682 \\ 47 & 59702 & 1 & 37 & 460 & 4004 \\ 48 & 63891 & 1 & 38 & 473 & 4590 \\ 49 & 69362 & 1 & 38 & 509 & 4986 \\ 50 & 74348 & 1 & 38 & 509 & 4986 \\ 51 & 81303 & 1 & 39 & 563 & 5448 \\ 52 & 86751 & 1 & 39 & 563 & 5448 \\ 53 & 92199 & 1 & 39 & 563 & 5448 \\ 54 & 97836 & 1 & 41 & 630 & 6147 \end{matrix}

For 55 ≤ h ≤ 254, n(h, 4) and a_{i} are given by one of the following three sets of formulae:

(A) :  a_{2} = (9t + c_{21})
a_{3} = (4t + c_{31}) + (3t + c_{32})a_{2}
a_{4} = (7t + c_{41}) + (2t + c_{42})a_{2} + (2t + c_{43})a_{3}
n(h, 4) = (2t + c_{51}) + (t + c_{52})a_{2} + (6t + c_{53})a_{3} + (3t + c_{54})a_{4}
(B) :  a_{2} = (9t + c_{21})
a_{3} = (2t + c_{31}) + (3t + c_{32})a_{2}
a_{4} = (7t + c_{41}) + (2t + c_{42})a_{2} + (2t + c_{43})a_{3}
n(h, 4) = (4t + c_{51}) + (3t + c_{52})a_{2} + (2t + c_{53})a_{3} + (3t + c_{54})a_{4}
(C) :  a_{2} = (9t + c_{21})
a_{3} = (4t + c_{31}) + (3t + c_{32})a_{2}
a_{4} = (7t + c_{41}) + (2t + c_{42})a_{2} + (2t + c_{43})a_{3}
n(h, 4) = (t + c_{51}) + (4t + c_{52})a_{2} + (6t + c_{53})a_{3} + (3t + c_{54})a_{4}

where h = 12t + r, 0 ≤ r ≤ 11, and c_{ij} are given in the following table: k = 4 (continued)

r c_{21} c_{31} c_{32} c_{41} c_{42} c_{43} c_{51} c_{52} c_{53} c_{54} Valid for:
0 A  2 1 0 1 0 1 −3 0 4 −1 4 ≤ t ≤ 5
0 A  1 0 0 0 0 0 −2 0 1 1 6 ≤ t ≤ 11
0 B  2 2 −1 3 −1 0 −1 −2 −1 4 12 ≤ t ≤ 21
1 A  1 0 2 1 1 0 0 0 1 0 5 ≤ t ≤ 21
2 A  2 1 1 1 1 1 −3 1 4 0 5 ≤ t ≤ 6
2 A  1 0 2 1 1 0 0 0 1 1 7 ≤ t ≤ 20
2 B  5 3 −1 6 −1 0 0 −2 −1 5 21 ≤ t ≤ 21
3 A  3 1 2 2 1 1 −1 0 4 0 1 ≤ t ≤ 20
4 A  3 1 2 2 1 1 −1 0 4 1 2 ≤ t ≤ 20
5 A  3 1 2 2 1 1 −1 0 4 2 4 ≤ t ≤ 20
6 A  3 1 2 2 1 1 −1 0 4 3 5 ≤ t ≤ 20
7 A  7 3 2 5 1 2 −1 0 7 1 2 ≤ t ≤ 11
7 A  8 4 1 7 1 0 0 1 1 5 12 ≤ t ≤ 20
8 A  7 3 3 5 2 2 −1 1 7 1 1 ≤ t ≤ 16
8 A  8 4 1 7 1 0 0 1 1 6 17 ≤ t ≤ 20
9 A  7 3 3 5 2 2 −1 1 7 2 1 ≤ t ≤ 20
10 A  7 3 3 5 2 2 −1 1 7 3 4 ≤ t ≤ 19
10 C  11 6 1 10 1 0 0 3 0 7 20 ≤ t ≤ 20
11 A  10 4 3 7 2 2 0 1 7 3 2 ≤ t ≤ 7
11 B  11 4 2 10 1 2 3 1 1 6 8 ≤ t ≤ 20

The extremal bases of type A were independently investigated by Mossige [4], who developed a procedure for determining the corresponding h-range. Selmer [7] showed the others to be given by similar formulae of type B. Type C is a variant of type A.

k = 5

\begin{matrix}h & n(h, 5) & a_{1} & a_{2} & a_{3} & a_{4} & a_{5} \\ 7 & 345 & 1 & 8 & 11 & 64 & 102 \\ 8 & 512 & 1 & 9 & 15 & 78 & 115 \\ 8 & 512 & 1 & 9 & 15 & 80 & 118 \\ 9 & 797 & 1 & 9 & 23 & 108 & 181 \\ 10 & 1055 & 1 & 8 & 27 & 119 & 194 \\ 11 & 1475 & 1 & 10 & 34 & 165 & 270 \\ 12 & 2047 & 1 & 10 & 26 & 195 & 320 \\ 13 & 2659 & 1 & 13 & 34 & 242 & 409 \\ 14 & 3403 & 1 & 11 & 48 & 278 & 720 \\ 15 & 4422 & 1 & 14 & 50 & 325 & 782 \\ 16 & 5629 & 1 & 14 & 61 & 381 & 984 \\ 17 & 6865 & 1 & 13 & 67 & 326 & 1191 \\ 18 & 8669 & 1 & 14 & 75 & 500 & 1306 \\ 19 & 10835 & 1 & 14 & 89 & 523 & 1892 \\ 20 & 12903 & 1 & 14 & 102 & 589 & 1912 \\ 21 & 15785 & 1 & 14 & 88 & 727 & 2060 \\ 22 & 18801 & 1 & 18 & 97 & 858 & 2156 \end{matrix}

k = 5 (continued)

\begin{matrix}h & n(h, 5) & a_{1} & a_{2} & a_{3} & a_{4} & a_{5} \\ 23 & 22456 & 1 & 20 & 91 & 894 & 3330 \\ 24 & 26469 & 1 & 16 & 148 & 843 & 3894 \\ 25 & 31108 & 1 & 16 & 148 & 975 & 4554 \\ 26 & 36949 & 1 & 22 & 136 & 1168 & 4227 \\ 27 & 42744 & 1 & 22 & 162 & 1372 & 4889 \\ 28 & 49436 & 1 & 25 & 139 & 1510 & 5657 \\ 29 & 57033 & 1 & 23 & 170 & 1610 & 5811 \\ 30 & 66771 & 1 & 24 & 201 & 1718 & 7596 \\ 31 & 75558 & 1 & 23 & 192 & 1976 & 7018 \\ 32 & 86303 & 1 & 25 & 180 & 1916 & 8793 \\ 33 & 96852 & 1 & 28 & 202 & 2150 & 9867 \\ 34 & 110253 & 1 & 29 & 209 & 2434 & 11256 \\ 35 & 123954 & 1 & 27 & 231 & 2495 & 11464 \\ 36 & 140688 & 1 & 30 & 227 & 2839 & 12993 \\ 37 & 158389 & 1 & 31 & 234 & 2926 & 13391 \\ 38 & 178811 & 1 & 30 & 275 & 2947 & 16472 \\ 39 & 197293 & 1 & 29 & 300 & 3671 & 16677 \\ 40 & 223580 & 1 & 29 & 266 & 3382 & 18856 \\ 41 & 247194 & 1 & 32 & 294 & 3739 & 20847 \\ 42 & 273443 & 1 & 34 & 325 & 4133 & 23063 \\ 43 & 300747 & 1 & 33 & 342 & 4560 & 25414 \\ 44 & 331461 & 1 & 32 & 393 & 4562 & 25751 \\ 45 & 368894 & 1 & 32 & 457 & 5137 & 28671 \\ 46 & 401350 & 1 & 37 & 421 & 5602 & 31205 \\ 47 & 443231 & 1 & 33 & 336 & 5224 & 34431 \\ 48 & 490325 & 1 & 36 & 515 & 6304 & 35400 \\ 49 & 536399 & 1 & 34 & 422 & 6065 & 38741 \\ 50 & 586322 & 1 & 42 & 444 & 6906 & 45542 \\ 51 & 634430 & 1 & 36 & 482 & 7132 & 40052 \\ 52 & 699698 & 1 & 35 & 570 & 6602 & 50446 \\ 53 & 754166 & 1 & 40 & 462 & 7666 & 50721 \\ 54 & 823136 & 1 & 39 & 474 & 7840 & 51893 \\ 55 & 892139 & 1 & 42 & 511 & 8494 & 56238 \\ 56 & 968914 & 1 & 39 & 489 & 8580 & 65052 \\ 57 & 1052562 & 1 & 43 & 617 & 10091 & 66380 \\ 58 & 1150377 & 1 & 46 & 606 & 9531 & 72397 \\ 59 & 1236682 & 1 & 44 & 552 & 10237 & 77846 \\ 60 & 1325927 & 1 & 41 & 631 & 11205 & 74232 \\ 61 & 1420882 & 1 & 44 & 623 & 10432 & 89278 \\ 62 & 1547688 & 1 & 49 & 646 & 12050 & 91649 \\ 63 & 1678695 & 1 & 49 & 664 & 12338 & 93848 \\ 64 & 1782370 & 1 & 52 & 705 & 13100 & 99644 \end{matrix}

k = 5 (continued)

\begin{matrix}h & n(h, 5) & a_{1} & a_{2} & a_{3} & a_{4} & a_{5} \\ 65 & 1888725 & 1 & 48 & 698 & 12988 & 111755 \\ 66 & 2036874 & 1 & 48 & 746 & 13252 & 113747 \\ 67 & 2165553 & 1 & 51 & 793 & 14087 & 120914 \end{matrix}

k = 6

\begin{matrix}h & n(h, 6) & a_{1} & a_{2} & a_{3} & a_{4} & a_{5} & a_{6} \\ 7 & 664 & 1 & 7 & 12 & 64 & 113 & 193 \\ 8 & 1045 & 1 & 9 & 14 & 65 & 170 & 297 \\ 9 & 1617 & 1 & 6 & 31 & 48 & 256 & 373 \\ 10 & 2510 & 1 & 9 & 31 & 96 & 366 & 411 \\ 11 & 3607 & 1 & 7 & 41 & 105 & 490 & 815 \\ 12 & 5118 & 1 & 6 & 47 & 120 & 565 & 946 \\ 13 & 7066 & 1 & 10 & 35 & 133 & 759 & 1304 \\ 14 & 9748 & 1 & 11 & 49 & 188 & 810 & 2109 \\ 15 & 12793 & 1 & 8 & 71 & 192 & 1215 & 1993 \\ 16 & 17061 & 1 & 15 & 49 & 285 & 1292 & 3043 \\ 17 & 22342 & 1 & 13 & 82 & 387 & 1723 & 4789 \\ 18 & 28874 & 1 & 13 & 94 & 354 & 1968 & 5062 \\ 19 & 36560 & 1 & 16 & 87 & 408 & 2351 & 6452 \\ 20 & 45754 & 1 & 17 & 93 & 436 & 2898 & 6897 \\ 21 & 57814 & 1 & 14 & 129 & 469 & 3585 & 8757 \\ 22 & 72997 & 1 & 17 & 109 & 624 & 3998 & 9618 \\ 23 & 87555 & 1 & 12 & 117 & 541 & 4487 & 11496 \\ 24 & 106888 & 1 & 19 & 138 & 782 & 5346 & 13991 \\ 25 & 129783 & 1 & 19 & 157 & 896 & 5656 & 19313 \end{matrix}

k = 7

\begin{matrix}h & n(h, 7) & a_{1} & a_{2} & a_{3} & a_{4} & a_{5} & a_{6} & a_{7} \\ 7 & 1137 & 1 & 7 & 18 & 62 & 104 & 244 & 259 \\ 7 & 1137 & 1 & 8 & 13 & 66 & 115 & 254 & 415 \\ 8 & 2001 & 1 & 6 & 28 & 47 & 127 & 412 & 602 \\ 9 & 3191 & 1 & 7 & 30 & 86 & 189 & 607 & 920 \\ 10 & 5047 & 1 & 6 & 29 & 96 & 246 & 857 & 1179 \\ 11 & 7820 & 1 & 10 & 34 & 153 & 380 & 1342 & 1487 \\ 12 & 11568 & 1 & 8 & 49 & 127 & 419 & 1566 & 2604 \\ 13 & 17178 & 1 & 12 & 40 & 223 & 544 & 2479 & 3253 \end{matrix}

k = 8

\begin{matrix}h & n(h, 8) & a_{1} & a_{2} & a_{3} & a_{4} & a_{5} & a_{6} & a_{7} & a_{8} \\ 7 & 1911 & 1 & 4 & 17 & 31 & 117 & 209 & 513 & 550 \\ 7 & 1911 & 1 & 6 & 20 & 41 & 109 & 228 & 509 & 580 \\ 8 & 3485 & 1 & 8 & 13 & 58 & 169 & 295 & 831 & 1036 \end{matrix}

References

[1] R. Alter, J. Barnett, Remarks on the postage stamp problem with applications to computers, Congr. Numer. 19 (1977), 43–59.

[2] M. F. Challis, Two new techniques for computing extremal h-bases A_{k}, Computer J. 36 (1993), 117–126.

[3] S. Mossige, Algorithms for computing the h-range of the Postage stamp problem, Math. Comp. 36 (1981), 575–582.

[4] S. Mossige, On extremal h-bases A_{4}, Math. Scand. 61 (1987), 5–16.

[5] S. Mossige, Symmetric bases with large 2-range for k ≤ 75, preprint, 1991.

[6] J. P. Robinson, Some postage stamp 2-bases, J. Integer Seq. 12 (2009), Article 09.1.1.

[7] E. S. Selmer, Associate bases in the postage stamp problem, J. Number Theory 42 (3) (1992), 320–336.

[8] J. Shallit, The computational complexity of the local postage stamp problem, ACM SIGACT News 33 (2002), 90–94.

[9] N. J. A. Sloane, The On-Line Encylopedia of Integer Sequences, 2009.

2000 Mathematics Subject Classification: Primary 11B13. Keywords: h-basis, extremal h-basis.

(Concerned with sequences \underline{A001210}, \underline{A001211}, \underline{A001216}, \underline{A001215}, \underline{A001216}, \underline{A053346}, and \underline{A053348}.)

Received September 23 2009; revised version received November 18 2009; January 27 2010. Published in Journal of Integer Sequences, January 30 2010.

Return to Journal of Integer Sequences home page.