Some Postage Stamp 2-Bases

John P. Robinson Coordinated Laboratory for Computational Genomics University of Iowa Iowa City, IA 52242 USA

                    john-robinson@uiowa.edu

Abstract

A set of k integers is a 2-basis if every positive integer up to n can be expressed as the sum of no more than 2 values from the set; an extremal 2-basis is one for which n is as large as possible. A new algorithm extends the lower bound of Mossige for symmetric bases. An assumed modulo structure is combined with local search. These 2-bases match all known extremal values for k from 11 to 20. Bases out to k = 82 are given.

1 Introduction

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

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

such that

1. sums of h (or fewer) of these a_{j} can realize the numbers 1, 2, …, n,

2. the value of n is as large as possible.

This extremal total is denoted n_{h}(k). The h-range for a particular set A is denoted n_{h}(A). Informally, h denotes the maximum number of stamps on an envelope, while k is the number of stamp denominations.

Mossige [1] presented efficient search algorithms for determining n_{h}(k), which Shallit [4] has shown to be NP-hard. The extremal GPSP for k = 3 has been solved for any h and Mossige has constructed very good h-bases for k = 4 which are believed to be extremal [2, 3].

This note considers only the h = 2 case. Most of the known extremal GPSP 2-bases are symmetric, i.e., a_{i} + a_{k−i} = a_{k} for i = 1, …, k. For some values of k there are several extremal 2-bases solutions. For k = 11, there are 4 solutions, two of them being symmetric. The instance k = 10 is the only known case with no symmetric extremal solution.

Mossige [1] gave extremal symmetric 2-bases for k from 15 to 30 (Table 4). To date, these out to k = 20 have been shown to be globally extremal (see \underline{A001212} of Sloane’s table [5]). Our search algorithm uses some properties of these bases.

2 Construction

We consider only the h = 2 case and will generate symmetric 2-bases, i.e. a_{i} + a_{k−i} = a_{k} for i = 1, …, k. Let s denote a repeated central difference following an initial preamble, e.g., row 4 of Table 4 [1], k = 18, has the first half difference sequence 1, 2, 1, 1, 3, 6, 6, 6, 6, and we say s = 6. The complete difference sequence is k elements long with the second half the reverse of the first half.

We refer to s as the stride of the bases. The initial s elements a_{i} we call the preamble; the central basis elements a_{i} corresponding to the differences of s we call the amble. Mossige [1] has the same 6 element preamble (1, 2, 1, 1, 3, 6) for the first 7 values of k; the amble just gets longer as k increases.

From Table 4 [1] we observe the following for these globally extremal bases:

Property 1: The first s − 1 elements a_{j} have distinct nonzero residues modulo s.

Property 2: Element a_{s} repeats a nonzero residue modulo s.

Property 3: The first s elements match any following sequence of difference values s.

Preamble construction:

1. Assume a positive integer value for s.

2. Enumerate all possible s element 2-range preambles with properties 1 and 2.

3. Report those sets with property 3 with maximum a_{s}.

It is easy to show that this construction is an algorithm. Property 1 is combined with admissibility to prune the combinations. Table 1 lists the experiential number of preamble cases that were examined. This number grows by a factor of about 4 for each increment in s. We call a resulting preamble a PA which has two parameters s and a_{s}.

Table 1: Number of candidate preamble cases for various stride lengths s.

Stride s Cases  Stride s Cases
11  192  18  1,044,846
12  634  19  3,822,468
13  1,654  20  17,365,943
14  6,277  21  69,076,273
15  18,757  22  334,698,203
16  73,775  23  1,438,317,540
17  246,196  24  7,367,635,861

From a PA we can construct a basis for k ≥ 2s. The PA and its reversal have 2s elements; thus the length of the amble is k − 2s. The largest element a_{k} is equal to the sum of all the differences. For a symmetric basis, n_{2}(A) = 2a_{k}, and

n_{2}(A) = 2ks + 4a_{s} − 4s^{2} for k ≥ 2s.

Note that this 2-range grows as 4a_{s}. Our construction yields all known extremal GPSP 2-bases for k > 11 [5]. Representative most efficient PAs are listed in Table 2.

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

\begin{matrix}s & \{a_{s}\} \\ 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, 5, 8, 10, 12, 19, 22, 23, 25, 30, 31, 36, 43, 45, 61\} \\ 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, 2, 3, 5, 9, 12, 15, 17, 23, 28, 32, 35, 37, 44, 45, 66, 79, 82, 86, 91, 94, 102, 112, 118\} \end{matrix}

3 Observations

Some values of s yield poor bases, e.g. s = 7 is bested by either s = 6 or s = 8. Other values have singular points e.g. s = 10 has 2 symmetric bases [1] which tie s = 9 and s = 11 at k = 30. In Table 3 we report a best s for k from 30 to about 82. The corresponding PAs are in Table 2.

The bases constructed from Table 2, for the ranges in Table 3, are all above the 2k^{2}/7 lower bound construction of Mossige [1]. Our bases suggest extremal n_{2}(k) of about 5k^{2}/16.

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

\begin{matrix}s & a_{s} & k range & n_{2}(A) \\ 11 & 35 & 30-40 & 22k − 344 \\ 13 & 43 & 40-43 & 26k − 504 \\ 15 & 56 & 43-50 & 30k − 676 \\ 16 & 61 & 50-58 & 32k − 780 \\ 19 & 80 & 58-62 & 38k − 1124 \\ 20 & 88 & 62-66 & 40k − 1248 \\ 21 & 95 & 66-68 & 42k − 1380 \\ 22 & 105 & 68-79 & 44k − 1516 \\ 24 & 118 & 79-82 & 48k − 1832 \end{matrix}

References

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

[2] S. Mossige, The postage stamp problem: the extremal basis for k = 4, J. Number Theory 90 (2001), 44–61.

[3] E. S. Selmer, On the postage stamp problem with three stamp denominations, Math. Scand. 47 (1980), 29–71.

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

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

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

(Concerned with sequence \underline{A001212}.)

Received September 9 2008; revised version received November 19 2008. Published in Journal of Integer Sequences, December 14 2008.

Return to Journal of Integer Sequences home page.