\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf Some Postage Stamp 2-Bases}
\vskip 1cm
\large
John P. Robinson \\
Coordinated Laboratory for Computational Genomics \\
University of Iowa \\
Iowa City, IA  52242 \\
USA \\
\href{mailto:jprobin@engineering.uiowa.edu}{\tt john-robinson@uiowa.edu} \\
\end{center}

\vskip .2 in

\begin{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.
\end{abstract}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{defin}[theorem]{Definition}
\newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}}
\newtheorem{examp}[theorem]{Example}
\newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}}
\newtheorem{rema}[theorem]{Remark}
\newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}}




\section{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<\dots<a_k\}$$
such that
\begin{enumerate}
\item sums of $h$ (or fewer) of these $a_j$ can realize the numbers $1,2,\dots,n$,
\item the value of $n$ is as large as possible.
\end{enumerate}

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 \cite{Mos81} presented efficient search algorithms for
determining $n_h(k)$, which Shallit \cite{Sha02} 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 \cite{Mos01,Sel80}.

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,\ldots,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 \cite{Mos81} 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 \seqnum{A001212} of Sloane's table \cite{Slo08}).
Our search algorithm uses some properties of these bases.

\section{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,\dots,k$.  Let $s$ denote a repeated
central difference following an initial preamble, e.g., row 4 of Table
4 \cite{Mos81}, $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
\cite{Mos81} 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 \cite{Mos81} we observe the following for these globally
extremal bases:

\begin{description}
\item[Property 1:] The first $s-1$ elements $a_j$ have distinct nonzero residues modulo $s$.
\item[Property 2:] Element $a_s$ repeats a nonzero residue modulo $s$.
\item[Property 3:] The first $s$ elements match any following sequence of difference values $s$.
\end{description}

Preamble construction:

\begin{enumerate}
\item Assume a positive integer value for $s$.
\item Enumerate all possible $s$ element 2-range preambles with properties 1 and 2.
\item Report those sets with property 3 with maximum $a_s$.
\end{enumerate}

It is easy to show that this construction is an algorithm.  Property 1
is combined with admissibility to prune the combinations.  Table
\ref{pre} 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 \emph{PA} which has two
parameters $s$ and $a_s$.

\begin{table}[H]
\caption{Number of candidate preamble cases for various stride lengths $s$.}
\centering
\bigskip
\begin{tabular}{clccl}
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\\
\end{tabular}
\label{pre}
\end{table}

From a PA we can construct a basis for  $k \geq 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 \text{ for } k \geq 2s .$$

Note that this 2-range grows as $4a_s$.  Our construction yields all
known extremal GPSP 2-bases for $k > 11$ \cite{Slo08}.  Representative
most efficient PAs are listed in Table \ref{pas}.

\begin{table}[H]
\caption{Most efficient PAs for $s=11,\dots,24$}
\bigskip
\centering
\begin{tabular}{cl}
$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{tabular}
\label{pas}
\end{table}

\section{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 \cite{Mos81} 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 \ref{pas}.

The bases constructed from Table \ref{pas}, for the ranges in Table
\ref{n2a}, are all above the $2k^2/7$ lower bound construction of
Mossige \cite{Mos81}.  Our bases suggest extremal $n_2(k)$ of about
$5k^2/16$.

\begin{table}[H]
\caption{Best $n_2(A)$ for the symmetric bases}
\bigskip
\centering
\begin{tabular}{lllllll}
$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{tabular}
\label{n2a}
\end{table}

\begin{thebibliography}{5}

\bibitem{Mos81}
S. Mossige, Algorithms for computing the $h$-range of the postage stamp
problem, {\em Math. Comp.\/} {\bf 36} (1981), 575--582.

\bibitem{Mos01}
S. Mossige, The postage stamp problem:  the extremal basis for $k=4$,
{\em J. Number Theory\/} {\bf 90} (2001), 44--61.

\bibitem{Sel80}
E. S. Selmer, On the postage stamp problem with three stamp
denominations, {\em Math. Scand.\/} {\bf 47} (1980), 29--71.

\bibitem{Sha02}
J. Shallit, The computational complexity of the local postage stamp
problem, {\em ACM SIGACT News\/} {\bf 33} (2002), 90--94.

\bibitem{Slo08}
N. J. A. Sloane,
\href{http://www.research.att.com/~njas/sequences/}{The On-Line
Encylopedia of Integer Sequences}, 2008.

\end{thebibliography}



\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 11B13.

\noindent \emph{Keywords: } $h$-basis, extremal $h$-basis.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A001212}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  September 9 2008;
revised version received  November 19 2008.
Published in {\it Journal of Integer Sequences}, December 14 2008.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}