<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[english]{babel}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{rotating}

\renewcommand{\algorithmiccomment}[1]{\hfill\small\{#1\}\normalsize}

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

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

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

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf A Meet-in-the-Middle Algorithm for Finding \\
\vskip .1in
Extremal Restricted Additive 2-Bases
}
\vskip 1cm
\large
Jukka Kohonen \\
Department of Mathematics and Statistics\\
P. O. Box 68\\
FI-00014 University of Helsinki\\
Finland \\
\href{mailto:jukka.kohonen@helsinki.fi}{\tt jukka.kohonen@helsinki.fi}
\end{center}

\vskip .2 in

% These macros are used to create underbraces and overbraces
% within a matrix
\newcommand{\underblock}[2]{
  \underbrace{\begin{matrix}#1\end{matrix}}_{#2}
}
\newcommand{\overblock}[2]{
  \overbrace{\begin{matrix}#1\end{matrix}}^{#2}
}


\begin{abstract}
An additive 2-basis with range $n$ is {\em restricted} if its largest
element is $n/2$.  Among the restricted 2-bases of given length $k$,
the ones that have the greatest range are {\em extremal restricted}.
We describe an algorithm that finds the extremal restricted 2-bases of
a given length, and we list them for lengths up to $k=41$.
\end{abstract}


\section{Introduction}
Let $n$ be a positive integer.  An {\it additive 2-basis for~$n$}, or
more briefly a {\it basis for~$n$}, is a set of integers $A_k =
\{0=a_0 &lt; a_1 &lt; \cdots &lt; a_k\}$ such that every integer in $[0,n]$ is
the sum of two of its elements, not necessarily distinct.  The {\it
  length} of the basis is $k$.  The largest possible~$n$ for a basis
$A_k$ is its {\it range} and denoted $n_2(A_k)$.  The maximum range
among all bases of length~$k$ is $n_2(k)$, and a basis that attains this
maximum is {\it extremal} \cite[pp.\ 123--127]{guy2004}.

A basis $A_k$ is {\it admissible} if $n_2(A_k) \ge a_k$, {\it
  restricted} if $n_2(A_k) \ge 2a_k$, and {\it symmetric} if $a_i +
a_{k-i} = a_k$ for all $0\le i\le k$.  Since for any basis $n_2(A_k) \le
2a_k$, a restricted basis has in fact $n_2(A_k) = 2a_k$ exactly.

The maximum range among restricted bases is called the {\it extremal
  restricted range} and denoted $n_2^*(k)$, and an {\it extremal
  restricted basis} is one that attains this maximum.  For many values
of $k$, at least some of the extremal bases are restricted, so that
$n_2^*(k)=n_2(k)$.  This is not always true: a counterexample is
$k=10$, where $n_2^*(10)=44$, but $n_2(10)=46$ (see
Table~\ref{table:k10}).  Thus, when $k=10$, the extremal restricted
bases are not extremal bases, and the extremal bases are neither
restricted nor symmetric.

Similarly, the maximum range among symmetric bases can be called the
{\it extremal symmetric range}, and a basis that attains this maximum
can be called {\it extremal symmetric basis}.  Extremal symmetric
bases are known up to $k=30$ due to Mossige \cite{mossige1981}.

\begin{table}[bt]
\begin{center}
\begin{tabular}{ll|l}
range &amp; notes &amp; basis \\
\hline
44 &amp; R,A &amp; 0 1 2 3 7 11 15 17 20 21 22 $\dagger$ \\
44 &amp; R,S &amp; 0 1 2 3 7 11 15 19 20 21 22 \\
44 &amp; R,S &amp; 0 1 2 5 7 11 15 17 20 21 22 \\
44 &amp; R,A &amp; 0 1 2 5 7 11 15 19 20 21 22 $\dagger$ \\
44 &amp; R,S &amp; 0 1 2 5 8 11 14 17 20 21 22 \\
44 &amp; R,A &amp; 0 1 3 4 6 11 13 18 19 21 22 $\ddagger$ \\
44 &amp; R,S &amp; 0 1 3 4 9 11 13 18 19 21 22 \\
44 &amp; R,A &amp; 0 1 3 4 9 11 16 18 19 21 22 $\ddagger$ \\
\hline
46 &amp; NR,A,E &amp; 0 1 2 3 7 11 15 19 21 22 24 \\
46 &amp; NR,A,E &amp; 0 1 2 5 7 11 15 19 21 22 24 \\
\hline
\end{tabular}
\caption{With length $k=10$, there are eight extremal restricted bases
  (which are not extremal bases); and two extremal nonrestricted
  bases; all listed by Wagstaff \cite{wagstaff1979}.  The two bases
  marked with~$\dagger$ are mirror images of each other; similarly the
  two bases marked with~$\ddagger$.  Notes: R = restricted, NR =
  nonrestricted; S = symmetric, A = asymmetric; E = extremal.  Only
  the two bases with range 46 are extremal bases.}
\label{table:k10}
\end{center}
\end{table}

All extremal bases of lengths $k\le 24$ are currently known
\cite{kohonen2014}.  Interestingly, all of them are either {\em both}
symmetric and restricted, or {\em neither}.  Three questions arise
naturally:
\begin{enumerate}
\item If an extremal basis is symmetric, is it necessarily restricted?
\item If an extremal basis is restricted, is it necessarily symmetric?
\item Does every $k \ge 15$ have an extremal basis that is symmetric?
\end{enumerate}

The first question is answered affirmatively by a theorem of Rohrbach
\cite{rohrbach1937}.  The second question was posed by Riddell and
Chan \cite[p.~631]{riddell1978}, but to our knowledge has not been
answered in general; with $k\le 24$ the answer is yes.

The third question has appeared in a stronger form: it was suggested
that all extremal bases with $k \ge 15$ might be symmetric
\cite{challis1993}.  This was later disproven by Challis and Robinson,
since $k=21$ has four extremal bases: two symmetric, two asymmetric
\cite{challis2010}.  The question remains whether every $k \ge 15$ has
at least one extremal basis that is symmetric.

In this work we describe an efficient algorithm for finding all
extremal restricted bases of a given length $k$.  The algorithm is
based on the idea that a restricted basis can be constructed by
concatenating two shorter admissible bases, one of them as a mirror
image.  With this method we have computed all extremal restricted
bases of lengths $k \le 41$.

Note that we have included $a_0=0$ in a basis, similarly to Wagstaff
\cite{wagstaff1979}.  If $0$ is excluded, the equivalent condition is
that every integer in $[0,n]$ is the sum of {\em at most} two elements
of the basis \cite[p.~3.1]{selmer1986}.  Excluding the zero is perhaps
more usual in current literature, but including it is more convenient
for our purposes.  The zero element is not counted in the length of
a basis.


\section{Related work}
Our search algorithm builds on a combination of existing ideas.
Rohrbach discusses symmetric bases, and the proof of his Satz 1 is
based on the observation that if a basis is mirrored from $a_k$, then
its pairwise sums are mirrored from $2a_k$ \cite{rohrbach1937}.  We
shall exploit a generalization of this for asymmetric restricted
bases.

Riddell and Chan discuss the connection between symmetric and
restricted bases \cite{riddell1978}.  Mossige notes that symmetric
bases $A_k$ can be efficiently searched by scanning through admissible
bases of length $A_{\lceil k/2 \rceil}$ \cite{mossige1981}.  For
symmetric bases this is sufficient; the second half of a symmetric
basis is a mirror image of the first half, and then Rohrbach's theorem
ensures that the constructed set $A_k$ is a basis for $2a_k$.  For
asymmetric restricted bases, a similar search can be conducted
separately for the two halves of the basis (prefix and suffix).
However, since Rohrbach's theorem does not apply to asymmetric bases,
the construction does not automatically yield a basis for $2a_k$.
This must be checked separately.

The final ingredient is the ``gaps test'' by Challis
\cite{challis1993}.  Based on a simple combinatorial argument, it
prunes the search tree of admissible bases, if they are required to
have a range of at least a given target value $T$.  In
section~\ref{section:prefix} we shall prove lower bounds for the
ranges of the prefix and the mirrored suffix.  With these lower bounds
the gaps test prunes the search tree very efficiently.


\section{Definitions and initial results}
If $A$ and $B$ are sets of integers, we define
\begin{equation*}
  A+B := \{a+b : a \in A, b \in B\},
\end{equation*}
and if $b$ is an integer, we define the {\it mirror image} of $A$ with respect to $b$ as
\begin{equation*}
  b-A := \{b-a : a \in A\}.
\end{equation*}
The set of integers {\it generated by} $A$ is
\begin{equation*}
  2A := A+A = \{a+a' : a,a' \in A\}.
\end{equation*}
It is straightforward to verify that
\begin{equation*}
  2(b-A) = 2b - 2A.
\end{equation*}
By $[c,d]$ we denote the consecutive integers $\{c, c+1, \ldots, d\}$.
Now the condition that $A$ is a basis for $n$ is succintly stated as
follows:
\begin{equation*}
  2A \supseteq [0,n].
\end{equation*}
If $A_k = \{a_0 &lt; \cdots &lt; a_k\}$ is a basis and $i&lt;k$, then $A_i =
\{a_0, \ldots, a_i\}$ is a {\it partial basis}.  We state without
proof three easy observations (see \cite{challis1993} and
\cite{selmer1986}):

\begin{lemma}
  If a basis is restricted, then it is admissible.
  \label{lemma:restadm}
\end{lemma}

\begin{lemma}
  If a basis is extremal, then it is admissible.
  \label{lemma:extadm}
\end{lemma}

\begin{lemma}
  If a basis $A_k$ is admissible, then for all $i&lt;k$ the partial basis
  $A_i$ is admissible, and $a_{i+1} \le n_2(A_i)+1$.
  \label{lemma:partial}
\end{lemma}

The first question posed in the introduction is now answered by the
following theorem, essentially the same as Rohrbach's Satz 1
\cite[p.~4]{rohrbach1937}.

\begin{theorem}
  If $A_k$ is an extremal basis and it is symmetric, then it is
  restricted.
  \label{theorem:symmrest}
\end{theorem}
\begin{proof}
  Let $a_k = \max\{A_k\}$.  By Lemma~\ref{lemma:extadm}, $A_k$ is
  admissible; thus $2A_k \supseteq [0,a_k]$.  By symmetry $A_k =
  a_k-A_k$, thus
  \begin{equation*}
    2A_k = 2(a_k-A_k) = 2a_k - 2A_k \supseteq [a_k, 2a_k].
  \end{equation*}
  Combining the above observations we have $2A_k \supseteq [0,2a_k]$,
  thus $A_k$ is restricted.
\end{proof}

Note that if $A_k$ is a restricted basis with range $n$, then its
largest element is exactly $a_k=n/2$.  Exploiting the idea of
mirroring from the largest element we obtain the following theorem.

\begin{theorem}
  If $A_k$ is a restricted basis with range $n$, then $a_k-A_k$ is
  also a restricted basis for $n$.
  \label{theorem:mirror}
\end{theorem}
\begin{proof}
  Since $A_k$ is a basis for $n$, it follows that $2A_k \supseteq
  [0,n]$.  Now
  \begin{equation*}
    2(a_k-A_k) = 2a_k - 2A_k = n - 2A_k \supseteq [0,n],
  \end{equation*}
  thus $a_k-A_k$ is a basis for $n$.  Its largest element is $a_k-0 =
  a_k = n/2$, thus it is restricted.
\end{proof}

Theorem~\ref{theorem:mirror} implies that asymmetric restricted bases
always form pairs that are mirror images of each other.  Two such
pairs are seen in Table~\ref{table:k10}.

\section{Prefix and suffix of a restricted basis}
\label{section:prefix}

Let $A_k$ be a restricted basis with range $n$ and length $k \ge 3$.
Then by Theorem~\ref{theorem:mirror} the mirror image $B_k = a_k-A_k$
is also a restricted basis with range $n$.  Choose now an arbitrary
{\it pivot index} $i$ such that $0&lt;i&lt;k-1$.  Split $A_k$ into a {\it
  prefix} $A_i = \{a_0 &lt; \cdots &lt; a_i\}$ and a {\it suffix} $R =
\{a_{i+1} &lt; \cdots &lt; a_k\}$.  The prefix is a partial basis of $A_k$.
The suffix can be mirrored from $a_k$ to obtain another basis
\begin{equation*}
B_j = a_k - R = \{b_0 &lt; \cdots &lt; b_j\},
\end{equation*}
where $j=k-1-i$, and $b_h = a_k - a_{k-h}$ for all $0\le h \le j$.
Now $B_j$ is a partial basis of $B_k$.

By Lemma~\ref{lemma:restadm} both $A_k$ and $B_k$ are admissible, and
then by Lemma~\ref{lemma:partial}
\begin{align*}
  n_2(A_i) &amp;\ge a_{i+1}-1,\\
  n_2(B_j) &amp;\ge b_{j+1}-1.
\end{align*}
We have now lower bounds for the ranges $n_2(A_i)$ and $n_2(B_j)$, but the
bounds depend on $a_{i+1}$ and $b_{j+1}$.  However, these values can
further be bounded from below:
\begin{align*}
  a_{i+1} &amp;= a_k - b_j \ge a_k - (n_2(B_{j-1})+1) \ge a_k - n_2(j-1) - 1, \\
  b_{j+1} &amp;= a_k - a_i \ge a_k - (n_2(A_{i-1})+1) \ge a_k - n_2(i-1) - 1,
\end{align*}
where $n_2(i-1)$ and $n_2(j-1)$ are the maximum ranges of bases of lengths
$i-1$ and $j-1$, respectively.  These maximum ranges are currently
known up to length $24$.

Combining these bounds we can state a necessary condition for
$A_k$ being a restricted basis with range $n$.

\begin{theorem}
  If $A_k$ is a restricted basis with range $n$, and $i$ is
  an index such that $0&lt;i&lt;k-1$, and $i+j=k-1$, then:
  \begin{enumerate}
  \item The prefix $A_i$ is an admissible basis such that
    $n_2(A_i) \ge a_k - n_2(j-1) - 2$.
  \item The mirrored suffix $B_j = a_k-\{a_{i+1},\ldots,a_k\}$ is an
    admissible basis such that $n_2(B_j) \ge a_k - n_2(i-1) - 2$.
  \end{enumerate}
  \label{theorem:main}
\end{theorem}

\begin{example}
Let $k=10$ and $n=44$, and choose $i=5$ (thus $j=4$).  If $A_{10}$ is
a restricted basis for $44$, then $a_{10}=22$.

Since $n_2(3)=8$, $b_4$ cannot be greater than $8+1=9$; in other words,
$a_6 = 22-b_4$ cannot be smaller than $22-9 = 13$; thus $n_2(A_5) \ge
12$.

Similarly, since $n_2(4)=12$, $a_5$ cannot be greater than $12+1=13$; in
other words, $b_5 = 22-a_5$ cannot be smaller than $22-13=9$; thus
$n_2(B_4) \ge 8$.

The lower bounds are the ones given by Theorem~\ref{theorem:main}.
Consider now a restricted basis $A_{10}$ and its mirror image
$B_{10}$, shown in right-to-left order:
\begin{equation*}
  \begin{array}{lrrrrrrrrrrrl}
    &amp; \multicolumn{6}{c}{A_5}   &amp; \multicolumn{5}{c}{R} \\
    &amp; \multispan6\mathstrut\downbracefill &amp; \multispan5\mathstrut\downbracefill \\
    A_{10} = &amp; 0&amp;  1&amp; 3&amp; 4&amp; 6&amp;11&amp;13&amp;18&amp;19&amp;21&amp;22 \\
            &amp;22&amp;21&amp;19&amp;18&amp;16&amp;11&amp; 9&amp; 6&amp; 3&amp; 1&amp; 0  &amp; = B_{10}\\
    \multispan7               &amp; \multispan5\mathstrut\upbracefill \\
    \multispan7               &amp; \multicolumn{5}{c}{B_4} \\
  \end{array}
\end{equation*}
The prefix $A_5$ has range $12$, and the mirrored suffix $B_4$ has
range $10$.  Both ranges are within the bounds required by
Theorem~\ref{theorem:main}.
\end{example}

The second part of Theorem~\ref{theorem:main} also provides an upper
bound for the range of a restricted basis:
\begin{align*}
  n_2(A_k) = 2a_k &amp;\le 2n_2(B_j) + 2n_2(i-1) + 4 \\
                &amp;\le 2n_2(j) + 2n_2(i-1) + 4.
\end{align*}
Choosing $i = \lfloor k/2 \rfloor$ this yields the following bounds,
for even and odd values of~$k$.
\begin{corollary}
If $r&gt;1$ is an integer, then
\begin{align*}
  n_2^*(2r)   &amp;\le 4n_2(r-1) + 4,   \\
  n_2^*(2r+1) &amp;\le 2n_2(r-1) + 2n_2(r) + 4.
\end{align*}
\label{cor:upper}
\end{corollary}


\section{Search algorithm}
Suppose that $k$ and $n$ are given, and the task is to enumerate every
restricted basis of length $k$ and range $n$ (if any such bases
exist).  Choose a pivot index $i$, for example $i = \lfloor k/2
\rfloor$.

A straightforward method would be to enumerate all admissible prefix
bases $A_i$, all admissible mirrored suffix bases $B_j$, and for each
pair $(A_i, B_j)$ check whether $A_i \cup (n/2 - B_j)$ happens to be a
basis for $n$, that is, whether it generates all integers in $[0,n]$.
For large $k$ this is not feasible, as the number of admissible bases
of length $i$ increases rapidly (see \seqnum{A167809} in \cite{oeis}).

However, Theorem~\ref{theorem:main} gives definite lower bounds for
the ranges of the prefix $A_i$ and the mirrored suffix $B_j$.  Thus
only a tiny fraction of all admissible prefixes and mirrored suffixes
need to be considered, as seen in the following example.

\begin{example}
Let $k=25$ and $n=228$.  We want to know whether there are any
restricted bases with these values, and to list them if there are.
Choose $i=12$ (thus $j=12$).  The last element of a restricted basis
must be $a_k = n/2 = 114$.  There are $15\;752\;080$ admissible bases
of length 12, but we only need to consider the prefixes $A_i$ such
that $n_2(A_i) \ge 114-n_2(11)-2 = 58$; there are only $187$ such
prefixes.
\end{example}

Admissible bases with a given length and a given minimum range can be
enumerated with the algorithm (``K-program'') described by Challis
\cite{challis1993}.  Combining these ingredients we obtain
Algorithm~\ref{alg:mim}, which enumerates all restricted bases of
given length $k$ and range $n$.

\begin{algorithm}
\caption{List restricted bases of length $k$ and range $n$}
\begin{algorithmic}[1]
\REQUIRE $k \ge 3$
\STATE $i \leftarrow \lfloor k/2 \rfloor$ \COMMENT{Choose pivot index}
\STATE $j \leftarrow k-i-1$
\STATE $n_a \leftarrow n_2(i-1)$ \COMMENT{Lookup from \seqnum{A001212}}
\STATE $n_b \leftarrow n_2(j-1)$ \COMMENT{Lookup from \seqnum{A001212}}
\STATE ${\cal A} \leftarrow \{A_i : n_2(A_i) \ge n/2 - n_b - 2 \}$   \COMMENT{List prefixes with Challis algorithm \cite{challis1993}}
\STATE ${\cal B} \leftarrow \{B_j : n_2(B_j) \ge n/2 - n_a - 2 \}$  \COMMENT{List mirrored suffixes with Challis algorithm}
\FORALL{$A_i \in {\cal A}$}
  \FORALL{$B_j \in {\cal B}$}
     \STATE $R \leftarrow n/2 - B_j$ \COMMENT{Mirror from $n/2$}
     \STATE $A_k \leftarrow A_i \cup R$ \COMMENT{Concatenate}
     \IF[Generate pairwise sums and check range]{$2A_k \supseteq [0,n]$}
       \PRINT{$A_k$}
     \ENDIF
  \ENDFOR
\ENDFOR
\end{algorithmic}
\label{alg:mim}
\end{algorithm}

If $n_2^*(k)$ is not known, Algorithm~\ref{alg:mim} can be run with
different values of $n$, starting from the upper bound for $n_2^*(k)$
provided by Corollary~\ref{cor:upper}.  If no solutions are found, $n$
is then decreased in steps of $2$, until for some $n$ there are
solutions.  Only even values of $n$ need to be considered, since the
range of a restricted basis is always even.

\begin{example}
  Let $k=25$.  By Corollary~\ref{cor:upper}, $n_2^*(25) \le 240$.  For
  $n=240$ the search algorithm finds no solutions.  Then $n$ is
  reduced in steps of $2$, until for $n=228$ the algorithm returns one
  solution:
  \begin{align*}
    A_{25} = \{&amp;0,1,3,4,6,10,13,15,21,29,37,45,53,\\
              &amp;61,69,77,85,93,99,101,104,108,110,111,113,114 \}
  \end{align*}
  By construction, this is an extremal restricted basis,
  so now we know that $n_2^*(25) = 228$.
\end{example}


\section{Results}
Using the search algorithm described in the previous section, we
performed an exhaustive search for extremal restricted bases of
lengths $k=25,\ldots,41$.  The bases are listed in
Table~\ref{table:newrestricted}.  For ease of reference, previously
known extremal restricted bases of lengths $k=1,\ldots,24$ are listed
in Table~\ref{table:oldrestricted}.

\begin{sidewaystable}[p]
\begin{center}
\small
\setlength{\tabcolsep}{4pt}
\begin{tabular}{lll|rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr}
$k$ &amp; $n_2^*(k)$ &amp; &amp; \multicolumn{5}{l}{basis} \\
\hline
  1 &amp;   2 &amp; S&amp;   0&amp;   1\\
\hline
  2 &amp;   4 &amp; S&amp;   0&amp;   1&amp;   2\\
\hline
  3 &amp;   8 &amp; S&amp;   0&amp;   1&amp;   3&amp;   4\\
\hline
  4 &amp;  12 &amp; S&amp;   0&amp;   1&amp;   3&amp;   5&amp;   6\\
\hline
  5 &amp;  16 &amp; S&amp;   0&amp;   1&amp;   3&amp;   5&amp;   7&amp;   8\\
\hline
  6 &amp;  20 &amp; S&amp;   0&amp;   1&amp;   2&amp;   5&amp;   8&amp;   9&amp;  10\\
  6 &amp;  20 &amp; S&amp;   0&amp;   1&amp;   3&amp;   5&amp;   7&amp;   9&amp;  10\\
\hline
  7 &amp;  26 &amp; S&amp;   0&amp;   1&amp;   2&amp;   5&amp;   8&amp;  11&amp;  12&amp;  13\\
  7 &amp;  26 &amp; S&amp;   0&amp;   1&amp;   3&amp;   4&amp;   9&amp;  10&amp;  12&amp;  13\\
\hline
  8 &amp;  32 &amp; S&amp;   0&amp;   1&amp;   2&amp;   5&amp;   8&amp;  11&amp;  14&amp;  15&amp;  16\\
\hline
  9 &amp;  40 &amp; S&amp;   0&amp;   1&amp;   3&amp;   4&amp;   9&amp;  11&amp;  16&amp;  17&amp;  19&amp;  20\\
\hline
 10 &amp;  44 &amp;  &amp;   \multicolumn{8}{l}{see Table~\ref{table:k10}} \\
\hline
 11 &amp;  54 &amp; S&amp;   0&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; S&amp;   0&amp;   1&amp;   3&amp;   5&amp;   6&amp;  13&amp;  14&amp;  21&amp;  22&amp;  24&amp;  26&amp;  27\\
\hline
 12 &amp;  64 &amp; S&amp;   0&amp;   1&amp;   3&amp;   4&amp;   9&amp;  11&amp;  16&amp;  21&amp;  23&amp;  28&amp;  29&amp;  31&amp;  32\\
\hline
 13 &amp;  72 &amp; S&amp;   0&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\\
\hline
 14 &amp;  80 &amp; S&amp;   0&amp;   1&amp;   3&amp;   4&amp;   5&amp;   8&amp; $\cdots$ &amp;  +6 &amp; $\cdots$&amp;  32&amp;  35&amp;  36&amp;  37&amp;  39&amp;  40\\
\hline
 15 &amp;  92 &amp; S&amp;   0&amp;   1&amp;   3&amp;   4&amp;   5&amp;   8&amp; $\cdots$ &amp;  +6 &amp; $\cdots$&amp;  38&amp;  41&amp;  42&amp;  43&amp;  45&amp;  46\\
\hline
 16 &amp; 104 &amp; S&amp;   0&amp;   1&amp;   3&amp;   4&amp;   5&amp;   8&amp; $\cdots$ &amp;  +6 &amp; $\cdots$&amp;  44&amp;  47&amp;  48&amp;  49&amp;  51&amp;  52\\
\hline
 17 &amp; 116 &amp; S&amp;   0&amp;   1&amp;   3&amp;   4&amp;   5&amp;   8&amp; $\cdots$ &amp;  +6 &amp; $\cdots$&amp;  50&amp;  53&amp;  54&amp;  55&amp;  57&amp;  58\\
\hline
 18 &amp; 128 &amp; S&amp;   0&amp;   1&amp;   3&amp;   4&amp;   5&amp;   8&amp; $\cdots$ &amp;  +6 &amp; $\cdots$&amp;  56&amp;  59&amp;  60&amp;  61&amp;  63&amp;  64\\
\hline
 19 &amp; 140 &amp; S&amp;   0&amp;   1&amp;   3&amp;   4&amp;   5&amp;   8&amp; $\cdots$ &amp;  +6 &amp; $\cdots$&amp;  62&amp;  65&amp;  66&amp;  67&amp;  69&amp;  70\\
\hline
 20 &amp; 152 &amp; S&amp;   0&amp;   1&amp;   3&amp;   4&amp;   5&amp;   8&amp; $\cdots$ &amp;  +6 &amp; $\cdots$&amp;  68&amp;  71&amp;  72&amp;  73&amp;  75&amp;  76\\
\hline
 21 &amp; 164 &amp; S&amp;   0&amp;   1&amp;   3&amp;   4&amp;   5&amp;   8&amp; $\cdots$ &amp;  +6 &amp; $\cdots$&amp;  74&amp;  77&amp;  78&amp;  79&amp;  81&amp;  82\\
 21 &amp; 164 &amp; S&amp;   0&amp;   1&amp;   3&amp;   4&amp;   6&amp;  10&amp;  13&amp;  15&amp;  21&amp; $\cdots$ &amp;  +8 &amp; $\cdots$&amp;  61&amp;  67&amp;  69&amp;  72&amp;  76&amp;  78&amp;  79&amp;  81&amp;  82\\
\hline
 22 &amp; 180 &amp; S&amp;   0&amp;   1&amp;   3&amp;   4&amp;   6&amp;  10&amp;  13&amp;  15&amp;  21&amp; $\cdots$ &amp;  +8 &amp; $\cdots$&amp;  69&amp;  75&amp;  77&amp;  80&amp;  84&amp;  86&amp;  87&amp;  89&amp;  90\\
\hline
 23 &amp; 196 &amp; S&amp;   0&amp;   1&amp;   3&amp;   4&amp;   6&amp;  10&amp;  13&amp;  15&amp;  21&amp; $\cdots$ &amp;  +8 &amp; $\cdots$&amp;  77&amp;  83&amp;  85&amp;  88&amp;  92&amp;  94&amp;  95&amp;  97&amp;  98\\
\hline
 24 &amp; 212 &amp; S&amp;   0&amp;   1&amp;   3&amp;   4&amp;   6&amp;  10&amp;  13&amp;  15&amp;  21&amp; $\cdots$ &amp;  +8 &amp; $\cdots$&amp;  85&amp;  91&amp;  93&amp;  96&amp; 100&amp; 102&amp; 103&amp; 105&amp; 106\\
\end{tabular}
\caption{Extremal restricted bases of lengths $k=1,\ldots,24$.  S =
  symmetric, A = asymmetric.  $+c$ indicates several elements with a
  repeated difference of $c$.}
\label{table:oldrestricted}
\end{center}
\end{sidewaystable}


\begin{sidewaystable}[p]
\begin{center}
\small
\setlength{\tabcolsep}{2pt}
\begin{tabular}{lll|rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr}
$k$ &amp; $n_2^*(k)$ &amp; &amp; \multicolumn{5}{l}{basis} \\
\hline
 25 &amp; 228 &amp; S&amp;   0&amp;   1&amp;   3&amp;   4&amp;   6&amp;  10&amp;  13&amp;  15&amp;  21&amp; $\cdots$ &amp; +8 &amp; $\cdots$&amp;  93&amp;  99&amp; 101&amp; 104&amp; 108&amp; 110&amp; 111&amp; 113&amp; 114\\
\hline
 26 &amp; 244 &amp; S&amp;   0&amp;   1&amp;   3&amp;   4&amp;   6&amp;  10&amp;  13&amp;  15&amp;  21&amp; $\cdots$ &amp; +8 &amp; $\cdots$&amp; 101&amp; 107&amp; 109&amp; 112&amp; 116&amp; 118&amp; 119&amp; 121&amp; 122\\
 26 &amp; 244 &amp; S&amp;   0&amp;   1&amp;   3&amp;   4&amp;   5&amp;   8&amp;  11&amp;  15&amp;  16&amp; $\cdots$ &amp; +9 &amp; $\cdots$&amp; 106&amp; 107&amp; 111&amp; 114&amp; 117&amp; 118&amp; 119&amp; 121&amp; 122\\
\hline
 27 &amp; 262 &amp; S&amp;   0&amp;   1&amp;   3&amp;   4&amp;   5&amp;   8&amp;  11&amp;  15&amp;  16&amp; $\cdots$ &amp; +9 &amp; $\cdots$&amp; 115&amp; 116&amp; 120&amp; 123&amp; 126&amp; 127&amp; 128&amp; 130&amp; 131\\
\hline
 28 &amp; 280 &amp; S&amp;   0&amp;   1&amp;   3&amp;   4&amp;   5&amp;   8&amp;  11&amp;  15&amp;  16&amp; $\cdots$ &amp; +9 &amp; $\cdots$&amp; 124&amp; 125&amp; 129&amp; 132&amp; 135&amp; 136&amp; 137&amp; 139&amp; 140\\
\hline
 29 &amp; 298 &amp; S&amp;   0&amp;   1&amp;   3&amp;   4&amp;   5&amp;   8&amp;  11&amp;  15&amp;  16&amp; $\cdots$ &amp; +9 &amp; $\cdots$&amp; 133&amp; 134&amp; 138&amp; 141&amp; 144&amp; 145&amp; 146&amp; 148&amp; 149\\
\hline
 30 &amp; 316 &amp; S&amp;   0&amp;   1&amp;   3&amp;   4&amp;   5&amp;   8&amp;  11&amp;  15&amp;  16&amp;  25&amp;  34&amp; $\cdots$ &amp;  +9 &amp; $\cdots$&amp; 124&amp; 133&amp; 142&amp; 143&amp; 147&amp; 150&amp; 153&amp; 154&amp; 155&amp; 157&amp; 158\\
 30 &amp; 316 &amp; S&amp;   0&amp;   1&amp;   2&amp;   5&amp;   6&amp;   8&amp;  13&amp;  14&amp;  17&amp;  19&amp;  29&amp; $\cdots$ &amp; +10 &amp; $\cdots$&amp; 129&amp; 139&amp; 141&amp; 144&amp; 145&amp; 150&amp; 152&amp; 153&amp; 156&amp; 157&amp; 158\\
 30 &amp; 316 &amp; A&amp;   0&amp;   1&amp;   2&amp;   5&amp;   6&amp;   8&amp;  13&amp;  14&amp;  17&amp;  19&amp;  29&amp; $\cdots$ &amp; +10 &amp; $\cdots$&amp; 129&amp; 133&amp; 139&amp; 141&amp; 146&amp; 150&amp; 152&amp; 154&amp; 155&amp; 157&amp; 158\\
 30 &amp; 316 &amp; A&amp;   0&amp;   1&amp;   3&amp;   4&amp;   6&amp;   8&amp;  12&amp;  17&amp;  19&amp;  25&amp;  29&amp; $\cdots$ &amp; +10 &amp; $\cdots$&amp; 129&amp; 139&amp; 141&amp; 144&amp; 145&amp; 150&amp; 152&amp; 153&amp; 156&amp; 157&amp; 158\\
 30 &amp; 316 &amp; S&amp;   0&amp;   1&amp;   3&amp;   4&amp;   6&amp;   8&amp;  12&amp;  17&amp;  19&amp;  25&amp;  29&amp; $\cdots$ &amp; +10 &amp; $\cdots$&amp; 129&amp; 133&amp; 139&amp; 141&amp; 146&amp; 150&amp; 152&amp; 154&amp; 155&amp; 157&amp; 158\\
 30 &amp; 316 &amp; S&amp;   0&amp;   1&amp;   3&amp;   4&amp;   7&amp;   8&amp;   9&amp;  16&amp;  17&amp;  21&amp;  24&amp; $\cdots$ &amp; +11 &amp; $\cdots$&amp; 134&amp; 137&amp; 141&amp; 142&amp; 149&amp; 150&amp; 151&amp; 154&amp; 155&amp; 157&amp; 158\\
\hline
 31 &amp; 338 &amp; S&amp;   0&amp;   1&amp;   3&amp;   4&amp;   7&amp;   8&amp;   9&amp;  16&amp;  17&amp;  21&amp;  24&amp; $\cdots$ &amp; +11 &amp; $\cdots$&amp; 145&amp; 148&amp; 152&amp; 153&amp; 160&amp; 161&amp; 162&amp; 165&amp; 166&amp; 168&amp; 169\\
\hline
 32 &amp; 360 &amp; S&amp;   0&amp;   1&amp;   3&amp;   4&amp;   7&amp;   8&amp;   9&amp;  16&amp;  17&amp;  21&amp;  24&amp; $\cdots$ &amp; +11 &amp; $\cdots$&amp; 156&amp; 159&amp; 163&amp; 164&amp; 171&amp; 172&amp; 173&amp; 176&amp; 177&amp; 179&amp; 180\\
\hline
 33 &amp; 382 &amp; S&amp;   0&amp;   1&amp;   3&amp;   4&amp;   7&amp;   8&amp;   9&amp;  16&amp;  17&amp;  21&amp;  24&amp; $\cdots$ &amp; +11 &amp; $\cdots$&amp; 167&amp; 170&amp; 174&amp; 175&amp; 182&amp; 183&amp; 184&amp; 187&amp; 188&amp; 190&amp; 191\\
\hline
 34 &amp; 404 &amp; S&amp;   0&amp;   1&amp;   3&amp;   4&amp;   7&amp;   8&amp;   9&amp;  16&amp;  17&amp;  21&amp;  24&amp; $\cdots$ &amp; +11 &amp; $\cdots$&amp; 178&amp; 181&amp; 185&amp; 186&amp; 193&amp; 194&amp; 195&amp; 198&amp; 199&amp; 201&amp; 202\\
\hline
 35 &amp; 426 &amp; S&amp;   0&amp;   1&amp;   3&amp;   4&amp;   7&amp;   8&amp;   9&amp;  16&amp;  17&amp;  21&amp;  24&amp; $\cdots$ &amp; +11 &amp; $\cdots$&amp; 189&amp; 192&amp; 196&amp; 197&amp; 204&amp; 205&amp; 206&amp; 209&amp; 210&amp; 212&amp; 213\\
\hline
 36 &amp; 448 &amp; S&amp;   0&amp;   1&amp;   3&amp;   4&amp;   7&amp;   8&amp;   9&amp;  16&amp;  17&amp;  21&amp;  24&amp; $\cdots$ &amp; +11 &amp; $\cdots$&amp; 200&amp; 203&amp; 207&amp; 208&amp; 215&amp; 216&amp; 217&amp; 220&amp; 221&amp; 223&amp; 224\\
\hline
 37 &amp; 470 &amp; S&amp;   0&amp;   1&amp;   3&amp;   4&amp;   7&amp;   8&amp;   9&amp;  16&amp;  17&amp;  21&amp;  24&amp; $\cdots$ &amp; +11 &amp; $\cdots$&amp; 211&amp; 214&amp; 218&amp; 219&amp; 226&amp; 227&amp; 228&amp; 231&amp; 232&amp; 234&amp; 235\\
\hline
 38 &amp; 492 &amp; S&amp;   0&amp;   1&amp;   3&amp;   4&amp;   7&amp;   8&amp;   9&amp;  16&amp;  17&amp;  21&amp;  24&amp; $\cdots$ &amp; +11 &amp; $\cdots$&amp; 222&amp; 225&amp; 229&amp; 230&amp; 237&amp; 238&amp; 239&amp; 242&amp; 243&amp; 245&amp; 246\\
\hline
 39 &amp; 514 &amp; S&amp;   0&amp;   1&amp;   3&amp;   4&amp;   7&amp;   8&amp;   9&amp;  16&amp;  17&amp;  21&amp;  24&amp; $\cdots$ &amp; +11 &amp; $\cdots$&amp; 233&amp; 236&amp; 240&amp; 241&amp; 248&amp; 249&amp; 250&amp; 253&amp; 254&amp; 256&amp; 257\\
\hline
 40 &amp; 536 &amp; S&amp;   0&amp;   1&amp;   3&amp;   4&amp;   7&amp;   8&amp;   9&amp;  16&amp;  17&amp;  21&amp;  24&amp;  35&amp;  46&amp; $\cdots$ &amp; +11 &amp; $\cdots$&amp; 222&amp; 233&amp; 244&amp; 247&amp; 251&amp; 252&amp; 259&amp; 260&amp; 261&amp; 264&amp; 265&amp; 267&amp; 268\\
 40 &amp; 536 &amp; S&amp;   0&amp;   1&amp;   2&amp;   5&amp;   7&amp;  10&amp;  11&amp;  19&amp;  21&amp;  22&amp;  25&amp;  29&amp;  30&amp; $\cdots$ &amp; +13 &amp; $\cdots$&amp; 238&amp; 239&amp; 243&amp; 246&amp; 247&amp; 249&amp; 257&amp; 258&amp; 261&amp; 263&amp; 266&amp; 267&amp; 268\\
\hline
 41 &amp; 562 &amp; S&amp;   0&amp;   1&amp;   2&amp;   5&amp;   7&amp;  10&amp;  11&amp;  19&amp;  21&amp;  22&amp;  25&amp;  29&amp;  30&amp; $\cdots$ &amp; +13 &amp; $\cdots$&amp; 251&amp; 252&amp; 256&amp; 259&amp; 260&amp; 262&amp; 270&amp; 271&amp; 274&amp; 276&amp; 279&amp; 280&amp; 281\\
\end{tabular}
\caption{Extremal restricted bases of lengths $k=25,\ldots,41$.  S =
  symmetric, A = asymmetric.  $+c$ indicates several elements with a
  repeated difference of $c$.}
\label{table:newrestricted}
\end{center}
\end{sidewaystable}

For lengths $25,\ldots,29$ the extremal restricted bases are the
extremal symmetric bases listed by Mossige \cite{mossige1981}.  For
lengths $31,\ldots,41$ they equal the bases given by Challis and
Robinson's construction \cite[p.~6]{challis2010}.  Note that while the
aforementioned construction gives a lower bound for the extremal
restricted range, exhaustive search gives the exact range.

With $k=30$, there are six extremal restricted bases with range $316$.
Four of them are symmetric and were listed by Mossige, but two are
asymmetric.  This is perhaps unexpected, and shows that at least one
of the questions 2 and 3 stated in the introduction must be answered
negatively.  It is currently not known whether $n_2(30)$ is $316$ or
greater.
\begin{itemize}
\item If $n_2(30)=316$, then we have here two extremal bases that are
  restricted, but asymmetric; this would answer question 2 negatively.
\item If $n_2(30)&gt;316$, then there must be some (currently unknown)
  nonrestricted bases with range greater than $316$, but they cannot
  be symmetric (for if they were, they would be restricted by
  Theorem~\ref{theorem:symmrest}).  This would answer question 3
  negatively.
\end{itemize}

As an example of the time requirement, with $k=41$ and $n=562$, the
algorithm generates $5\;514$ prefixes of length $20$ and range at
least $n/2-n_2(19)-2=139$.  These were enumerated in $120$ CPU hours
on parallel 2.6~GHz Intel Xeon processors, with a C++ implementation
of the Challis algorithm.  Since $41$ is odd, we have $j=i$, and the
mirrored suffixes are the same as the prefixes.  The concatenation
phase of the algorithm (lines 7 to 15) took 1.8 seconds with a Matlab
implementation.

\section{Discussion}
Restricted bases are an interesting class of additive bases for two
reasons.  On one hand, searching for the extremal solutions among
restricted bases is enormously faster than searching among all
additive bases, as illustrated in the previous sections.  This
efficiency stems from Theorem~\ref{theorem:mirror}, which places a
very strong constraint on any extremal restricted basis: that its
mirror image must also be a restricted basis (possibly different).
Thus restricted additive bases can be seen as a generalization of
symmetric additive bases.

On the other hand, among lengths $k=1,\ldots,24$, in almost every case
at least one of the extremal bases is restricted (with the sole
exception of $k=10$).  The reason for this is not known, and it is not
known whether this regularity continues for $k&gt;24$.  The case of
$k=30$, discussed in the previous section, suggests that there may be
surprises waiting to be found.

For simplicity, we have always taken $i = \lfloor k/2 \rfloor$ in our
search algorithm.  Further research is needed to find the optimal
pivot index $i$ that minimizes the search work.

While Theorem~\ref{theorem:mirror} as such does not apply to
nonrestricted bases, it would be interesting to know if it could be
generalized in such a way that applies to them.  Such a generalization
might provide an improved search method for extremal additive bases in
the nonrestricted case.


\begin{thebibliography}{99}

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

\bibitem{challis2010} M. F. Challis and J. P. Robinson, Some extremal
  postage stamp bases, {\em J. Integer Sequences} {\bf 13} (2010), Article
  10.2.3.

\bibitem{guy2004} R. Guy, {\em Unsolved Problems in Number Theory},
  2nd edition, Springer-Verlag, 2004.

\bibitem{kohonen2014} J. Kohonen and J. Corander, Addition chains meet
  postage stamps: Reducing the number of multiplications, {\em
    J. Integer Sequences} {\bf 17} (2014), Article 14.3.4.

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

\bibitem{riddell1978} J. Riddell and C. Chan, Some extremal 2-bases,
  {\em Math. Comp.} {\bf 32} (1978), 630--634.

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

\bibitem{selmer1986} E. S. Selmer, The local postage stamp
  problem. Part 1: general theory, Technical report no.~42,
  Department of Pure Mathematics, University of Bergen, 1986.

\bibitem{oeis} N. J. A. Sloane, On-Line Encyclopedia of Integer Sequences,
\url{http://oeis.org}.

\bibitem{wagstaff1979} S. S. Wagstaff, Additive $h$-bases for $n$, in
  M. B. Nathanson, ed., {\em Number Theory Carbondale 1979}, Lect.
  Notes in Math., Vol.~751, Springer, 1979, pp.~302--327.

\end{thebibliography}

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

\noindent \emph{Keywords: } additive basis, restricted basis.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences \seqnum{A001212},
\seqnum{A006638}, and \seqnum{A167809}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received March 17 2014;
revised version received  May 20 2014.
Published in {\it Journal of Integer Sequences}, May 20 2014.

\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>