<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[all]{xy}

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

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

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

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

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

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

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

\begin{document}

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

\begin{center}
\vskip 1cm{\LARGE\bf Characterizing Frobenius Semigroups by \\
\vskip .11in Filtration
}
\vskip 1cm
\large
Inga Johnson, Sean Powers, Colin Starr, Charles Trevelyan and \\
Craig Webster\\
Department of Mathematics\\
Willamette University\\
Salem, OR 97301\\
USA\\
\href{mailto:ijohnson@willamette.edu}{\tt ijohnson@willamette.edu}\\
\href{mailto:cstarr@willamette.edu}{\tt cstarr@willamette.edu}
\end{center}

\vskip .2 in

\begin{abstract}
For a given base $a$,  and for all integers $k$, we consider the sets
$$G_{a}(k)=\{a^{k},a^{k}+a^{k-1},\ldots,a^{k}+a^{k-1}+\dots+a^{1}+a^{0}\},$$
and for each $G_a(k)$  the corresponding ``Frobenius
set''  
$$F_a(k)=\{n \in\mathbb{N} \ |\ n \text{ is not a sum of  elements of }G_{a}(k) \}.$$
The sets $F_a(k)$ are nested and
their union is $\mathbb{N}$.   Given an integer $n$, we find the smallest $k$ such that $n \in F_a(k)$.
\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}}

%% User definitions:
\newcommand{\len}{\mbox{len}}
\newcommand{\bal}[1]{\begin{align*}#1\end{align*}}
\newcommand{\f}[2]{\displaystyle \frac{#1}{#2}}
\newcommand{\bt}{\begin{thm}}
\newcommand{\et}{\end{thm}}
\newcommand{\bp}{\begin{proof}}
\newcommand{\ep}{\end{proof}}
\newcommand{\bprop}{\begin{prop}}
\newcommand{\eprop}{\end{prop}}
\newcommand{\bl}{\begin{lemma}}
\newcommand{\el}{\end{lemma}}
\newcommand{\bc}{\begin{corollary}}
\newcommand{\ec}{\end{corollary}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}


\section{Introduction and statement of result}

The {\bf Frobenius problem} for a given set $A=\{a_1, a_2, \dots,
a_n\}$ of positive relatively prime integers is the problem of finding
the largest integer that cannot be expressed as a sum of (possibly
repeated) elements of $A$.  This largest such number is the {\it
Frobenius number} of the set $A$, denoted by $g(A)$.

Finding the Frobenius number for sets $A$ has been a  widely studied
problem since the early 1900's, when Frobenius was reported to have
posed the question frequently in lectures.  Sylvester \cite{Syl} is
widely credited with showing 
that for relatively prime integers $a$ and $b$,  $g(\{a, b\}) =
ab-(a+b)$, but he actually addressed a slightly different problem.
In 1990, Curtis showed that for an arbitrary
relatively prime set $A$ the Frobenius number cannot be expressed in
terms of a finite set of polynomials \cite{Cu}, although Greenberg and
later Davison found algorithms that are reasonably quick in practice in
the $n=3$ case  \cite{D,G}. In 1996, Ram\'{i}rez-Alfons\'{i}n
proved that the Frobenius problem for sets $A$ of three or more
elements is NP-hard \cite{RA}.  However, R. Kannan has shown that for
every fixed $n$, there is a method that solves the Frobenius problem in
polynomial time (although the degree of the polynomial grows rapidly
with $n$) \cite{Kannan}.

In this paper we study a family of sets $G_a(k)$, defined below, and for each such set we study not
only the Frobenius number but the set of all numbers which are not sums of elements of $G_a(k)$.  More precisely, let the base
$a\in \mathbb{N}$ be fixed.  For each $k \in \mathbb{N}$, we define
$$G_{a}(k)=\{a^{k},a^{k}+a^{k-1}, a^{k}+a^{k-1}+a^{k-2}, \ldots,a^{k}+a^{k-1}+\dots+a^{1}+a^{0}\}.$$
Note that the rightmost (and largest) element listed in the set above is a geometric series equal to $\frac{a^{k+1}-1}{a-1}$, and
henceforth we will write it as such without further comment.  For the sets $G_a(k)$ we study the Frobenius sets
$$F_{a}(k)=\{n
\in\mathbb{N}\ |\ n \text{ is not a sum of the elements of }G_{a}(k) \}.$$


  A straightforward calculation shows that the sets $F_a(k)$ are nested (i.e., $F_a(k-1) \subseteq F_a(k)$), and the union of the
sets $F_a(k)$ over all $k$ is $\mathbb{N}$.  This paper investigates the following question: for arbitrary $n\in
\mathbb{N},$ what is the least integer $k$ such that $n\in F_a(k)$? We denote this least positive integer as
$f_{a}(n):=\text{min}\{k\ |\ n\in F_a(k)\}$
and call it the {\it Frobenius level} of $n$ with respect to the sets $G_a(k)$.


\begin{example}\label{base2}
With $a=2$ and $k \leq 3$, we have
\[
\begin{array}{ccc}
G_2(1) = \{2, 3\}  &amp; \hspace{.5in}   &amp; F_2(1) =\{ 1 \}   \\
G_2(2) = \{ 4, 6, 7 \}  &amp;   &amp; F_2(2) = \{1, 2, 3, 5, 9 \}   \\
G_2(3) = \{8, 12, 14, 15\}  &amp;   &amp; F_2(3) = \{1, 2, 3, 4, 5, 6, 7, 9, 10, \\
&amp;&amp; 11, 13, 17, 19, 25, 33\}
\end{array}
\]
The sets $G_2(k)$, for $k=1, 2, \dots$ form the sequence A023758 of Sloane's Encyclopedia.
\end{example}

We see that $f_2(9)=2$ and $f_2(19)=3$; however, there is not enough information given in Example~\ref{base2} to determine
$f_2(30)$.  I. Johnson and J. L. Merzel \cite{JM} determined the Frobenius level of an integer $n$  with respect to the sets $G_2(k)$ while studying factorizations in the Steenrod algebra at the prime 2.
Their paper serves as motivation for studying these more general sets $G_a(k)$ for arbitrary $a$ and the solution presented in this paper is a generalization of their results.
It is believed that the results presented here will have implications
in the Steenrod algebra for odd primes analogous to those found at the
prime 2 by Johnson and Merzel.  For a discussion of the Steenrod
algebra and its role in the field of algebraic topology,
see \cite{MT,Rav,Steen,Wood}.


Our solution of this Frobenius level problem relies on careful study of base $a$ arithmetic, and the following definitions and
notations are required to state our result.   For a positive integer $n$, let $[n]$ denote a base $a$ expansion of $n$.  This
means if  $w_i \in \{0, 1, \dots, a-1\}$ for all $i$ and
$$n = w_k a^k + w_{k-1} a^{k-1} + \dots + w_2 a^2 + w_1 a^1 + w_0 a^0,$$
then $[n] = w_k w_{k-1}\dots w_1 w_0$.    We note that this expansion is unique up to leading zeros.  For example, in base 3
(ternary) we may view [41] as 1112 or 0001112.  We call an ordered string of digits $b_k b_{k-1} b_{k-2} \dots b_2 b_1b_0$ with
each digit $b_i$ in $\{0, 1, \dots, a-1\}$ a {\it base $a$ string}, and given integers $i, j$ such that $k \geq i+j
\geq i \geq 0$ the base $a$ string $b_{i+j}  \dots b_{i+1} b_i$ is called a {\it substring} of $b_k b_{k-1} b_{k-2} \dots b_2
b_1b_0$. We will use roman characters to denote integers and Greek letters to denote strings and substrings.

For a given base-$a$ string $\beta $, let $\left\vert \beta \right\vert $ denote the integer with expansion $\beta$ in base $a$.
The length of the string $\beta$ will be denoted by $\len(\beta)$.  Of course, the length is only defined for a given base $a$
string.  Expressions such as $\len([n])$ are not well-defined and will not be used.

Let $\beta=b_{i+j}b_{i+j-1}\dots b_{i}$ be a substring of $b_k \dots b_2 b_1b_0$.  Then $\beta$ is a {\it non-increasing
substring} if and only if $ b_{m}\leq b_{m-1}$ for $i&lt;m\leq i+j$.  That is, we will read from right to left to determine whether
a string is increasing, and of course constant strings are non-increasing.  (For our purposes, ``{\it constant string}'' refers
to a string of length at least two in which all digits are equal.)  For an arbitrary base-$a$ string $b_k
\dots b_2 b_1b_0$ we say that a {\it drop} occurs at $b_m$  provided $b_{m+1}&lt;b_{m}$. A non-increasing substring $b_{i+j} \dots
b_{i+1} b_{i}$ of $b_k \dots b_2 b_1b_0$ is said to {\it follow a drop} provided $i\neq 0$ and a drop occurs at $b_{i-1}$. Given
a base $a$ string $\beta= b_k  \dots b_m \dots b_1b_0,$ the digit  $b_m$ is said to {\it contribute} to $\beta$ if $b_m$ is
itself a digit in a non-increasing substring of $\beta$ that follows a drop.  In examples and diagrams we will underline
contributing digits. We remark that a digit $b_m$ contributes to a string $\beta$ if and only if (1) a drop occurs at $b_{m-1}$,
or (2) $b_{m-1}$ contributes and $b_m \leq b_{m-1}$.  Thus whether or not a digit contributes is completely determined by the
behavior of the digit to its immediate right.

\begin{example} Here is an example of a string, $\gamma = 201120100121$, with drops indicated by arrows and contributing digits underlined.
\begin{center}
\xymatrix@1@=1pt@M=6pt{ \gamma: &amp;&amp;2 &amp;\underline{0} &amp;\underline{1}&amp;\underline{1}&amp;&amp;\ar@(ul,dl)[ll]_&lt;{drop \hspace{.3in}}2
&amp;\underline{0} &amp;&amp;\ar@(ul,dl)[ll]_&lt;{drop \hspace{.3in}}1 &amp;\underline{0} &amp;\underline{0} &amp;\underline{1}  &amp;&amp;\ar@(ul,dl)[ll]_&lt;{drop \hspace{.3in}} 2 &amp;1}
\end{center}
\end{example}

Note that we have not indicated drops within contributing substrings since the important characteristic is whether a digit
contributes.

\begin{definition}
For a given base-$a$ string $\beta,$ define $z(\beta)$ to be the number of digits in $\beta$ that contribute to $\beta$.
\end{definition}

For instance, in ternary, $z(\underline{01}2\underline{0}21000)=3$ and $z(1\underline{01}2\underline{11}2)=4$. The contributing
digits have been underlined.

The function $z$ exhibits a ``{\it quasi-linear}'' property in the sense of the following lemma.

\begin{lemma}\label{qlinear}  Let $\beta$ be a  base-$a$ string, $\beta=b_k\cdots b_{j} \cdots b_2 b_1b_0$, where
$b_{j}$ is not a digit in a constant substring that follows a drop.  Then
$$z(\beta)=z(b_k \cdots b_j) + z(b_{j} \cdots b_{1}b_0) .$$
\end{lemma}

\begin{proof} If $j=k$ or $j=0$ the result is clear.   Suppose $k&gt;j&gt;0$.  The assumption on $b_j$ implies that either $b_j$ does not
contribute to $\beta$, or  it does contribute and $b_j \neq b_{j+1}$ and $b_{j}\neq b_{j-1}$.  The result is clear in the case
that $b_j$ does not contribute to $\beta$, so suppose $b_j$ does contribute to $\beta$. Then we have the following two cases:

(i) $b_{j+1} &lt; b_j &lt; b_{j-1}$  \hfill (ii) $b_{j+1}&gt;b_j$ and $b_j &lt; b_{j-1}$. \hfill {}


It suffices to prove that each digit of $\beta$ that contributes to $\beta$ also contributes to the sum $z(b_k \cdots b_j) +
z(b_{j} \cdots b_{0})$ once and only once.  In case (i), $b_j$ contributes to $b_jb_{j-1} \dots b_1b_0$; however, it cannot
contribute to $b_k \cdots b_{j+1} b_j$ as it cannot follow a drop.  Thus the digit $b_j$ contributes once to the sum.  The digits
in the substring $b_jb_{j-1} \dots b_1$ are contributing if and only if they contribute to $\beta$.  Since $b_{j+1}$ contributes
to $\beta$, the digits of the substring $b_k \cdots b_{j+1} $ contribute to  $b_k \cdots b_{j+1} b_j$ if and only if they
contribute to $\beta$. The proof for case (ii) is analogous except that $b_{j+1}$ does not contribute to $\beta$ and does not
contribute to $b_k \cdots b_{j+1} b_j$, but all contributions from the left of $b_{j+1}$ are the same in both strings.
\end{proof}

Given strings $\alpha $ and $\beta $, their concatenation will be denoted by $\alpha \beta $.   Lastly, we define the ``star"
notation.
\begin{definition}
For nonempty strings $\alpha $ and $\beta ,$ we define the relation $*$ by
\begin{equation*}
%\label {star}
\alpha * \beta \Leftrightarrow \left\vert \alpha \right\vert &lt;z(\beta )
\end{equation*}
\end{definition}

\begin{example} Consider the ternary string 1211111201.   If $\alpha=12$ and $\beta=11111201$,
then $z(\beta)=6$ and $\left\vert\alpha\right\vert=5$.  In this case, $12*11111201$ holds; note that len$(\beta)=8=7+1.$  However,
$121*1111201$ does not hold as $16 \not&lt;5$.
\end{example}

The following theorem is one of the main results of this paper.  In Section 3 we give an algorithmic description of this theorem and briefly discuss its complexity.

\begin{theorem}\label{mainthrm}
Let $n\in \mathbb{N}$.  Then the Frobenius level of $n,$ $f_a(n),$ is the smallest $k$ for which we can write $n=|\alpha\beta|$
with $\len(\beta)=k+1$ and $\alpha \ast\beta$.
\end{theorem}

The previous example shows that the Frobenius level of $n=36091= \left\vert 1211111201 \right\vert$ is $f_3(36091)=7.$

Theorem~\ref{mainthrm} reduces to the results of Johnson and Merzel when $a=2$.  In the Johnson and Merzel paper $z(\beta)$ is
defined as the number of non-trailing zeros in $\beta$ and our definition of $z(\beta)$ reduces to the Johnson-Merzel definition
in the case $a=2$.


\section{Proof of Theorem 1}\label{next}

The proof of Theorem~\ref{mainthrm} is organized as follows: Lemma~\ref{coeffs} gives a particularly useful way to represent
integers that are not in $F_a(k)$.  Lemmas~\ref{recursive1} and~\ref{recursive2} show that the sets $F_a(k)$ can be described
recursively. Lemmas~\ref{subtraction1} and~\ref{subtraction2} set up  technical details to assist in the proof of
Theorem~\ref{starthrm} by induction.  Theorem~\ref{mainthrm} is then a corollary of Theorem~\ref{starthrm}.  Along the way,
Theorem~\ref{frob} gives an explicit formula for the Frobenius number of $G_a(k)$ which corresponds to the well-known results of Nijenhuis and Wilf \cite{NW}.

\begin{lemma}\label{coeffs}
\label{lem1} If $n\not\in F_a(k)$, then there exist
$c_{1}\in\mathbb{Z}_{\geq 0}$, $c_{2},\ldots,c_{k+1}\in \{0,\ldots, a-1\}$ such that $n=c_{1}a^{k}+c_{2}(a^{k}+a^{k-1})+\dots
+c_{k+1} (a^k+a^{k-1}+\dots+a+1).$
\end{lemma}

\begin{proof}  Suppose $n \not\in F_a(k)$.  Then there exist coefficients $w_i$, $1\leq i \leq k+1$, such that
$$n = w_1 a^k +w_2 (a^k + a^{k-1}) + \dots +w_{k+1} (a^k +a^{k-1}+\dots +a^1+a^0).$$
If the coefficients $w_i$ satisfy the conditions of the lemma then we are done; otherwise, let $j$ be the largest subscript for
which $w_j \geq a$.  Using the division algorithm, write $w_j = a q +c_j,$ where $0 \leq c_j &lt; a.$ Substitution gives

\begin{eqnarray*}
w_j (a^k +a^{k-1} + \dots + a^{k-j+1}) &amp; = &amp; (aq+c_j)(a^k +a^{k-1} + \dots + a^{k-j+1}) \\
&amp;=&amp; aq(a^k +a^{k-1} + \dots + a^{k-j+1})\\
&amp; &amp; +c_j(a^k + \dots + a^{k-j+1}) \\
&amp;=&amp;aq(a^k) +q(a^k + a^{k-1}+\dots +a^{k-j+2})\\
&amp; &amp;+c_j(a^k + \dots + a^{k-j+1}).
\end{eqnarray*}
Next, define $c_m:=w_m$ for all $j &lt; m \leq k+1$.  Thus $n$ can be written as
\begin{eqnarray*}
n &amp; = &amp; (w_1+aq) a^k +w_2 (a^k + a^{k-1}) + \dots +w_{j-2}(a^k+a^{k-1}+ \dots +a^{k-j+3})\\
    &amp;&amp;+ (w_{j-1} +q)(a^k+a^{k-1}+ \dots +a^{k-j+2})+c_j(a^k+a^{k-1}+\dots + a^{k-j+1})\\
    &amp;&amp;+c_{j+1}(a^k+a^{k-1}+\dots + a^{k-j})+\dots +c_{k+1} (a^k +a^{k-1}+\dots +a^1+a^0).
\end{eqnarray*}
Now $c_j, c_{j+1}, ..., c_{k+1} \in \{0, 1, 2, \dots, a-1\}$, and repeating the procedure above at most $j-2$ times gives the
coefficients $c_i$ in the desired range for $i=2, 3, ..., k+1$.
\end{proof}


\begin{lemma}\label{recursive1} Let $n\in \mathbb{N},$ and let $q$ and $r$ be the unique integers such that $n=aq+r$, where $0\leq r&lt;a$.
Let $R=r\frac{a^{k+1}-1}{a-1}$. Then $n\in F_{a}(k)$ if and only if $n&lt;R$ or $\frac{n-R}{a}\in F_{a}(k-1)$.
\end{lemma}

\begin{proof} We prove that $n\notin F_a(k)$ if and only if $n\ge R$ and $\f{n-R}{a}\notin F_a(k-1).$

Suppose $n\geq R$ and $\frac{n-R}{a}\not\in F_{a}(k-1)$.  Then $\f{n-R}{a}$ is a nonnegative-integral combination of the elements
of $G_{a}(k-1)$; thus
$$\frac{n-R}{a}=c_{1}a^{k-1}+c_{2}(a^{k-1}+a^{k-2})+\dots+c_{k}(a^{k-1}+a^{k-2}+\dots+1)$$ for some $c_1, \ldots, c_k\in
\mathbb{Z}_{\ge 0}.$  Therefore
\begin{equation*}
\label{Lem2eq2}
n=c_{1}a^{k}+c_{2}(a^{k}+a^{k-1})+\dots+c_{k}(a^{k}+a^{k-1}+\dots+a) + R,
\end{equation*}
\noindent where $c_1$, $c_2$, ..., $c_{k}\in \mathbb{Z}_{\geq 0}$.
  Because
$R=r\left (\frac{a^{k+1}-1}{a-1}\right)=r\left(a^k+a^{k-1}+\cdots+ a + 1 \right)$, $n\not\in F_a(k)$.

Conversely, suppose $n\not\in F_a(k)$.  By Lemma \ref{lem1}, there exist $c_{1}\in \mathbb{Z}_{\geq 0}$ and
$c_2,c_3,\ldots,c_{k+1}\in \{0,\ldots,a-1\}$ such that
\begin{equation*}
\begin{array}{rcl}
\label{Lem2eq3}
n&amp;=&amp;c_{1}a^{k}+c_{2}(a^k+a^{k-1})+\cdots+c_{k+1}(a^k+\cdots+a+1)\\
 &amp;=&amp;a(c_1a^{k-1}+c_2(a^k+a^{k-1})+\cdots+c_{k+1}(a^{k-1}+\cdots+1))+c_{k+1}.
\end{array}
\end{equation*}
Since $r$ is unique and $0\le c_{k+1}&lt;a,$ we see from the equation above that $c_{k+1}=r$. Therefore,
\begin{equation*}
\label{Lem2eq4}
\frac{n-R}{a}=c_{1}a^{k-1}+c_{2}(a^{k-1}+a^{k-2})+\dots+c_{k}(a^{k-1}+a^{k-2}+\dots+1).
\end{equation*}
Thus, $\frac{n-R}{a}\not\in S_{a}(k-1)$.  Since $n-R\geq 0$, $n\geq R$.
\end{proof}




\begin{lemma}\label{recursive2} Let $n\not\equiv 0 \pmod a$. Then $n\in F_{a}(k)$ if and only if $n-\frac{a^{k+1}-1}{a-1}\in F_a(k)$.
\end{lemma}

\begin{proof}
Let $n-\frac{a^{k+1}-1}{a-1} \notin F_{a}(k)$.  Then $n\notin F_{a}(k)$ follows immediately.

Suppose $n\not\in F_{a}(k)$.  Write

\begin{equation*}
n=c_{1}a^{k}+c_{2}(a^{k}+a^{k-1})+\dots +c_{k+1}(a^k+a^{k-1}+\dots+a+1),
\end{equation*}
where $c_1\in\mathbb{Z}^+$ and $c_2$, $c_3, \dots , c_{k+1}\in \{ 0,1,\dots a-1 \}.$  Note that $c_{k+1}\geq 1$ since
$n\not\equiv 0$ (mod $a$).  Then
$$n-\frac{a^{k+1}-1}{a-1}=c_{1}a^{k}+c_{2}(a^k+a^{k-1})+\cdots+(c_{k+1}-1)\frac{a^{k+1}-1}{a-1},$$

\noindent which implies that $n-\frac{a^{k+1}-1}{a-1}\not\in F_a(k)$.
\end{proof}


We notice that the Frobenius number for the sets $G_a(k)$ is the largest element of $F_a(k),$ and since the sets $F_a(k)$ can be
described recursively we present an easy to prove formula for $g(G_a(k))$ in Theorem~\ref{frob}. We note that the sets $G_a(k)$
are part of a well studied class known as sequentially redundant sets. Recall that a \textit{sequentially redundant set} of
positive integers is a set $A=\{ a_1, a_2, \dots, a_n\}$ such that for $j =2, 3, \dots, n$, there exist non-negative integers
$t_{ij}$ such that
$$\frac{a_j}{d_j} = \frac{1}{d_{j-1}} \sum_{i=1}^{j-1} t_{ij} a_i,$$
where  $d_i = \gcd\{a_1, a_2, \dots, a_i\}$ for each $1\leq i\leq n$. The Frobenius number of a sequentially redundant set is
well-known \cite{NW}; thus the result below is not new.


\begin{theorem}\label{frob}
The Frobenius number of the set $G_a(k)$ is
$$g(\{a^k, a^k+a^{k-1}, \dots , a^k+a^{k-1}+\dots +a^0\}) = \frac{1-a^{k+1}k-a^{k+1}+a^{k+2}k}{a-1} $$
%(a-1)\left(\sum_{i=1}^{k} (a^k+a^{k-1}+ \dots +a^{k-i})\right)-a^k.$$
\end{theorem}

\begin{proof}
We proceed by induction on $k$.  $G_a(1) = \{a, a+1\},$ so using Sylvester's formula we have $g(\{a, a+1\}) = a(a+1) - (2a+1) =
(a-1)(a+1) - a$ as desired.  Next we assume the formula holds for $G_a(k-1)$.  Then the largest number in $S_a(k-1)$ is
 $$g(G_a(k-1)) = (a-1)\left(\sum_{i=1}^{k-1}(a^{k-1} + a^{k-2} + \cdots + a^{k-1-i})\right) - a^{k-1}.$$
Lemma~\ref{recursive1} implies that if $w$ is the largest element of $F_a(k-1),$ then for maximal $R$ $aw+R$ is the largest
element of $F_a(k)$.  The largest possible $R$ occurs for $r=a-1$; thus $R=a^{k+1}-1$.  Therefore
\begin{eqnarray*}
g(G_a(k)) &amp; = &amp; a\left((a-1)\left(\sum_{i=1}^{k-1}(a^{k-1} + a^{k-2} + \cdots + a^{k-1-i})\right) - a^{k-1}\right) \\
&amp;&amp;+a^{k+1}-1\\
 %&amp; = &amp; (a-1)\left(\sum_{i=1}^{k-1}(a^{k} + a^{k-1} + \cdots + a^{k-i})\right) - a^{k} + a^{k+1}-1 \\
 %&amp;=&amp; (a-1)\left(\sum_{i=1}^{k-1}(a^{k} + a^{k-1} + \cdots + a^{k-i})\right) - a^{k} \\
 %&amp; &amp;+(a-1)(a^k+a^{k-1}+ \cdots +a+1)\\
 &amp; = &amp; (a-1)\left(\sum_{i=1}^{k}(a^{k} + a^{k-1} + \cdots + a^{k-i})\right) - a^{k}\\
 &amp; = &amp; \frac{1-a^{k+1}k-a^{k+1}+a^{k+2}k}{a-1}.
\end{eqnarray*}\end{proof}



The next two lemmas describe the behavior of the function $z$ when a base-$a$ string of ones is subtracted from a base $a$ string
with a specific form.  We precede these lemmas with the following motivating example.


\begin{example} Let $a=3$ and consider the ternary string $$\gamma = 21101000100121.$$  Let $\delta = 111\cdots 1$ be a constant ternary
string of ones with $\len(\delta) = 14$.   We first calculate $\gamma - \delta$ and add a leading zero so $\len(\gamma - \delta)$
remains 14;  $\gamma -\delta = 02212111212010$.  Next we compare $z(\gamma)$ and $z(\gamma - \delta)$.  Contributing digits are
underlined below.

\begin{center}
\xymatrix@1@=1pt@M=6pt{ \gamma: &amp;&amp;2 &amp;1 &amp;1&amp;\underline{0}\ar[dd]&amp;1&amp;\underline{0} \ar[dd]&amp;\underline{0}\ar[dd]
&amp;\underline{0} \ar[dd] &amp;1 &amp;\underline{0} \ar[dd]&amp;\underline{0} \ar `d[l] `^d[llllllllll] [dlllllllllld] &amp;\underline{1} \ar[dd] &amp;2 &amp;1\\
&amp;&amp;&amp;&amp;&amp;&amp;&amp; {} &amp;&amp;&amp;&amp;&amp; \\
\gamma - \delta: &amp;&amp; \underline{0}&amp;2 &amp;2 &amp;\underline{1}&amp;2&amp;\underline{1}&amp;\underline{1}&amp;\underline{1} &amp;2 &amp;\underline{1} &amp;2 &amp;\underline{0}
&amp;1 &amp;0 }
\end{center}

Thus $z(\gamma) = 7 = z(\gamma-\delta)$. The key observation to make in this example is that all contributing digits in $\gamma$
are paired with contributing digits in the same position in $\gamma -\delta$ except for the rightmost contributing zero in
$\gamma,$ which is paired with the leading contributing digit in $\gamma -\delta$.
\end{example}


\begin{lemma}
\label{subtraction1}
Suppose a base-$a$ string $\gamma=h_n h_{n-1} \cdots h_{l+1} h_l h_{l-1} \cdots h_1 h_0$ satisfies the following conditions:
\begin{enumerate}
\item[(i)] for $0 \leq i \leq l-1$, $h_i &gt; 0$,
\item[(ii)] $h_l=0$ [note: it is possible that $l=1$],
\item[(iii)] for $l+1 \leq i \leq n-1,$ $h_i = 0$ or 1 (possibly empty), and
\item[(iv)] $h_n&gt;1$.
\end{enumerate}

\noindent Suppose $\delta$ is a base-$a$ string of 1's with length $n+1$.  Then $z(\gamma-\delta)=z(\gamma)$,
where $\gamma-\delta$ has the same length as $\gamma$ (by appending a leading zero if necessary).
\end{lemma}

\begin{proof} Firstly, note that $a&gt;2$ is forced by the given conditions.  Now, to compute $\gamma-\delta,$ we ``borrow'' from each
digit to the left of $h_l.$  The result is $$\gamma - \delta =
[h_n-2][h_{n-1}+a-2]\cdots[h_{l+1}+a-2][h_{l}+a-1][h_{l-1}-1]\cdots[h_{1}-1][h_0-1].$$



Since $2 \leq h_n \leq a-1,$  $h_n - 2 &lt; a-2.$  Also,
$h_{n-1}$ is either a 0 or 1 in $\gamma$.  Thus, the $n-1$ digit in $\gamma-\delta$ is $a-2$ more than the $n-1$ digit of
$\gamma$: it increases by $a$ due to borrowing from $h_n,$ loses one because the $n-2$ digit borrows from it, and loses one more
from subtracting $\delta$.  The value of the $n-1$ digit of $\gamma-\delta$ is thus either $a-2$ or $a-1$. Therefore, $h_{n}-2&lt;
h_{n-1}+a-2$, and the $n$ digit will be a drop in $\gamma -\delta$.  However, in $\gamma$, $h_n &gt; h_{n-1},$ so there is a drop in
$\gamma - \delta$ that is not in $\gamma$.

In $\gamma-\delta,$ the $l+1$ through $n-1$ digits are each $a-2$ more than $h_i$ (since $\gamma-\delta$ requires borrowing
throughout these digits), and therefore this section yields the same digit-by-digit contribution to $\gamma-\delta$ as to
$\gamma$.

Note that $h_l=0,$ so the $l$-digit of $\gamma-\delta$ is $a-1.$  (Since $h_l$ is the first zero appearing in $\gamma,$ no
borrowing is necessary to the right of $h_l.$)  If $h_{l+1}=0$ (and is hence part of a non-increasing sequence to the left of a
drop) in $\gamma$, then the $l+1$ digit in $\gamma - \delta$ is $a-2$ and is therefore a drop and counted as it was for
$z(\gamma)$. If $h_{l+1}=1$, then the $l+1$ digit in $\gamma - \delta$ has value $a-1$ and thus is not part of a non-increasing
sequence following a drop; it is again counted as it was for $z(\gamma)$. Thus, in either case, the contribution to
$\gamma-\delta$ from the $l+1$ digit is the same as it is in $\gamma$.


Since $h_{l-1}-1$ is less than $a-1$ and $h_{l}+a-1=a-1,$ the $l$ digit in $\gamma-\delta$ is not a drop.  However, the
digit at position $l$ in $\gamma$ is a drop since it is the first zero appearing in $\gamma.$  Thus, $\gamma-\delta$ loses a drop
that $\gamma$ had.

For $l-1&gt;i\geq 1$, each digit $h_i&gt;0$, and therefore no borrowing is required for corresponding digits in $\gamma - \delta$. Thus
these digits make the same contribution to $\gamma-\delta$ as to $\gamma.$

The net result of these considerations is that the contribution in $\gamma$ that occurs at $h_l$ is moved to the leading digit in
$\gamma-\delta,$ but all other contributions remain the same.  Therefore $z(\gamma-\delta)=z(\gamma),$ as desired.




\end{proof}

Before continuing with the next lemma, we pause to recall the relation $*$: if $\alpha$ and $\beta$ are nonempty base-$a$
strings, then $\alpha *\beta \iff |\alpha|&lt;z(\beta).$

\begin{lemma}\label{subtraction2}
Let $\beta=b_{k} b_{k-1} \cdots b_2 b_1 b_0$ and $\alpha$ be strings in base $a$.  Let $\delta=1\cdots 1$ be a string of
$k+1$ ones in base $a$.

Suppose
\begin{enumerate}
\item[(a)] $\beta \not\equiv 0 \pmod a$,


\item[(b)] $z(\beta)&gt;0$, and

\item[(c)] $|\alpha| &gt; 0$.
\end{enumerate}

Then
\begin{enumerate}
\item[(i)] for $|\beta|&gt;|\delta|$, $\alpha *\beta \Leftrightarrow \alpha * (\beta - \delta)$, and

\item [(ii)] for $|\beta|&lt;|\delta|$, $\alpha*\beta \Leftrightarrow [|\alpha | -1] * ([1]\beta -\delta)$, where $1$ and $\beta$ are
concatenated to create $[1]\beta&gt;\delta$.
\end{enumerate}

\end{lemma}

\begin{proof}  {\bf Case (i):} Suppose $|\beta|&gt;|\delta|$.  Then either $\beta$ is zero-free or it contains a zero.
If  $\beta$ is zero-free, then $\beta - \delta$ requires no borrowing, so $z(\beta)=z(\beta-\delta)$ and $\alpha$ does not
change.  (Note: this also implies that in Case (i), the hypotheses $|\alpha|&gt;0$ is unnecessary.)  Thus $ \alpha * \beta \iff
\alpha* (\beta - \delta)$.

Now suppose that $\beta$ contains at least one zero.  Write $\beta=b_{k}b_{k-1} \cdots b_1 b_0$.  Inductively define substrings
$\beta_i$,  $i=1,2,\dots m$, for $m&lt;k+1$, as follows:
$$\beta_1=b_{j_1}\cdots b_{l_1}\cdots b_1 b_0,$$ where $l_1$ is the smallest subscript in $\beta$ such that $b_{l_1}=0$, and
$j_1&gt;l_1$ is the smallest subscript in $\beta$ such that $b_{j_1}&gt;1$.  Note that this subscript exists since $|\beta|&gt;|\delta|.$
If $b_w=0$ for some $w&gt;j_1$, then define $\beta_2=b_{j_2}\cdots b_{l_2}\cdots b_{j_1}$, where $l_2&gt;j_1$ is the smallest subscript
such that $b_{l_2}=0$, and $j_2&gt;l_2$ is the smallest subscript such that $b_{j_2}&gt;1$. A diagram of the basic structure of each
$\beta_i$ is included below.
$$\overbrace{\underbrace{b_{j_i}}_{&gt;1} \underbrace{\dots \hspace{.05in}_{ \hspace{.01in}_{ \hspace{.01in} }} }_{\leq 1}
\underbrace{b_{l_i}}_{=0} \underbrace{\dots b_{j_{i-1}}}_{\neq0} }^{\beta_i}$$

Create successively $\beta_1, \beta_2, \beta_3, \ldots, \beta_m$ as above, where either $b_{k}$ appears in $\beta_m$ or $b_w&gt;0$
for all $w&gt;j_m$. In the former case, define $\beta_{m+1}$ to be the empty string; in the latter case, define $\beta_{m+1}=b_{k}
b_{k-1} \cdots b_{j_m}$.  The following diagram gives a picture of $\beta$ and the $\beta_i$ substrings.

\

\xymatrix@C=4pt@M=0pt{
\beta: &amp;&amp;b_k \ar@{-}@/^1pc/ [rr]|{\beta_{m+1}} &amp; \dots &amp; b_{j_m}  \ar@{-}@/^1pc/ [rrrr]|{\beta_{m}} &amp; \dots &amp;\underline{b_{l_m}}
\ar `d[l]  `^d[ll] [lld]
&amp; \dots &amp;b_{j_{m-1}} &amp;
% b_{j_2} \ar@{-}@/^1pc/ [rrrr]|{\beta_{2}} &amp; \dots &amp; \underline{b_{l_2}}
 %\ar `d[l]  `^d[ll] [lld]
&amp; \dots &amp; b_{j_1} \ar@{-}@/^1pc/ [rrrr]|{\beta_{1}} &amp; \dots&amp; \underline{b_{l_1}}  \ar `d[l]  `^d[ll] [lld]
&amp; \dots &amp; b_0 \\
\beta - \delta: &amp;&amp; &amp;{} &amp;\underline{b_{j_m }- 2}  &amp;{}&amp;{}&amp;{}&amp;{}&amp;{}
%&amp;\underline{b_{j_2} - 2} &amp;
&amp;&amp;\underline{b_{j_1} -2} &amp; }

\

The $\beta_i$ satisfy the hypotheses of Lemma \ref{subtraction1} and of quasi-linearity.   Thus each $b_{l_i}$ is contributing in
$\beta$ and is paired with the contributing digit $b_{j_i}-2$ in $\beta-\delta$.

Let $\delta_i$ denote a string of ones of length $\len(\beta_i)$ for $i=1,\dots , m+1$.
We compute:
\begin{eqnarray*}
z(\beta) &amp; = &amp; \sum_{i=1}^{m+1} z(\beta_i)  \hspace{.1in} \textrm{by quasi-linearity}\\
&amp;=&amp; \sum_{i=1}^{m+1} z(\beta_i-\delta_i) \hspace{.1in} \textrm{by Lemma~\ref{subtraction1}.}
\end{eqnarray*}

It remains to show that $ \sum_{i=1}^{m+1} z(\beta_i-\delta_i) = z(\beta -\delta)$.  Notice that quasi-linearity does not apply
to the strings $\beta_i-\delta_i$ as the leading digit of $\beta_i -\delta_i$ is one less than the last digit of $\beta_{i+1} -
\delta_{i+1}$.  However,  we can piece these strings together to form $\beta-\delta$ by deleting the last digit of each
$\beta_{i}-\delta_{i}$ for $i=2,\dots,m+1$ and concatenating appropriately.  Recall that these last digits are not contributing
digits to $\beta_i -\delta_i$ so none of them are underlined.  In addition, every digit in each $\beta_{i} - \delta_{i}$ has the
same right neighbor after forming $\beta-\delta$ (by deletion and concatenation) except  $b_{j_{i-1}+1}-1$, so we must only show
that $b_{j_{i-1}+1}-1$, for $i = 2, \dots , m+1$, contributes to $\beta_{i} - \delta_{i}$ if and only if it contributes to $\beta
- \delta$.  (That is, we must show that the deletion-concatenation procedure does not disturb any underlining.)

Now
\begin{eqnarray*}
b_{j_{i-1}+1} -1 \textrm{ contributes to } \beta_i - \delta_i &amp; \iff &amp; b_{j_{i-1}+1} -1 &lt; b_{j_{i-1}} -1 \\
&amp; \iff &amp; b_{j_{i-1}+1} -1 \leq b_{j_{i-1}} -2.
\end{eqnarray*}

We know from the proof of Lemma \ref{subtraction1} that $b_{j_i-1}-2$ contributes to $\beta_{i-1}-\delta_{i-1},$ and hence to
$\beta-\delta.$  This implies that $b_{j_{i-1}+1} -1\leq b_{j_{i-1}}-2$ if and only if $b_{j_{i-1}+1}-1$ contributes to
$\beta-\delta.$

Thus each contribution to $\beta_i-\delta_i$ is counted once and only once in $\beta-\delta,$ so $\sum_{i=1}^{m+1}z(\beta_i-\delta_i)=
z(\beta-\delta).$

{\bf Case (ii):} Now consider $|\beta|&lt;|\delta|$.  If $\beta$ has no digits larger than 1, then form $\tilde{\beta}$ as below
(with $t=-1$). If $\beta$ has a digit larger than 1, let $t$ be the largest integer such that $b_t&gt;1$.  Apply case (i) to $\beta'
= b_t
\dots b_1 b_0$ and $\delta' = 1 \dots 1$, a string of $t+1$ ones.  Then $z(\beta') = z(\beta'-\delta')$.

Consider $\tilde\beta =[1]b_kb_{k-1}\dots b_{t+1}= [a+b_k] b_{k-1} \dots b_{t+1}$ where $b_{t+1}, \dots, b_k \in \{0, 1\}$.  Let
$s \geq t+1$ be the least integer such that $b_s=0$.  Note that such a $b_s$ exists since $|\beta| &lt;|\delta|$.  Let $\tilde\delta
= 1\dots 1$ be a string of $k-t$ ones.  For $i$ from $t+1$ through $k$, the digits $c_i$ of $\tilde\beta - \tilde\delta$ are as
follows:
\[
\left\{
\begin{array}{cl}
 c_i = 0, &amp;  \textrm{ if }t+1\leq i&lt;s;   \\
 c_s =a-1; &amp; \\
 c_i = a-1,&amp; \textrm{if } i&gt;s \textrm{ and } b_i=1;    \\
  c_i = a-2, &amp;  \textrm{ if } i&gt;s \textrm{ and } b_i = 0.
\end{array}
\right.
\]

If $t\ge 0,$ then the digits labelled $t+1$ through $s-1$ of $\tilde\beta$ are all 1, and the corresponding digits of
$\tilde\beta-\tilde\delta$ are all 0.  Since the $t+1$ digit is a drop in either case, both strings contribute the same.  If
$t=-1,$ then digits $t+1=0$ through $s-1$ of $\tilde\beta$ are all 1 (since $\beta\not\equiv 0$ (mod $a$)) and the corresponding
digits of $\tilde\beta-\tilde\delta$ are all 0, and none of these contribute.  Note that the string of digits from $t+1$ to $s-1$
could be empty.

Now $b_s=0$ contributes to $\tilde\beta$ since it is a drop from the preceding digit, but the $s$th digit of
$\tilde\beta-\tilde\delta$ does not contribute since it equals $a-1.$  Thus, the contributions in $\beta$ up through the $s$th
digit are $z(\beta')+(s-t-1)+1,$ and the contributions in $[1]\beta-\delta$ up through the $s$th digit are $z(\beta')+(s-t-1).$


  From the table above, we see that the $s+1$ through $k$ digits contribute in $\beta$ if and only if they contribute in $[1]\beta
-\delta$ since $0\leftrightarrow a-2$ and $1 \leftrightarrow a-1$.  For $b_s$ becomes $a-1$ in $\tilde\beta-\tilde\delta.$
Therefore, if $b_{s+1}=0$ (and therefore contributes to $\beta),$ then the $s+1$ digit of $\tilde\beta-\tilde\delta$ is $a-2,$
which contributes to $\tilde\beta-\tilde\delta.$  If $b_{s+1}=1$ (and therefore does not contribute to $\beta),$ then the $s+1$
digit of $\tilde\beta-\tilde\delta$ is $a-1,$ which does not contribute to $\tilde\beta-\tilde\delta.$  The remaining digits of
$\tilde\beta-\tilde\delta$ may be considered in the same way.

Thus, overall, we have $z([1]\beta - \delta) =z(\beta) -1$ since only the $s$th digit contributes differently in $\beta$ and
$\tilde\beta-\tilde\delta.$

\end{proof}


\begin{theorem}\label{starthrm} For nonempty strings $\alpha$ and $\beta$
with $\left\vert \alpha \beta \right\vert \neq 0,$ $$\alpha * \beta
\Leftrightarrow \left\vert \alpha \beta \right\vert \in F_{a}(len(\beta )-1).$$
\end{theorem}

\begin{proof} We proceed by induction on $n:=|\alpha \beta|$.
Set $k:=len(\beta )-1$, so the theorem asserts $\alpha * \beta
\Leftrightarrow n\in F_a(k)$.


If  $n=1$, then $\left\vert \alpha \right\vert =0, |\beta|=1,$ $\beta=\underbrace{0\cdots 01}_{k+1\mbox{ digits}}$ and
$z(\beta)=k$, so $\alpha
\ast \beta \Leftrightarrow |\alpha|&lt;z(\beta) \Leftrightarrow 0&lt;k \Leftrightarrow 1\in F_a(k)$, where the last equivalence follows
from the definition of $F_a(k)$ and the fact that $1\in F_a(k)$ exactly when $k&gt;0.$

Now assume that $n&gt;1$ and that the theorem holds for all smaller positive integers.
\begin{enumerate}
\item[(i)] \ Suppose $n\equiv 0$ (mod $a$). \

Write $\beta =\beta ^{\prime }0$, and note $\len(\beta ^{\prime})=k$ and $z(\beta )=z(\beta ^{\prime })$ since appending a zero
to the right of $\beta'$ cannot introduce a drop.  Then
\begin{equation*}
\alpha * \beta \Leftrightarrow \alpha \ast \beta ^{\prime
}\Leftrightarrow \frac{n}{a}=\left\vert \alpha \beta ^{\prime }\right\vert \in F_a(k-1)\Leftrightarrow n\in F_a(k),
\end{equation*}
where the second equivalence follows by induction and the last from Lemma~\ref{recursive1} since $R=0.$

\item[(ii)] \ Suppose $n\not\equiv 0$ (mod $a$). Note that this implies that in base $a,$ the last digit of $\beta$ is nonzero.
There are three cases:

\begin{enumerate}
\item[(a)]  Suppose $z(\beta )=0$. Then $\beta$ has no drops and thus can be written as a sum of the elements in
$G_{a}(k)$. Then $\left\vert \beta \right\vert =c_{1}a^{k}+\dots+c_{k+1}(a^k+\dots +a+1)$, and $n=\left\vert
\alpha
\right\vert \cdot a^{k+1}+c_{1}a^{k}+\dots+c_{k+1}(a^k+\dots +a+1)\notin F_a(k)$.  \ In this case, $\alpha \ast \beta $
and $n\in F_a(k)$ are both false.

\item[(b)] Suppose $z(\beta )&gt;0$ and $\left\vert \alpha \right\vert =0$. \  Certainly $n=\left\vert \beta \right\vert \le
a^{k+1}-1$. In fact, since $\beta$ has a drop, we have $n&lt;a^{k+1}-1.$  (The base-$a$ digits of $\beta$ cannot all equal $a-1$
since $\beta$ has a drop.) There are two cases.
\begin{enumerate}
\item[(1)]
If $\left\vert \beta \right\vert &lt;a^k+\dots +a+1$, then $n&lt; R$ ($n\not\equiv 0 \pmod{a}\implies R\ge a^k+\ldots+a^1+a^0)$.  Thus, by
Lemma~\ref{recursive1}, $n\in F_a(k),$ and therefore $\alpha \ast \beta $ and $n\in F_a(k)$ are both true.

\item[(2)] Again let $\delta$ be a string of $k+1$ ones in base $a,$ and assume that
$a^k+\dots +a+1\leq \left\vert \beta \right\vert &lt;a^{k+1}-1$.  Since $|\alpha|=0,$ we may apply Lemma
\ref{recursive1} to obtain $$\alpha \ast \beta \Leftrightarrow \alpha\ast (\beta - \delta)
\Leftrightarrow |\alpha\beta|-|\delta|=n-(a^k+\ldots+a+1)\in F_a(k)\Leftrightarrow n\in F_a(k),$$
where it is understood that $\len(\beta-\delta)=\len(\beta).$  The first equivalence follows from Lemma~\ref{subtraction2}
(recall that the hypothesis $|\alpha|&gt; 0$ was unnecessary for Case (i)), the second from the induction hypothesis, and the last
from Lemma~\ref{recursive2}.
\end{enumerate}

\item[(c)] Suppose $z(\beta )&gt;0$ and $\left\vert \alpha \right\vert &gt;0$; then by Lemma \ref{subtraction2}
\bal{\alpha \ast \beta &amp;\Leftrightarrow \alpha * (\beta - \delta) \mbox{ or } \left [ \left\vert\alpha\right\vert -1 \right ] \
\ast ([1]\beta - \delta)\\
    &amp;\Leftrightarrow n-(a^k+\dots +a+1)\in F_a(k)\\
    &amp;\Leftrightarrow n\in F_a(k),}
where the first equivalence follows from Lemma~\ref{subtraction2}, the second from the induction hypothesis, and the last from
Lemma~\ref{recursive2}.
\end{enumerate}
\end{enumerate}
\end{proof}

Theorem \ref{mainthrm} is actually a corollary of Theorem~\ref{starthrm}.  One can easily compute $f_{a}(n)$ from Theorem~
\ref{mainthrm}. Here are a few example calculations.  Notice that to apply Theorem~\ref{mainthrm} it may be necessary to write a
string with leading zeros.

\bc\label{cor} Let $n\in \Z^+.$  Then $n\in F_a(k)$ if and only if there exist base-$a$ strings $\alpha$ and $\beta$ such that
\be \item $|\alpha\beta|=n$,
    \item $\alpha *\beta,$ and
    \item $k=\len(\beta)-1.$
\ee
\ec

\bp If such strings $\alpha$ and $\beta$ exist, then $n=\alpha\beta\in F_a(k)$ by Theorem \ref{starthrm}.  Conversely, if $n\in
F_a(k),$ then let $\beta$ be the last $k+1$ digits of a base-$a$ representation of $n$, and let $\alpha$ be the remaining digits,
setting $\alpha=0$ if otherwise $\alpha$ would be empty. This gives $|\alpha\beta|=n$ and $k=\len(\beta)-1$ directly.
Furthermore, since $|\alpha\beta|=n\in F_a(k), \alpha *\beta$ by Theorem \ref{starthrm}.
\ep




\begin{example}


\begin{enumerate}
\item For $n=24=|11000|=|0011000|$ with base $a=2,$ let $\alpha=0$ and $\beta=011000$; then $|\alpha \beta|= 24$ and $0=|\alpha| &lt;
z(\beta)=1$. We see that $f_{2}(24)=\len(\beta)-1=5$ since for no shorter $\beta$ will we have a drop.

\item In ternary, for $n=50_{10} = |1212_3|$, let $\alpha=0$ and $\beta=1212$; then $|\alpha \beta|= 50$ and $0=|\alpha| &lt; z(\beta)=2$.
Thus $f_{3}(50)=\len(\beta)-1=3$.

\item In base 7, for $n=22413_{10}=|122226_7|$, let $\alpha=1$ and $\beta=22226$; then $|\alpha\beta|=22413$ and $1=|\alpha| &lt;
z(\beta)=4$. Therefore $f_{7}(22413)=4$.
\end{enumerate}
\end{example}



We note that Theorem~\ref{starthrm} and Corollary~\ref{cor} completely characterize the Frobenius sets, $F_a(k)$.  In addition,
if $n \not\in F_a(k-1)$ there is a simple algorithm giving $n$ as a non-negative linear combination of the elements of
$G_a(k-1)$.

\

{\bf Representation Algorithm:}  Assuming $n \not\in F_a(k-1)$
   the following algorithm gives $t_i \geq 0$ such that
   $$n=t_0 a^{k-1}+t_1 (a^{k-1}+a^{k-2}) +t_2(a^{k-1}+a^{k-2}+a^{k-3})+ \dots +t_k(a^{k-1}+\dots+a^1+a^0).$$

\be
\item  Write $n$ in base $a$ as $n=c_r\cdots c_1c_0.$
\item  Let $t_k := c_0$ and $Remain:=n-t_k(a^{k-1}+\dots+a^1+a^0)$.
\item  If $Remain=0$,  put $t_{k-1} = t_{k-2} = \dots = t_0:=0$, then STOP.
\item  Let $m:=1$.
\item  Write $Remain$ in base $a$ as  $c_{mr}\dots c_{m2} c_{mm} \overbrace{00\dots0}^{m \hspace{.1in}\textrm{zeros}}.$
\item  Let $t_{k-m} := c_{mm}$ and put $Remain:= Remain - t_{k-m}(a^{k-1}+a^{k-2}+\dots +a^m)$.
\item  If $Remain=0$, put $t_{k-m-1} =t_{k-m-2} \dots =t_0:=0$, then STOP.
\item  If $Remain &gt; 0$, put $m:=m+1$.  If $m&lt;k$  GOTO step (5).
\item  If $Remain &gt; 0$ and $m=k$, put $t_0 = \frac{Remain}{a^k}$.  STOP.
\ee

Here is an example using the  Representation Algorithm.

\begin{example} Suppose $a=3$.  Let $n=1541=2\cdot 3^6+3^4+2$.  The ternary representation of $1541$ is $2010002$.  Since $2*010002$ holds
but $20*10002$ is false, $1541 \in F_3(5)$ but $1541 \not\in F_3(4)$ by Corollary~\ref{cor}.  Recall that $G_3(4) = \{81, 108,
117, 120, 121\}$.  We begin by writing the elements of $G_3(4)$ in base $a=3$: $[G_3(4)]_3 = \{ 10000, 11000, 11100, 11110,
11111\}$. We will find non-negative coefficients $t_i$ such that
$$2010002=t_0(10000)+t_1(11000)+t_2(11100)+t_3(11110)+t_4(11111)$$

The ternary representation of $1541$ implies $t_4 = 2$.   The next few steps outlined below involve subtracting the appropriate multiple of the elements of $G_3(4)$.  The quantity $Remain$ is changed by each subtraction and each new $Remain$ amount gives another $t_i$.

\[
\begin{array}{crcrcrcr}
&amp; \textrm{Step }1&amp;&amp;\textrm{Step } 2&amp;\\
n=&amp;2010002  &amp;  \hspace{.2in} &amp;  1210010  &amp; \hspace{.2in} &amp;\\
 &amp;\underline{-    22222 } &amp;   &amp; \underline{- 11110}   &amp;&amp;\\
Remain: &amp; 1210010 &amp;   &amp;   1121200 &amp;&amp; \\
&amp;  \implies t_3=1&amp;&amp; \implies t_2=2&amp;&amp;
\end{array}
\]


\[
\begin{array}{crcrcrcr}
&amp; \textrm{Step }3&amp;&amp;\textrm{Step } 4\\
n=&amp;1121200  &amp; \hspace{.2in} &amp;1022000 \\
  &amp; \underline{-22200}&amp;&amp; \underline{-22000}\\
Remain: &amp; 1022000 &amp;&amp; 1000000\\
&amp; \implies t_1=2&amp;&amp; \implies t_0= 9
\end{array}
\]

%%Check:  9(81)+2(108)+2(117)+1(120)+2(121) = 1541.
\end{example}



\section{Theorem~\ref{starthrm} as an Algorithm}
Fix the integer $a\geq 2$.
In this section we present the algorithm for determining, given $n\in \Z^+$, the least $k$ such that $n\in F_a(k).$  We then
briefly discuss the computational complexity of our algorithm.

\noindent {\bf Algorithm:}
\be
\item Write $n$ in base $a:$ $n=c_k\cdots c_1c_0.$
\item Let $\alpha_0:=c_k\cdots c_1$ and $\beta_0:=c_0.$
\item If $\alpha_0*\beta_0,$ then $n\in F_a(0).$  STOP.
\item If not $\alpha_0*\beta_0,$ let $l:=1.$
\item Let $\alpha_l:=c_k\cdots c_{l+1}$ and $\beta_l:=c_l\cdots c_0.$

\item If $\alpha_l*\beta_l,$ then $n\in F_a(l).$ STOP.
\item If $l&lt;k-1,$ then put $l:=l+1.$  GOTO step 5.
\item Let $\alpha_k:=0$ and $\beta_k:=c_k\cdots c_0.$
\item If $\alpha *\beta,$ then $n\in F_a(k).$  STOP.
\item Let $\alpha_{k+1}:=0$ and $\beta_{k+1}=0c_k\cdots c_0.$  Then $|\alpha|=0$ and $z(\beta_{k+1})=1,$ so $\alpha*\beta$ and
$n\in F_a(k+1).$  STOP.
\ee

It is clear that the above algorithm terminates.  Furthermore, since the algorithm checks membership in $F_a(k)$ for each value
of $k$ sequentially beginning with $k=0,$ it must determine the least value of $k$ such that $n\in F_a(k),$ as desired.

In the worst case, steps 5 through 7 are repeated at most $\log_a(n-1)+1$ times.  Each iteration requires about $\log_a(n)$
operations (mostly from computation of $z(\beta)).$ Steps outside of this loop require minimal computation, so the algorithm is
$O(\log^2_a(n))$.  Note that this algorithm can be improved to $O(\log(n))$ by repeated bisection of the base-$a$ representation of $n$.


We note in closing that a working group at Willamette University has studied a similar Frobenius-level problem for the following related $G$-sets.  For positive integers $a, b, c, d$ such that $\gcd(a, b) = \gcd(c, d) = 1$ and $ a&lt;b$, define $G(0) = \{a, b\}$, $G(1) =\{ac, bc, bc+d \}$, and for $k\geq 2$ $$G(k) = \{ac^k, bc^k, bc^k+dc^{k-1}, bc^k+dc^{k-1}+dc^{k-2}, \dots, bc^k+dc^k+\dots+dc^0\}.$$  They have found necessary and sufficient conditions for nested corresponding Frobenius-sets.   They are working to solve the Frobenius-level problem for these more general sequentially redundant sets \cite{2006frob}.


\begin{thebibliography}{99}

\bibitem{2006frob}{ P. Cudworth, T. Dailey, M. Flink, G. Houser, I. Johnson, B. Kehr, P. Le, J. Petersen, and C. Starr, Characterizing a generalized infinite family of Frobenius semigroups by filtration, in
preparation.}

\bibitem{Cu}{ F. Curtis, On formulas for the Frobenius number of a numerical semigroup, {\it Math. Scand.} {\bf 67} (1990), 190--192.}

\bibitem{D}{J. L. Davison, On the linear Diophantine problem of Frobenius, {\it J. Number Theory} {\bf 48} (1994), 353--363.}

\bibitem{G}{H. Greenberg, Solution to a linear Diophantine equation for nonnegative integers, {\it J. Algorithms} {\bf 9} (1988), 343--353. }

\bibitem{JM}{ I. Johnson and J. L. Merzel, A class of left ideals of the Steenrod algebra, {\it Homology, Homotopy Appl.} {\bf 9} (2007), 185--191.}

\bibitem{Kannan}{R. Kannan, Lattice translates of a polytope and the Frobenius problem, {\it Combinatorica} {\bf 12} (1992), 161--177.}

\bibitem{MT}{R. E. Mosher and M. C. Tangora, \textit{Cohomology Operations and Applications in Homotopy Theory}, Harper \&amp; Row, 1968.}

\bibitem{NW}{Albert Nijenhaus and Herbert S. Wilf, Representations of integers by linear forms in nonnegative integers, {\it J. Number Theory} {\bf 4} (1972), 98--106.}

%\bibitem{Ow}{R. W. Owens, An algorithm to solve the Frobenius problem, {\it Math. Mag.} {\bf 76} (2003),  264--275.}

\bibitem{RA}{J. L. Ram\'{i}rez-Alfons\'{i}n, Complexity of the Frobenius problem, {\it Combinatorica}, {\bf 16} (1996), 143--147.}

\bibitem{Rav}{D. C. Ravenel, \textit{Complex Cobordism and Stable Homotopy Groups of Spheres,}  Academic Press, 1986.}

\bibitem{Steen}{N. E.  Steenrod and D. B. A. Epstein, \textit{Cohomology Operations,} Princeton University Press, 1962.}

\bibitem{Syl} J. J. Sylvester, Problem 7382, 
{\it Math. Quest. Sol. Educational Times} {\bf 41} (1884), ix, 21.

\bibitem{Wood}{R. M. W. Wood,  Problems in the Steenrod algebra, \textit{Bull. London Math. Soc.} \textbf{30} (1998), 449--517.}
\end{thebibliography}


\bigskip
\hrule
\bigskip

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

\noindent \emph{Keywords: } Frobenius problem,
Frobenius level, sequentially redundant, Frobenius semigroup.

\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received August 1 2006;
revised versions received August 31 2007; September 13 2008; October 20 2008.
Published in {\it Journal of Integer Sequences}, December 14 2008.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                

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