\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{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 A Note on the Postage Stamp Problem
}
\vskip 1cm
\large
Amitabha Tripathi \\
Department of Mathematics \\
Indian Institute of Technology \\
Hauz Khas \\
New Delhi - 110016 \\
India \\
\href{mailto:atripath@maths.iitd.ac.in}{\tt atripath@maths.iitd.ac.in} \\
\end{center}

\vskip .2 in

\begin{abstract}
Let $h,k$ be fixed positive integers, and let $A$ be any set of
positive integers. Let $hA:=\{a_1+a_2+\cdots+a_r:a_i \in A, r \le
h\}$ denote the set of all integers representable as a sum of no
more than $h$ elements of $A$, and let $n(h,A)$ denote the largest
integer $n$ such that $\{1,2,\ldots,n\} \subseteq hA$. Let
$n(h,k)=\max_A\:n(h,A)$, where the maximum is taken over all sets
$A$ with $k$ elements. The purpose of this note is to determine
$n(h,A)$ when the elements of $A$ are in arithmetic progression.
In particular, we determine the value of $n(h,2)$.
\end{abstract}

\newtheorem{thm}{Theorem}
\newtheorem{corollary}[thm]{Corollary}




%\usepackage{amsmath}
%\usepackage{amssymb}
%\usepackage{amsthm}
%\usepackage{amsfonts}
%\usepackage{latexsym}
%\usepackage{amscd}
%\usepackage{mathrsfs}
%\usepackage[mathcal]{euscript}
%
%\setlength{\oddsidemargin}{0.0in}
%\setlength{\evensidemargin}{0.0in}
%\setlength{\topmargin}{0.0in}
%\setlength{\textheight}{9in}
%\setlength{\textwidth}{6.3in}

\newenvironment{pf}{\noindent{\bf Proof. }}{\hfill $\Box$ \\}
\def\lf{\lfloor}
\def\rf{\rfloor}
\def\l{\lambda}
\def\N{\mathbb N}


\section{Introduction}

A set $A=\{a_1<a_2<\cdots<a_k\}$ is called an {\em $h$-basis\/}
for a positive integer $n$ if each of $1,2,\ldots,n$ is
expressible as a sum of {\em at most\/} $h$ (not necessarily
distinct) elements of $A$. In order that $A$ be an $h$-basis for
$n$, it is necessary that $a_1=1$. For fixed positive integers $h$
and $k$, let $n(h,k)$ denote the largest integer for which an
$h$-basis of $k$ elements exists. The problem of determining
$n(h,k)$ is apparently due to Rohrbach \cite{Roh37a}, and has been
studied often. A large and extensive bibliography can be found in
a paper of Alter and Barnett \cite{AB80}. The {\em Postage Stamp
Problem\/} derives its name from the situation where we require
the largest integer $n=n(h,k)$ such that all stamp values from $1$
to $n$ may be made up from a collection of $k$ integer-valued
stamp denominations with the restriction that an envelope that can
have no more than $h$ stamps, repetitions being allowed. An
additional related problem is to determine all sets with $k$
elements that form an $h$-basis for $n(h,k)$.
We call such a set an {\em extremal $h$-basis\/}.  

It is easy to see that $n(1,k)=k$ with unique extremal basis
$\{1,2,\ldots,k\}$ and that $n(h,1)=h$ with unique extremal basis
$\{1\}$. The result $n(h,2)=\lf(h^2+6h+1)/4\rf$ with unique
extremal basis $\{1,(h+3)/2\}$ for odd $h$ and $\{1,(h+2)/2\}$ and
$\{1,(h+4)/2\}$ for even $h$ has been rediscovered several times,
for instance by St{\"{o}}hr \cite{Sto55a,Sto55b} and by Stanton,
Bate and Mullin \cite{SBM74}. No other closed-form formula is
known for any other pair $(h,k)$ where one of $h,k$ is fixed. In
addition, $n(h,k)$ is known for several pairs $(h,k)$; see
\cite{AB80}. Asymptotic bounds for $n(h,k)$ are due to Rohrbach
\cite{Roh37a}, while bounds for $n(h,3)$ and $n(2,k)$ are due to
Hofmeister \cite{Hof68}, and due to Rohrbach \cite{Roh37a},
Klotz \cite{Klo69}, Moser \cite{Mos60} and others, respectively. \\

Let $h,k$ be fixed positive integers, and let $A$ be any set of
positive integers. Let 
$$hA:=\{a_1+a_2+\cdots+a_r:a_i \in A, r \le
h\}$$
denote the set of all integers representable as a sum of no
more than $h$ elements of $A$, and let $n(h,A)$ denote the largest
integer $n$ such that $\{1,2,\ldots,n\} \subseteq hA$. Thus
$n(h,k)=\max_A\:n(h,A)$, where the maximum is taken over all sets
$A$ with $k$ elements. The purpose of this note is to determine
$n(h,A)$ when the elements of $A$ are in arithmetic progression. In
particular, this easily gives the value of $n(h,2)$.

\section{Main Result}

Throughout this section, $h,k,d$ are fixed positive integers. Let
$$A=\{1,1+d,1+2d,\ldots,1+(k-1)d\}$$
be a $k$-term arithmetic progression. In order that
$n \in hA$, it is necessary and sufficient that the equation
\begin{equation}
x_0+(1+d)x_1+(1+2d)x_2+\cdots+(1+(k-1)d)x_{k-1} = \sum_{i=0}^{k-1}\,x_i +
\left(\sum_{i=0}^{k-1}\,ix_i\right)d = n
\end{equation}
has a solution, with $x_i \in {\N} \cup 0$ for all $i$ and 
$\sum_{i=0}^{k-1}\,x_i \le h$. \\

Suppose $x_0,x_1,\ldots,x_{k-1}$ are nonnegative integers whose sum is at most $a$. Then
$x_1+2x_2+\cdots+(k-1)x_{k-1}$ assumes all values $0,1,\ldots,(k-1)a$ as the $x_i$'s range over
nonnegative integers whose sum does not exceed $a$. Indeed, to achieve the sum $q(k-1)+r$ for
$0 \le q<a$ and $0 \le r<k-1$ or for $q=a$, we may choose $x_{k-1}=q$, $x_r=0$ or $1$
according as $r=0$ or $r>0$, and all other $x_i$ zero. We are now in a position to state our
main result. \\

\begin{thm} Let $h,k,d$ be positive integers. Then
\[ n(h,\{1,1+d,1+2d,\ldots,1+(k-1)d\}) = \left\{ \begin{array}{ll}
     h, & \mbox{if $h \le d-1$}; \\
     h+(k-1)(h+1-d)d, & \mbox{if $h \ge d$}.
                                                 \end{array}
                                         \right.
\]
\end{thm}


\begin{pf}
We write $A=\{1,1+d,1+2d,\ldots,1+(k-1)d\}$. The case $h \le d-1$
is easy to see. Henceforth, we assume $h \ge d$. Suppose
$x_0,x_1,\ldots,x_{k-1}$ are chosen such that the sum in (1)
equals $n=n(h,A)$. If $\sum_{i=0}^{k-1}\,x_i<h$, $x_0$ may be
incremented by $1$ without violating the restriction on the sum of
the $x_i$'s, thereby achieving the sum $n(h,A)+1$. Thus
$\sum_{i=0}^{k-1}\,x_i=h$, so that $n(h,A) \equiv h$ (mod $d$) by
(1) and $m:=\sum_{i=0}^{k-1}\,ix_i \le (k-1)h$.

Now $h+1+md \in hA$ if and only if (1) has a solution with $\sum_{i=0}^{k-1}\,x_i=h+1-{\l}d$
and $\sum_{i=0}^{k-1}\,ix_i=m+{\l}$ for some ${\l} \in {\N}$. Such a simultaneous solution
exists precisely when $m+{\l} \le (h+1-{\l}d)(k-1)$, that is, when
$m \le (h+1-{\l}d)(k-1)-{\l} \le (h+1-d)(k-1)-1$. Thus $h+1+md \not\in hA$ for
$m \ge (h+1-d)(k-1)$, and $n(h,A) \le h+(k-1)(h+1-d)d$.

It remains to show that every positive integer less than or equal
to $h+(k-1)(h+1-d)d$ is an element of $hA$. Any such integer $N$
can be expressed as $r+qd$, where $r,q$ satisfy the inequalities
$1 \le r \le h$ and $q \le (k-1)r$, as follows. We choose the
largest $r \equiv N$ (mod $d$) which is also less than or equal to
$h$. Such an $r$ is greater than or equal to $h+1-d$, so that
$qd=N-r \le N-(h+1-d) \le h+(h+1-d)((k-1)d-1)<((k-1)(h+1-d)+1)d$,
and $q \le (k-1)(h+1-d) \le (k-1)r$. Thus
$\sum_{i=0}^{k-1}\,x_i=r$ and $\sum_{i=0}^{k-1}\,ix_i=q$ is
simultaneously solvable by the argument immediately preceding the
Theorem. This completes the proof.
\end{pf}


\begin{corollary}
For $h \ge 1$,
\[ n(h,2) = \left\lf \frac{h^2+6h+1}{4} \right\rf. \]
Moreover, the only extremal basis is $\{1,(h+3)/2\}$ if $h$ is odd, and $\{1,(h+2)/2\}$ and
$\{1,(h+4)/2\}$ if $h$ is even. \\
\end{corollary}

\begin{pf}
From Theorem 1,
\[ n(h,2) = h+\max_{d \ge 1}\,(h+1-d)d = h+\left\lf \frac{(h+1)^2}{4} \right
   \rf = \left\lf \frac{h^2+6h+1}{4} \right\rf. \]
It is easy to see that the maximum is achieved at $d=(h+1)/2$, so that there is only one
extremal basis if $h$ is odd and two such bases if $h$ is even.
\end{pf}

\bigskip

\noindent{\bf Remark.}  The function $n(h,2)$ is sequence A014616 in
Sloane's table \cite{Sloane}.

\bigskip

\section{Acknowledgments}

The author is grateful to the referee for a careful reading and
for numerous suggestions all of which have helped improve the
presentation of this article.


\begin{thebibliography}{9}

\bibitem{Roh37a}
H. Rohrbach, Ein Beitrag zur additiven Zahlentheorie, {\em Math.
Z.\/}, {\bf 42}, 1--30, 1937.

\bibitem{AB80}
R. Alter and J. A. Barnett, A postage stamp problem, {\em Amer.
Math. Monthly\/}, {\bf 87}, 206--210, 1980.

\bibitem{Sto55a}
A. St{\"{o}}hr, Gel{\"{o}}ste und ungel{\"{o}}ste Fragen
{\"{u}}ber Basen der nat{\"{u}}rlichen Zahlenreihe, I, {\em J.
reine Angew. Math.\/}, {\bf 194}, 40--65, 1955.

\bibitem{Sto55b}
A. St{\"{o}}hr, Gel{\"{o}}ste und ungel{\"{o}}ste Fragen
{\"{u}}ber Basen der nat{\"{u}}rlichen Zahlenreihe, II, {\em J.
reine Angew. Math.\/}, {\bf 194}, 111--140, 1955.

\bibitem{SBM74}
R. G. Stanton, J. A. Bate and R. C. Mullin, Some tables for the
postage stamp problem, {\em Congr. Numer.\/}, Proceedings of the
Fourth Manitoba Conference on Numerical Mathematics, Winnipeg,
{\bf 12}, 351--356, 1974.

\bibitem{Hof68}
G. R. Hofmeister, Asymptotische Absch{\"{a}}tzungen f{\"{u}}r
dreielementige Extremalbasis in nat{\"{u}}rlichen Zahlen, {\em J.
reine Angew. Math.\/}, {\bf 232}, 77--101, 1968.

\bibitem{Klo69}
W. Klotz, Eine obere Schranke f{\"{u}}r die Reichweite einer
Extremalbasis zweiter Ordnung, {\em J. reine Angew. Math.\/}, {\bf
238}, 161--168, 1969.

\bibitem{Mos60}
L. Moser, On the representation of $1,2,\dots,n$ by sums, {\em
Acta Arith.\/}, {\bf 6}, 11--13, 1960.

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

\end{thebibliography}



\bigskip
\hrule
\bigskip

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

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

\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received July 1 2005;
revised version received  December 15 2005.
Published in {\it Journal of Integer Sequences},
December 15 2005.

\bigskip
\hrule
\bigskip

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


\end{document}