<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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}

\usepackage{rotating}


\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 Extremal Postage Stamp Bases
}
\vskip 1cm
\large
Michael F. Challis\\
Hempnall House\\
Lundy Green Hempnall\\
Norwich NR15 2NU \\
United Kingdom\\
\href{mailto:mike@hempnallhouse.co.uk}{\tt mike@hempnallhouse.co.uk}\\
\ \\
John P. Robinson \\
Center for Bioinformatics and Computational Biology \\
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$ 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.  
\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}}

\providecommand{\e}[1]{\ensuremath{\times 10^{#1}}}

\section{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&lt;a_2&lt;\cdots&lt;a_k\}$$

\noindent such that

\begin{enumerate}

\item[(a)] sums of $h$ or fewer of these $a_j$ can realize the numbers $1,2,\ldots,n$, and
\item[(b)] the value of $n$ is as large as possible.

\end{enumerate}

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 \cite{Mos81} presented
efficient search algorithms for determining $n_h(k)$, which Shallit
\cite{Sha02} has shown to be NP hard in $k$.  Various techniques (e.g.,
Challis \cite{Cha93}) 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 \cite{Rob09} are also given.

\section{Tree representation}

A set $A_k$ is said to be admissible (strictly, $h$-admissible) if
$n_h(A_k) \geq 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,\ldots,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 \ref{pre} 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.

\begin{table}[!ht]
\centering
\begin{minipage}{\textwidth}
\centering
\bigskip

\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
\hline
 &amp; Admissible &amp; \multicolumn{8}{c|}{Average fan-out by level} \\
$h$ &amp; cases &amp; \multicolumn{1}{c}{1} &amp; \multicolumn{1}{c}{2} &amp; \multicolumn{1}{c}{3}  &amp; \multicolumn{1}{c}{4} &amp; \multicolumn{1}{c}{5} &amp; \multicolumn{1}{c}{6} &amp; \multicolumn{1}{c}{7} &amp; \multicolumn{1}{c|}{8}\\  \hline
6 &amp; $5.2\e{6}$ &amp; 6 &amp; 11.8 &amp; 23.9 &amp; 43.2 &amp; 71.6 &amp; &amp; &amp; \\  \hline
7 &amp; $5.6\e{9}$ &amp; 7 &amp; 15.0 &amp; 32.5 &amp; 64.0 &amp; 114 &amp; 234 &amp; &amp; \\  \hline
8 &amp; $2.5\e{13}$ &amp; 8 &amp; 18.5 &amp; 42.8 &amp; 90.8 &amp; 174 &amp; 307 &amp; 525 &amp; \\  \hline
9\footnotemark[1] &amp; $3.7\e{17}$ &amp; 9 &amp; 22.3 &amp; 54.7 &amp; 125 &amp; 256 &amp; 472 &amp; 860 &amp; 1502 \\  \hline
\end{tabular}
\end{minipage}
\caption{Cases and fan-out}
\label{pre}
\end{table}

\footnotetext[1]{Estimates.}

\section{\texorpdfstring{Algorithm for case $h=k=8$}{Algorithm for case h=k=8}}

The number of admissible postage stamp sets grows rapidly for the diagonal case (Table \ref{pre}).  Level $k-1$ has the largest average fan-out; e.g., over 500 for $h=8$.  We extend the method of Challis \cite{Cha93} 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 \emph{generate}($x$) procedure, we use look-up tables.  We next outline this speed-up for $h=8$.

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\leq len\leq 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 \cite{Cha93} describes two different algorithms (the \emph{K-program} and \emph{H-program}) and the 2002 result was obtained using the \emph{K-program}, whereas the 2009 result was obtained using an independent algorithm based on the \emph{H-program}.

\section{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 \cite{Cha93}, 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 \cite{Cha93} we show that the following value $X &lt; T$ is a ``difficult" target for $A_k$: that is, in almost all cases (provided $h \gg k$) there is no generation of $X$ as the sum of no more than $h$ values from $A_k$:
\begin{equation}
\label{eq:1}
X = (C_k - 1)a_k + (C_{k-1} - 1)a_{k-1} + \ldots + (C_2 - 1)a_2 + (a_2 - 1)
\end{equation}
where
$$T = C_ka_k + R_k\mbox{ for } 0 \leq R_k &lt; a_k,$$
and
$$a_i = C_{i-1}a_{i-1} + R_{i-1}\mbox{ for }0 \leq R_{i-1} &lt; a_{i-1}, \, 3 \leq i &lt; k .$$

We now suppose that we can find a value $x$ such that
	$$x \leq X \mbox{ and } x  &gt; (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 &gt; 0$, $a_{i}' = a_i$, $1 \leq i &lt; 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 &gt; 0,\,  j \geq 0$$
with
\begin{equation}
C_{(k-1)}' = C_{k-1}
\label{eq:2}
\end{equation}							

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
\begin{equation}
x'  &gt; (C_{k}' - 2)a_{k}' + (h - C_{k}' + 2)a_{k-1}.
\label{eq:3}
\end{equation}					

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} + \ldots + f_2a_2 + f_1$$  
with  
$$(C_{k}' - 1) + f_{k-1} + \ldots + f_1 \leq 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} + \ldots + f_2a_2 + f_1$$
or
$$x = (C_k - 1)a_k + f_{k-1}a_{k-1} + \ldots + f_2a_2 + f_1  \mbox{ with }  (C_{k}' - 1) + f_{k-1} + \ldots + f_1 \leq h .$$
But since $C_{k}' \leq 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 (\ref{eq:1}) we know that $F \leq (C_{k-1} - 1)a_{k-1} + \ldots + (C_2 - 1)a_2 + (a_2 - 1)$, and so
$$x' \leq (C_{k}' - 1)a_{k}' + (C_{k-1} - 1)a_{k-1} + \ldots + (C_2 - 1)a_2 + (a_2 - 1) = X'$$
where $X'$ is the difficult target for $A_{k}'$, so $x' &lt; T$.

Once we have discovered a suitable value $x$ we can reject all sets $A_{k}'$ for $r=0,1,\dots$
without further ado so long as the two conditions (\ref{eq:2}) and (\ref{eq: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:

\bigskip
\begin{center}
\begin{tabular}{cccc}
$k$&amp;$h$&amp;Average chain length&amp;Speed increase\\
4&amp;150&amp;1088&amp;7\%\\
5&amp;35&amp;395&amp;11\%\\
6&amp;14&amp;124&amp;9\%
 \end{tabular}
 \end{center}
 \bigskip

\section{Corrections to ``Some extremal postage stamp 2-bases"}

Of minor importance are the following corrections to Table 1 of the original article \cite{Rob09}:

\begin{center}
\begin{tabular}{cll}
Stride $s$&amp;Original value&amp;Correct value\\
13&amp;1,654&amp;1,658\\
17&amp;246,196&amp;246,169\\
21&amp;69,076,273&amp;69,075,740\\
\end{tabular}
\end{center}

A counting bug was found in the original program which was most serious for $s=21$.

The type of 2-bases investigated by Robinson \cite{Rob09} were also investigated by Mossige \cite{Mos91}, who first describes preambles $\mathrm{PA}(s,a_s)$ and then describes a property \emph{extensibility}.  Consider the following family of bases derived from $\mathrm{PA}(s,a_s)$:

$$A_{p+s}=\{1,a_2,\ldots,a_s=b_0,a_s+s=b_1,a_s+2s=b_2,\ldots,a_s+ps=b_p\}$$

\bigskip

We say $\mathrm{PA}(s,a_s)$ is \emph{extensible} if $A_{p+s}$ is admissible for all $p$.

Next we say that an extensible preamble $\mathrm{PA}(s,a_s)$ is
\emph{symmetricizable} if the family of the symmetric bases $A_k$
derived from it in the obvious way (see Robinson \cite{Rob09}) are
admissible for all $k\geq k_0$ for some $k_0$.  It is straightforward
to show that $\mathrm{PA}(s, a_s)$ is extensible if $A_{p+s}$ is
admissible for some $p$ such that $b_{p-1} \geq 2b_0$, and that it is
symmetricizable if the derived symmetric basis is admissible for some
$p$ such that $b_p \geq 2b_0$. These facts were used by Challis when
coding his algorithm to determine optimal preambles $\mathrm{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 $\mathrm{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 \emph{anomalous}; then there are no anomalous preambles for $s&lt;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 \cite{Rob09}:

\begin{table}[ht]
\caption{Most efficient PAs for $s=11,\ldots,26$}
\begin{center}
\begin{tabular}{cl}
$s$&amp;$A$\\
11&amp;$\{1,3,4,7,8,9,16,17,21,24,35\}$\\
13&amp;$\{1,2,5,7,10,11,19,21,22,25,29,30,43\}$\\
15&amp;$\{1,2,5,6,8,9,13,19,22,27,29,33,40,41,56\}$\\
16&amp;$\{1,2,3,7,8,9,12,15,22,26,30,36,37,43,45,61\}$\\
17&amp;$\{1,2,5,6,7,12,13,16,26,28,31,37,38,42,44,49,66\}$\\
19&amp;$\{1,2,3,6,9,11,12,15,16,27,32,37,45,48,52,55,61,62,80\}$\\
20&amp;$\{1,2,4,5,11,13,14,19,29,35,37,43,46,47,50,52,56,58,68,88\}$\\
21&amp;$\{1,2,3,6,10,14,17,19,26,29,36,41,49,51,54,55,58,60,67,74,95\}$\\
22&amp;$\{1,3,5,7,8,12,14,18,26,32,33,42,43,50,60,63,68,79,81,83,97,105\}$\\
24&amp;$\{1,3,5,6,13,15,16,18,22,38,41,44,47,52,55,58,59,60,74,80,81,91,93,117\}$\\
%25&amp;$\{1,3,5,6,9,12,15,16,20,23,33,36,39,44,57,60,67,71,72,79,88,93,99,102,124\}$\\
%25&amp;$\{1,3,4,6,9,11,12,14,15,20,32,33,41,43,47,48,60,67,71,80,88,94,99,102,124\}$\\
%26&amp;$\{1,3,5,6,9,13,15,17,20,21,30,33,44,49,50,63,64,74,77,86,92,94,97,106,114,132\}$\\
26&amp;$\{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{tabular}
\end{center}
\end{table}

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

\begin{table}[h!]
\caption{Best $n_2(A_k)$ for the symmetric bases}
\begin{center}
\begin{tabular}{lllllll}
$s$&amp;&amp;$a_s$&amp;&amp;$k$-range&amp;&amp;$n_2(A_k)$\\
11&amp;&amp;35&amp;&amp;30-40&amp;&amp;$22k-344$\\
13&amp;&amp;43&amp;&amp;40-43&amp;&amp;$26k-504$\\
15&amp;&amp;56&amp;&amp;43-52&amp;&amp;$30k-676$\\
16&amp;&amp;61&amp;&amp;52-56&amp;&amp;$32k-780$\\
17&amp;&amp;66&amp;&amp;56-58&amp;&amp;$34k-892$\\
19&amp;&amp;80&amp;&amp;58-62&amp;&amp;$38k-1124$\\
20&amp;&amp;88&amp;&amp;62-67&amp;&amp;$40k-1248$\\
22&amp;&amp;105&amp;&amp;67-80&amp;&amp;$44k-1516$\\
24&amp;&amp;117&amp;&amp;80-82&amp;&amp;$48k-1836$\\
%25&amp;&amp;124&amp;&amp;84-86&amp;&amp;$50k-2004$\\
%26&amp;&amp;132&amp;&amp;86-88&amp;&amp;$52k-2176$\\
26&amp;&amp;135&amp;&amp;82-?&amp;&amp;$52k-2164$
\end{tabular}
\end{center}
\end{table}

Interestingly, Mossige missed $\mathrm{PA}(16,61)$ and noted that for $9\leq s\leq 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 \ref{sec:AppA}), an exhaustive search for optimal 2-bases for $k=21$ found the following to be extremal:

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

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


\section{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)  \geq9338$, which is more than twice the Fibonacci lower bound of
4180 \cite{Alt77}.

\section{\texorpdfstring{Appendix A:  Table of extremal ranges $n(h,k)$ with corresponding $h$-bases $A_k$}{Appendix A:  Table of extremal ranges n(h,k) with corresponding h-bases Ak}}
\label{sec:AppA}

Note that the smaller values in the following table were previously published by the first author \cite{Cha93}.

%Put the full text of results from Dr. challis' email in the Appendix as Table 4, or a several tables, in whatever format takes the least time for you to prepare.  Keep the current version in case the reviewer(s)/editor require just the new results.

%It would be really nice to include all the results as an Appendix (ie after the references); new results since 1993 could always be identified by an asterisk. But if the referees really don't want this, could I ask for a layout for Table 4 that is more akin to my 1993 appendix, with separate sections for h =2, h =3, k= 4, k =5 etc, and right-aligned columns of numbers?  The attached PostScript files show what I mean. We should also include the new results for k = 4: in 1993 I had confirmed that the sets defined by the formulae (A) and (B) were extremal as far as h=157,  but can now confirm for all h &lt;= 241.

\bigskip

$\mathbf{h=2}$

\bigskip

\begin{tabular}{r@{\hspace{.2in}}r@{\hspace{.2in}}rrrrrrrrrrrrrrrrrrrrrr}
$k$&amp;\multicolumn{1}{c}{$n(2,k)$}&amp;&amp;$a_i$\\
3 &amp; 8 &amp;&amp; 1&amp;3&amp;4\\
4 &amp; 12 &amp;&amp; 1&amp;3&amp;5&amp;6\\
5 &amp; 16 &amp;&amp; 1&amp;3&amp;5&amp;7&amp;8\\
6 &amp; 20 &amp;&amp; 1&amp;2&amp;5&amp;8&amp;9&amp;10\\
6 &amp; 20 &amp;&amp; 1&amp;3&amp;4&amp;8&amp;9&amp;11\\
6 &amp; 20 &amp;&amp; 1&amp;3&amp;4&amp;9&amp;11&amp;16\\
6 &amp; 20 &amp;&amp; 1&amp;3&amp;5&amp;6&amp;13&amp;14\\
6 &amp; 20 &amp;&amp; 1&amp;3&amp;5&amp;7&amp;9&amp;10\\
7 &amp; 26 &amp;&amp; 1&amp;2&amp;5&amp;8&amp;11&amp;12&amp;13\\
7 &amp; 26 &amp;&amp; 1&amp;3&amp;4&amp;9&amp;10&amp;12&amp;13\\
7 &amp; 26 &amp;&amp; 1&amp;3&amp;5&amp;7&amp;8&amp;17&amp;18\\
\end{tabular}

\begin{sidewaystable}
$\mathbf{h=2}$ \textbf{(continued)}

\bigskip

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

\newpage
$\mathbf{h=3}$

\smallskip

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

\bigskip

$\mathbf{h=4}$

\smallskip

\begin{tabular}{r@{\hspace{.2in}}r@{\hspace{.2in}}rrrrrrrrrrrr}
$k$&amp;\multicolumn{1}{c}{$n(4,k)$}&amp;&amp;$a_i$\\
3 &amp; 26 &amp;&amp; 1&amp;5&amp;8\\
4 &amp; 44 &amp;&amp; 1&amp;3&amp;11&amp;18\\
5 &amp; 70 &amp;&amp; 1&amp;3&amp;11&amp;15&amp;32\\
6 &amp; 108 &amp;&amp; 1&amp;4&amp;9&amp;16&amp;38&amp;49\\
6 &amp; 108 &amp;&amp; 1&amp;5&amp;8&amp;27&amp;29&amp;44\\
7 &amp; 162 &amp;&amp; 1&amp;4&amp;9&amp;24&amp;35&amp;49&amp;51\\
7 &amp; 162 &amp;&amp; 1&amp;4&amp;10&amp;15&amp;37&amp;50&amp;71\\
7 &amp; 162 &amp;&amp; 1&amp;5&amp;8&amp;25&amp;31&amp;52&amp;71\\
8 &amp; 228 &amp;&amp; 1&amp;3&amp;8&amp;19&amp;33&amp;39&amp;92&amp;102\\
9 &amp; 310 &amp;&amp; 1&amp;4&amp;10&amp;11&amp;28&amp;33&amp;78&amp;118&amp;143\\
9 &amp; 310 &amp;&amp; 1&amp;5&amp;7&amp;22&amp;31&amp;36&amp;83&amp;117&amp;133\\
10 &amp; 422 &amp;&amp; 1&amp;4&amp;9&amp;24&amp;26&amp;42&amp;104&amp;115&amp;174&amp;185\\
11 &amp; 550 &amp;&amp; 1&amp;4&amp;9&amp;20&amp;34&amp;52&amp;62&amp;137&amp;149&amp;229&amp;242\\
\end{tabular}

\bigskip

$\mathbf{h=5}$

\smallskip

\begin{tabular}{r@{\hspace{.2in}}r@{\hspace{.2in}}rrrrrrrrrrr}
$k$&amp;\multicolumn{1}{c}{$n(5,k)$}&amp;&amp;$a_i$\\
3 &amp; 35 &amp;&amp; 1&amp;6&amp;7\\
4 &amp; 71 &amp;&amp; 1&amp;4&amp;12&amp;21\\
4 &amp; 71 &amp;&amp; 1&amp;5&amp;12&amp;28\\
5 &amp; 126 &amp;&amp; 1&amp;4&amp;9&amp;31&amp;51\\
6 &amp; 211 &amp;&amp; 1&amp;4&amp;13&amp;24&amp;56&amp;61\\
6 &amp; 211 &amp;&amp; 1&amp;5&amp;8&amp;33&amp;54&amp;67\\
7 &amp; 336 &amp;&amp; 1&amp;4&amp;13&amp;24&amp;30&amp;87&amp;106\\
8 &amp; 524 &amp;&amp; 1&amp;6&amp;8&amp;33&amp;48&amp;77&amp;183&amp;236\\
9 &amp; 726 &amp;&amp; 1&amp;4&amp;13&amp;18&amp;51&amp;92&amp;163&amp;208&amp;223\\
10 &amp; 1016 &amp;&amp; 1&amp;6&amp;8&amp;21&amp;60&amp;93&amp;104&amp;154&amp;378&amp;414\\
\end{tabular}

\newpage
$\mathbf{h=6}$

\bigskip

\begin{tabular}{r@{\hspace{.2in}}r@{\hspace{.2in}}rrrrrrrrrr}
$k$&amp;\multicolumn{1}{c}{$n(6,k)$}&amp;&amp;$a_i$\\
3 &amp; 52 &amp;&amp; 1&amp;7&amp;12\\
4 &amp; 114 &amp;&amp; 1&amp;4&amp;19&amp;33\\
5 &amp; 216 &amp;&amp; 1&amp;7&amp;12&amp;43&amp;52\\
6 &amp; 388 &amp;&amp; 1&amp;7&amp;11&amp;48&amp;83&amp;115\\
7 &amp; 638 &amp;&amp; 1&amp;4&amp;18&amp;31&amp;104&amp;145&amp;170\\
8 &amp; 1007 &amp;&amp; 1&amp;5&amp;18&amp;29&amp;97&amp;170&amp;219&amp;308\\
9 &amp; 1545 &amp;&amp; 1&amp;6&amp;10&amp;32&amp;77&amp;114&amp;284&amp;447&amp;471\\
\end{tabular}

\bigskip

$\mathbf{k=2}$

\bigskip

Separate formulae are given for $h$ even and $h$ odd:

$$\begin{array}{rclll}
n(2t,2) &amp; = &amp; t(t+3) &amp;&amp; \mbox{with } a_2=t+1 \mbox{ or } t+2\\
n(2t+1,2) &amp; = &amp; t(t+4)+2 &amp;&amp; \mbox{with } a_2=t + 2
\end{array}$$

\bigskip

$\mathbf{k=3}$

\bigskip

\begin{minipage}{2.5in}
\begin{tabular}{r@{\hspace{.2in}}r@{\hspace{.2in}}rrrr}
$h$&amp;\multicolumn{1}{c}{$n(h,3)$}&amp;&amp;$a_1$&amp;$a_2$&amp;$a_3$\\
7 &amp; 69 &amp;&amp; 1&amp;8&amp;13\\
8 &amp; 89 &amp;&amp; 1&amp;9&amp;14\\
9 &amp; 112 &amp;&amp; 1&amp;9&amp;20\\
10 &amp; 146 &amp;&amp; 1&amp;10&amp;26\\
11 &amp; 172 &amp;&amp; 1&amp;9&amp;30\\
11 &amp; 172 &amp;&amp; 1&amp;10&amp;26\\
12 &amp; 212 &amp;&amp; 1&amp;11&amp;37\\
13 &amp; 259 &amp;&amp; 1&amp;13&amp;34\\
14 &amp; 302 &amp;&amp; 1&amp;12&amp;52\\
\end{tabular}
\end{minipage}
\begin{minipage}{2.5in}
\begin{tabular}{r@{\hspace{.2in}}r@{\hspace{.2in}}rrrr}
$h$&amp;\multicolumn{1}{c}{$n(h,3)$}&amp;&amp;$a_1$&amp;$a_2$&amp;$a_3$\\
15 &amp; 354 &amp;&amp; 1&amp;12&amp;52\\
16 &amp; 418 &amp;&amp; 1&amp;15&amp;54\\
17 &amp; 476 &amp;&amp; 1&amp;14&amp;61\\
18 &amp; 548 &amp;&amp; 1&amp;15&amp;80\\
19 &amp; 633 &amp;&amp; 1&amp;18&amp;65\\
20 &amp; 714 &amp;&amp; 1&amp;17&amp;91\\
21 &amp; 805 &amp;&amp; 1&amp;17&amp;91\\
22 &amp; 902 &amp;&amp; 1&amp;19&amp;102\\
22 &amp; 902 &amp;&amp; 1&amp;20&amp;92\\
\end{tabular}
\end{minipage}

\vspace{.2in}

\begin{minipage}{2.8in}

For $h \geq 23$, $n(h,3)$ and $a_i$ are given by the formulae:

\bigskip

$\begin{array}{rcl}
      a_2 &amp; = &amp; (6t + c_{21})\\
      a_3 &amp; = &amp; (2t + c_{31}) + (2t + c_{32})a_2\\
      n(h,3) &amp; = &amp; (4t + c_{41}) + (2t + c_{42})a_2\\
      &amp;&amp; \hspace{.2in} +(3t + c_{43})a_3
\end{array}$
\end{minipage}
\hspace{.2in}
\begin{minipage}{2.6in}

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

\bigskip
\centering
\begin{tabular}{rrrrrrrr}
$r$&amp;&amp;$c_{21}$&amp;$c_{31}$&amp;$c_{32}$&amp;$c_{41}$&amp;$c_{42}$&amp;$c_{43}$\\
0&amp;&amp;3&amp;1&amp;1&amp;0&amp;0&amp;0\\
1&amp;&amp;3&amp;1&amp;1&amp;0&amp;0&amp;1\\
2&amp;&amp;5&amp;2&amp;1&amp;1&amp;0&amp;1\\
3&amp;&amp;5&amp;2&amp;1&amp;1&amp;0&amp;2\\
4&amp;&amp;7&amp;3&amp;1&amp;2&amp;0&amp;2\\
5&amp;&amp;6&amp;2&amp;2&amp;2&amp;1&amp;2\\
6&amp;&amp;8&amp;3&amp;2&amp;3&amp;1&amp;2\\
7&amp;&amp;8&amp;3&amp;2&amp;3&amp;1&amp;3\\
8&amp;&amp;10&amp;4&amp;2&amp;4&amp;1&amp;3\\
\end{tabular}
\end{minipage}

\newpage

$\mathbf{k=4}$

\bigskip

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

\bigskip

For $55 \leq h \leq 254$, $n(h,4)$ and $a_i$ are given by one of the following three sets of formulae:

\bigskip

$\begin{array}{rrcl}
        (A): &amp; a_2 &amp; = &amp; (9t + c_{21})\\
        &amp; a_3 &amp; = &amp; (4t + c_{31}) + (3t + c_{32})a_2\\
        &amp; a_4 &amp; = &amp; (7t + c_{41}) + (2t + c_{42})a_2 + (2t + c_{43})a_3\\
        &amp; n(h,4) &amp; = &amp; (2t + c_{51}) + ( t + c_{52})a_2 + (6t + c_{53})a_3 + (3t + c_{54})a_4
\end{array}$

\bigskip

$\begin{array}{rrcl}
        (B): &amp; a_2 &amp; = &amp; (9t + c_{21})\\
        &amp; a_3 &amp; = &amp; (2t + c_{31}) + (3t + c_{32})a_2\\
        &amp; a_4 &amp; = &amp; (7t + c_{41}) + (2t + c_{42})a_2 + (2t + c_{43})a_3\\
        &amp; n(h,4) &amp; = &amp; (4t + c_{51}) + (3t + c_{52})a_2 + (2t + c_{53})a_3 + (3t + c_{54})a_4
\end{array}$

\bigskip

$\begin{array}{rrcl}
        (C): &amp; a_2 &amp; = &amp; (9t + c_{21})\\
        &amp; a_3 &amp; = &amp; (4t + c_{31}) + (3t + c_{32})a_2\\
        &amp; a_4 &amp; = &amp; (7t + c_{41}) + (2t + c_{42})a_2 + (2t + c_{43})a_3\\
        &amp; n(h,4) &amp; = &amp; (t + c_{51}) + (4t + c_{52})a_2 + (6t + c_{53})a_3 + (3t + c_{54})a_4
\end{array}$

\bigskip

where  $h = 12t + r$,  $0 \leq r \leq 11$,  and $c_{ij}$ are given in the following table:

\newpage

$\mathbf{k=4}$ \textbf{(continued)}
\vspace{-.1in}
\begin{center}
\begin{tabular}{rrrrrrrrrrrrrr}
$r$&amp;&amp;&amp;$c_{21}$&amp;$c_{31}$&amp;$c_{32}$&amp;$c_{41}$&amp;$c_{42}$&amp;$c_{43}$&amp;$c_{51}$&amp;$c_{52}$&amp;$c_{53}$&amp;$c_{54}$&amp;Valid for:\\
0&amp;A&amp;&amp;2&amp;1&amp;0&amp;1&amp;0&amp;1&amp;$-3$&amp;0&amp;4&amp;$-1$&amp;$ 4 \leq t \leq  5$\\
0&amp;A&amp;&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;$-2$&amp;0&amp;1&amp;1&amp;$ 6 \leq t \leq 11$\\
0&amp;B&amp;&amp;2&amp;2&amp;$-1$&amp;3&amp;$-1$&amp;0&amp;$-1$&amp;$-2$&amp;$-1$&amp;4&amp;$12 \leq t \leq 21$\\
1&amp;A&amp;&amp;1&amp;0&amp;2&amp;1&amp;1&amp;0&amp;0&amp;0&amp;1&amp;0&amp;$ 5 \leq t \leq 21$\\
2&amp;A&amp;&amp;2&amp;1&amp;1&amp;1&amp;1&amp;1&amp;$-3$&amp;1&amp;4&amp;0&amp;$ 5 \leq t \leq  6$\\
2&amp;A&amp;&amp;1&amp;0&amp;2&amp;1&amp;1&amp;0&amp;0&amp;0&amp;1&amp;1&amp;$ 7 \leq t \leq 20$\\
2&amp;B&amp;&amp;5&amp;3&amp;$-1$&amp;6&amp;$-1$&amp;0&amp;0&amp;$-2$&amp;$-1$&amp;5&amp;$21\leq t\leq21$\\
3&amp;A&amp;&amp;3&amp;1&amp;2&amp;2&amp;1&amp;1&amp;$-1$&amp;0&amp;4&amp;0&amp;$ 1 \leq t \leq 20$\\
4&amp;A&amp;&amp;3&amp;1&amp;2&amp;2&amp;1&amp;1&amp;$-1$&amp;0&amp;4&amp;1&amp;$ 2 \leq t \leq 20$\\
5&amp;A&amp;&amp;3&amp;1&amp;2&amp;2&amp;1&amp;1&amp;$-1$&amp;0&amp;4&amp;2&amp;$ 4 \leq t \leq 20$\\
6&amp;A&amp;&amp;3&amp;1&amp;2&amp;2&amp;1&amp;1&amp;$-1$&amp;0&amp;4&amp;3&amp;$ 5 \leq t \leq 20$\\
7&amp;A&amp;&amp;7&amp;3&amp;2&amp;5&amp;1&amp;2&amp;$-1$&amp;0&amp;7&amp;1&amp;$ 2 \leq t \leq 11$\\
7&amp;A&amp;&amp;8&amp;4&amp;1&amp;7&amp;1&amp;0&amp;0&amp;1&amp;1&amp;5&amp;$12 \leq t \leq 20$\\
8&amp;A&amp;&amp;7&amp;3&amp;3&amp;5&amp;2&amp;2&amp;$-1$&amp;1&amp;7&amp;1&amp;$1 \leq t \leq 16$\\
8&amp;A&amp;&amp;8&amp;4&amp;1&amp;7&amp;1&amp;0&amp;0&amp;1&amp;1&amp;6&amp;$	17 \leq t \leq 20$\\
9&amp;A&amp;&amp;7&amp;3&amp;3&amp;5&amp;2&amp;2&amp;$-1$&amp;1&amp;7&amp;2&amp;$	1 \leq t \leq 20$\\   
10&amp;A&amp;&amp;7&amp;3&amp;3&amp;5&amp;2&amp;2&amp;$-1$&amp;1&amp;7&amp;3&amp;$	4 \leq t \leq 19$\\
10&amp;C&amp;&amp;11&amp;6&amp;1&amp;10&amp;1&amp;0&amp;0&amp;3&amp;0&amp;7&amp;$20\leq t\leq20$\\   
11&amp;A&amp;&amp;10&amp;4&amp;3&amp;7&amp;2&amp;2&amp;0&amp;1&amp;7&amp;3&amp;$	2 \leq t \leq  7$\\
11&amp;B&amp;&amp;11&amp;4&amp;2&amp;10&amp;1&amp;2&amp;3&amp;1&amp;1&amp;6&amp;$ 8 \leq t \leq 20$\\
\end{tabular}
\end{center}

The extremal bases of type A were independently investigated by Mossige \cite{Mos87}, who developed a procedure for determining the corresponding $h$-range. Selmer \cite{Sel92} showed the others to be given by similar formulae of type B.  Type C is a variant of type A.

\bigskip

$\mathbf{k=5}$

\smallskip

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

\newpage
$\mathbf{k=5}$ \textbf{(continued)}

\bigskip

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

$\mathbf{k=5}$ \textbf{(continued)}

\bigskip

\begin{tabular}{r@{\hspace{.2in}}r@{\hspace{.2in}}rrrrrr}
$h$&amp;\multicolumn{1}{c}{$n(h,5)$} &amp;&amp; $a_1$&amp;$a_2$&amp;$a_3$&amp;$a_4$&amp;$a_5$\\
65 &amp; 1888725 &amp;&amp; 1&amp;48&amp;698&amp;12988&amp;111755\\
66 &amp; 2036874 &amp;&amp; 1&amp;48&amp;746&amp;13252&amp;113747\\
67 &amp; 2165553 &amp;&amp; 1&amp;51&amp;793&amp;14087&amp;120914\\
\end{tabular}

\bigskip

$\mathbf{k=6}$

\bigskip

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

\bigskip

$\mathbf{k=7}$

\bigskip

\begin{tabular}{r@{\hspace{.2in}}r@{\hspace{.2in}}rrrrrrrr}
$h$&amp;\multicolumn{1}{c}{$n(h,7)$}&amp;&amp;$a_1$&amp;$a_2$&amp;$a_3$&amp;$a_4$&amp;$a_5$&amp;$a_6$&amp;$a_7$\\
7 &amp; 1137 &amp;&amp; 1&amp;7&amp;18&amp;62&amp;104&amp;244&amp;259\\
7 &amp; 1137 &amp;&amp; 1&amp;8&amp;13&amp;66&amp;115&amp;254&amp;415\\
8 &amp; 2001 &amp;&amp; 1&amp;6&amp;28&amp;47&amp;127&amp;412&amp;602\\
9 &amp; 3191 &amp;&amp; 1&amp;7&amp;30&amp;86&amp;189&amp;607&amp;920\\
10 &amp; 5047 &amp;&amp; 1&amp;6&amp;29&amp;96&amp;246&amp;857&amp;1179\\
11 &amp; 7820 &amp;&amp; 1&amp;10&amp;34&amp;153&amp;380&amp;1342&amp;1487\\
12 &amp; 11568 &amp;&amp; 1&amp;8&amp;49&amp;127&amp;419&amp;1566&amp;2604\\
13 &amp; 17178 &amp;&amp; 1&amp;12&amp;40&amp;223&amp;544&amp;2479&amp;3253\\
\end{tabular}

\bigskip

$\mathbf{k=8}$

\bigskip

\begin{tabular}{r@{\hspace{.2in}}r@{\hspace{.2in}}rrrrrrrrr}
$h$&amp;\multicolumn{1}{c}{$n(h,8)$}&amp;&amp;$a_1$&amp;$a_2$&amp;$a_3$&amp;$a_4$&amp;$a_5$&amp;$a_6$&amp;$a_7$&amp;$a_8$\\
7 &amp; 1911 &amp;&amp; 1&amp;4&amp;17&amp;31&amp;117&amp;209&amp;513&amp;550\\
7 &amp; 1911 &amp;&amp; 1&amp;6&amp;20&amp;41&amp;109&amp;228&amp;509&amp;580\\
8 &amp; 3485 &amp;&amp; 1&amp;8&amp;13&amp;58&amp;169&amp;295&amp;831&amp;1036\\
\end{tabular}



\pagebreak
\begin{thebibliography}{5}

\bibitem{Alt77}
R. Alter, J. Barnett, Remarks on the postage stamp problem with
applications to computers, {\em Congr. Numer.\/} {\bf 19} (1977),
43--59.

\bibitem{Cha93}
M. F. Challis, Two new techniques for computing extremal $h$-bases
$A_k$, {\em Computer J.} {\bf 36} (1993), 117--126.

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

\bibitem{Mos87}
S. Mossige, On extremal $h$-bases $A_4$, {\em Math. Scand.\/} {\bf 61}
(1987), 5--16.

\bibitem{Mos91}
S. Mossige, Symmetric bases with large 2-range for $k\leq 75$, preprint,
1991.

\bibitem{Rob09}
J. P. Robinson, Some postage stamp 2-bases, \emph{J. Integer Seq.}
\textbf{12} (2009), \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL12/Robinson/robinson4.html"}{Article 09.1.1}.

\bibitem{Sel92}
E. S. Selmer, Associate bases in the postage stamp problem, {\em J.
Number Theory\/} {\bf 42} (3) (1992), 320--336.

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

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

\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 sequences
\seqnum{A001210}, \seqnum{A001211}, \seqnum{A001216}, \seqnum{A001215}, \seqnum{A001216}, \seqnum{A053346}, and \seqnum{A053348}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received September 23 2009;
revised version received  November 18 2009; January 27 2010.
Published in {\it Journal of Integer Sequences}, January 30 2010.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                


                                                                                

</pre></body></html>