<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{mathrsfs}
\def\mod{\!\pmod}
\def\g{\tt g}
\def\m{\tt m}
\def\n{\tt n}
\def\s{\tt s}
\def\C{\mathscr C}
\def\G{\Gamma}
\def\S{\mathcal S}
\def\Imp{\Rightarrow}
\def\ds{\displaystyle}
\def\ts{\textstyle}
\def\lf{\lfloor}
\def\rf{\rfloor}
\def\lc{\lceil}
\def\rc{\rceil}
\def\Iff{\Leftrightarrow}
\def\LIff{\Longleftrightarrow}
\def\D{\Delta}
\def\G{\Gamma}
\def\L{\Lambda}
\def\N{\mathbb N}
\def\Z{\mathbb Z}
\def\a{\alpha}
\def\b{\beta}
\def\k{\kappa}
\def\l{\lambda}
\def\d{\delta}
\def\e{\epsilon}
\def\m{\bf m}
\def\s{\bf s}
\def\ov{\overline}
\def\es{\emptyset}
\def\imp{\rightarrow}
\def\pr{\prime}
\def\sm{\setminus}

\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}
\newtheorem{obs}[theorem]{Observation}

\begin{center}
\vskip 1cm{\LARGE\bf 
The Frobenius Problem for Modified \\
\vskip .1in
Arithmetic Progressions
}
\vskip 1cm
\large
Amitabha Tripathi\\
Department of Mathematics\\
Indian Institute of Technology\\
Hauz Khas, New Delhi -- 110016\\
India\\
\href{mailto:atripath@maths.iitd.ac.in}{\tt atripath@maths.iitd.ac.in}
\end{center}

\vskip .2 in


\begin{abstract}
For a set of positive and relatively prime integers $A$, let ${\G}(A)$
denote the set of integers obtained by taking all nonnegative
integer linear combinations of integers in $A$. Then there are finitely
many positive integers that do not belong to ${\G}(A)$. For the
modified arithmetic progression $A=\{a,ha+d,ha+2d,\ldots,ha+kd\}$,
$\gcd(a,d)=1$, we determine the largest integer ${\g}(A)$ that does not
belong to ${\G}(A)$, and the number of integers ${\n}(A)$ that do not
belong to ${\G}(A)$. We also determine the set of integers
${\S}^{\star}(A)$ that do not belong to ${\G}(A)$ which, when added to
any positive integer in ${\G}(A)$, result in an integer in ${\G}(A)$.
Our results generalize the corresponding results for arithmetic
progressions.
\end{abstract}


\section{Introduction}

Given a finite set $A=\{a_1,\ldots,a_k\}$ of positive integers with $\gcd\,A:=\gcd(a_1,\ldots,a_k)=1$, let $\G(A):=\{a_1x_1+\cdots+a_kx_k: x_i \ge 0\}$ 
and ${\G}^{\star}(A)=\G(A) \sm \{0\}$. It is well known that ${\G}^c(A):={\N} \sm \G(A)$ is finite. Although it was Sylvester \cite{Syl84} who first asked to determine
\[ {\g}(A):= \max {\G}^c(A), \]
and who showed that ${\g}(a_1,a_2)=(a_1-1)(a_2-1)-1$, it was Frobenius who was largely instrumental in giving this problem the early recognition,
and it is after him that the problem is named.
Ram\'{\i}rez-Alfons\'{\i}n's monograph on the Frobenius problem \cite{Ram05} gives an extensive survey. Related to the Frobenius problem is the problem of determining ${\n}(A):=|{\G}^c(A)|$. As in the case of determining ${\g}(A)$, it was Sylvester who showed that ${\n}(a_1,a_2)=\frac{1}{2}(a_1-1)(a_2-1)$. 

Tripathi \cite{Tri03} introduced the following variation of the Frobenius problem. Let
\[ {\S}^{\star}(A):= \{n \in {\G}^c(A): n+{\G}^{\star}(A) \subset {\G}^{\star}(A) \}. \]
Since ${\g}(A)$ is the largest integer in ${\S}^{\star}(A)$, the determination of ${\S}^{\star}(A)$ also provides the resolution of ${\g}(A)$. For the sake of convenience, we recall the following essential result regarding ${\S}^{\star}(A)$ from \cite{Tri03}. Fix $a \in A$, and let ${\m}_{\bf C}$ denote the smallest integer in ${\G}(A) \cap {\bf C}$, where ${\bf C}$ denotes a nonzero residue class modulo $a$. If ${\C}$ denotes the set of all nonzero residue classes modulo $a$, then
\begin{equation}\label{S*}
{\S}^{\star}(A) \subseteq \{{\m}_{\bf C}-a: {\bf C} \in {\C}\}.
\end{equation}
Moreover, if $(x)$ denotes the residue class of $x$ modulo $a$ and ${\m}_x$ the least integer in ${\G}(A) \cap (x)$, then
\begin{equation}\label{S*elt}
{\m}_j-a \in {\S}^{\star}(A) \LIff {\m}_j-a \ge {\m}_{j+i}-{\m}_i \;\;{\rm for}\;\;1 \le i \le a-1.
\end{equation}
Observe that ${\S}^{\star}(A) \ne \es$; in fact, ${\g}(A)$ is the largest integer in ${\S}^{\star}(A)$. A complete description of ${\S}^{\star}(A)$ would therefore lead to the determination of ${\g}(A)$. 

The functions ${\g}$ and ${\n}$ are easily determined from the values of ${\m}_{\bf C}$ by Lemma \ref{gn}. Brauer and Shockley \cite{BS62} proved (i) and Selmer \cite{Sel77} proved (ii); a short proof of both results may be found in \cite{Tri94}. 

\begin{lemma} \label{gn}
{\bf (\cite{{BS62,Sel77}})} Let $a \in A$. Then
\begin{itemize}
\item[{\rm (i)}]
${\g}(A)=\ds\max_{\bf C}\: {\m}_{\bf C}-a$, the maximum taken over all nonzero classes $\bf C$ modulo $a$;
\item[{\rm (ii)}]
${\n}(A)=\ds\frac{1}{a}\sum_{\bf C} {\m}_{\bf C} - \ts\frac{1}{2}(a-1)$, the sum taken over all nonzero classes $\bf C$ modulo $a$.
\end{itemize}
\end{lemma}

In cases when all but one integer in $A$ have a nontrivial divisor, the following reduction formulae given by Lemma \ref{gnreduction} is useful. Johnson \cite{Joh60} gave the reduction formulae for ${\g}(A)$ and R{\o}dseth \cite{Rod78} for ${\n}(A)$; a short proof of both results may be found in \cite{Tri06}. 

\begin{lemma} \label{gnreduction}
{\bf (\cite{{Joh60,Rod78}})} Let $a \in A$, let $d=\gcd\big(A \sm \{a\}\big)$, and define $A^{\pr}:=\frac{1}{d}\big(A \sm \{a\}\big)$.
\begin{itemize}
\item[{\rm (i)}]
${\g}(A) = d \cdot {\g}\big(A^{\pr} \cup \{a\}\big)+a(d-1)$;
\item[{\rm (ii)}]
${\n}(A) = d \cdot {\n}\big(A^{\pr} \cup \{a\}\big)+\frac{1}{2}(a-1)(d-1)$.
\end{itemize}
\end{lemma}

In this article, we determine ${\g}(A)$, ${\n}(A)$ and ${\S}^{\star}(A)$ for the modified arithmetic progression $A=\{a,ha+d,ha+2d,\ldots,ha+kd\}$ with $\gcd(a,d)=1$. 

\section{The case $A=\{a,ha+d,ha+2d,\ldots,ha+kd\}$}

For arithmetic progressions, Roberts \cite{Rob56} determined ${\g}(A)$, later simplified by Bateman \cite{Bat58}, while Grant \cite{Gra73} determined ${\n}(A)$. A simple proof for both these results using Lemma \ref{gn} can be found in \cite{Tri94}. In fact, it is also possible to determine ${\S}^{\star}(A)$ in this case; see \cite{Tri03}. The result about ${\g}(A)$ and ${\n}(A)$ when $A$ consists of terms in arithmetic progression can be modified or extended in many ways. One such modification is to consider $A=\{a,ha+d,ha+2d,\ldots,ha+kd\}$ with $\gcd(a,d)=1$ and $h,k \ge 1$. The result for ${\g}(A)$ is due to Selmer \cite{Sel77}, but we provide a simpler proof that also leads to other results. 

Henceforth let $A=\{a,ha+d,ha+2d,\ldots,ha+kd\}$ with $\gcd(a,d)=1$ and $h,k \ge 1$. Then ${\g}(A)$ denotes the largest $N$ such that
\begin{equation}\label{genap}
ax_0 + (ha+d)x_1 + (ha+2d)x_2 + \cdots + (ha+kd)x_k = a \left( x_0+h \ts\sum_{i=1}^k x_i \right) + d \left(\ts\sum_{i=1}^k ix_i \right) = N
\end{equation}
has no solution in nonnegative integers, and ${\n}(A)$ the number of such integers $N$. 

\begin{lemma} \label{minclass}
For each $x$, $1 \le x \le a-1$, the least positive integer of the form given by equation (\ref{genap}) in the class $dx \bmod a$ is given by $ha\left(1+\lf\frac{x-1}k\rf\right)+dx$.
\end{lemma}

\begin{proof}
Let ${\m}_{dx}$ denote the least positive integer in the class $(dx)$ modulo $a$. Then ${\m}_{dx}$ is the minimum value attained by the expression on the left in equation (\ref{genap}) subject to $\sum_{i=1}^k\:ix_i=x$ and each $x_i \ge 0$. If $x=qk+r$, $0 \le r \le k-1$, the sum $x_0+h\sum_{i=1}^k\:x_i$ is minimized by choosing $x_k=q$, $x_r=1$ and $x_i=0$ for all other $i$, unless $r=0$ in which case we must choose $x_r=0$. Thus the minimum value for $x_0+h\sum_{i=1}^k\:x_i$ is $h(q+1)$ if $r \ne 0$ and $hq$ if $r=0$, which may be combined as $h\left(1+\lf\frac{x-1}{k}\rf\right)$. Hence ${\m}_{dx}=ha\left(1+\lf\frac{x-1}{k}\rf\right)+dx$.
\end{proof}

\begin{theorem} \label{gnformula}
Let $a,d,h,k$ be positive integers, with $\gcd(a,d)=1$. Then
\begin{itemize}
\item[{\rm (i)}]
${\g}\big(a,ha+d,ha+2d,\ldots,ha+kd\big) = ha \left\lf\frac{a-2}{k} \right\rf + (h-1)a + d(a-1)$;
\item[{\rm (ii)}]
${\n}\big(a,ha+d,ha+2d,\ldots,ha+kd\big) = \frac{1}{2}h(a+r)\left(1+\left\lf \frac{a-2}{k} \right\rf \right) + \frac{1}{2}(a-1)(d-1)$, where $r \equiv a-2$ mod $k$.
\end{itemize}
\end{theorem}

\begin{proof}
\begin{itemize}
\item[]
\item[{\rm (i)}]
\[ \begin{array}{lcl}
{\g}\big(a,ha+d,ha+2d,\ldots,ha+kd\big) &amp; = &amp; \ds\max_{\bf C \in \C}\: {\m}_{\bf C} - a \\
&amp; = &amp; \ds\max_{1 \le x \le a-1}\: \Big( ha \left(1 + \left\lf \ts\frac{x-1}{k} \right\rf \right) + dx \Big) - a \\[10pt]
&amp; = &amp; ha \left\lf \ts\frac{a-2}{k} \right\rf + (h-1)a + d(a-1).
\end{array}
\]

\item[{\rm (ii)}]
Write $a-2=qk+r$, with $0 \le r \le k-1$. Then
\[ \begin{array}{lcl}
{\n}\big(a,ha+d,ha+2d,\ldots,ha+kd\big) &amp; = &amp; \frac{1}{a}\ds\sum_{\bf C \in \C}\: {\m}_{\bf C} - \ts\frac{1}{2}(a-1) \\
&amp; = &amp; \frac{1}{a} \ds\sum_{x=1}^{a-1}\:\Big( ha \left( 1+\left\lf \ts\frac{x-1}{k} \right\rf \right) + dx \Big) - \ts\frac{1}{2}(a-1) \\[14pt]
&amp; = &amp; h \ds\sum_{x=0}^{a-2}\: \left( 1+\left\lf \ts\frac{x}{k} \right\rf \right) + \ts\frac{1}{2}d(a-1) - \ts\frac{1}{2}(a-1) \\[14pt]
&amp; = &amp; h \big( k(1+2+\cdots+q) + (q+1)(r+1) \big) \\[10pt]
&amp;    &amp; + \frac{1}{2}(a-1)(d-1) \\[10pt]
&amp; = &amp; \frac{1}{2}h(a+r)\left(1+\left\lf \frac{a-2}{k} \right\rf \right) + \frac{(a-1)(d-1)}{2}.
\end{array}
\]
\end{itemize}
\end{proof}

\begin{obs}
The case when $A$ consists of integers in arithmetic progression is the special case $h=1$ in Theorem \ref{gnformula}.
\end{obs}

Recall that ${\S}^{\star}(A):=\{n \in {\G}^c(A): n+{\G}^{\star}(A) \subset {\G}^{\star}(A)\}$. Since ${\g}(A)$ is the {\it largest} element in ${\S}^{\star}(A)$, the set ${\S}^{\star}(A)$ is intimately linked with the Frobenius problem. 

\begin{theorem} \label{S*formula}
Let $a,d,h,k$ be positive integers, with $\gcd(a,d)=1$. Write $a-1=qk+r$, with $1 \le r \le k$. Then
\[ {\S}^{\star}\big(a,ha+d,ha+2d,\ldots,ha+kd\big) = \big\{ha\left\lf \ts\frac{x-1}{k} \right\rf+(h-1)a+dx: a-r \le x \le a-1 \big\}. \]
\end{theorem}

\begin{proof}
Fix $k \ge 1$, and let $A=\{a,ha+d,ha+2d,\ldots,ha+kd\}$. By equation $(\ref{S*})$ and Lemma \ref{minclass},
\[ {\S}^{\star}(A) \subseteq \left\{ ha\left\lf \ts\frac{x-1}{k} \right\rf + (h-1)a + dx: 1 \le x \le a-1 \right\}. \]
By equation $(\ref{S*elt})$, $ha\lf\frac{x-1}{k}\rf+(h-1)a+dx \in {\S}^{\star}$ if and only if for each $y$ with $1 \le y \le a-1$,
\begin{equation}\label{S*ineq1}
ha \lf \ts\frac{(x+y)\bmod{a}-1}{k} \rf + d\big((x+y)\bmod{a}\big) \le ha \left( \lf\ts\frac{x-1}{k}\rf+\lf\ts\frac{y-1}{k}\rf \right) + (h-1)a + d(x+y).
\end{equation}

Suppose $k \le a-1$, and write $a-1=qk+r$ with $1 \le r \le k$. Then unless $x=a-1$, $x+y \le a-1$ for at least one $y$. For such a $y$, equation $(\ref{S*ineq1})$ reduces to proving the inequality
\[ \lf \ts\frac{x+y-1}{k} \rf \le \lf \ts\frac{x-1}{k} \rf + \lf \ts\frac{y-1}{k} \rf. \]
If we now write $x=q_1k+r_1$, $y=q_2k+r_2$ with $1 \le r_1,r_2 \le k$, the reduced inequality above fails to hold precisely when $r_1+r_2 \ge k+1$. Given $x$, and hence $r_1$, the choice $y=r_2=k+1-r_1$ will thus ensure that equation $(\ref{S*ineq1})$ fails to hold provided $x+y \le a-1$. However, such a choice for $y$ is not possible precisely when $x \ge qk+1=a-r$, so that equation $(\ref{S*ineq1})$ always holds in only these cases. Finally, it is easy to verify that equation $(\ref{S*ineq1})$ holds if $x=a-1$. This shows ${\S}^{\star}=\big\{ha\lf\frac{x-1}{k}\rf+(h-1)a+dx: a-r \le x \le a-1\big\}$ if $1 \le k \le a-1$.

If $k \ge a$, equation $(\ref{S*ineq1})$ reduces to $d\big((x+y)\bmod{a}\big) \le d(x+y)+(h-1)a$. Thus ${\S}^{\star}(A)=\big\{(h-1)a+dx: 1 \le x \le a-1\big\}$, as claimed, since $r=a-1$ and $\lf\frac{x-1}{k}\rf=0$ in this case. This completes the proof.
\end{proof}

\begin{obs}
The case when $A$ consists of integers in arithmetic progression is the special case $h=1$ in Theorem \ref{S*formula}. Moreover, the result in the first part of Theorem \ref{gnformula} follows directly from Theorem \ref{S*formula}.
\end{obs}

\section{Acknowledgments}

The author wishes to thank the anonymous referee for his comments. 

\begin{thebibliography}{99}

\bibitem{Bat58}
P. T. Bateman, Remark on a recent note on linear forms, {\it Amer. Math. Monthly}, {\bf 65} (1958), 517--518.

\bibitem{BS62}
A. Brauer and J. E. Shockley, On a problem of Frobenius, {\it J. Reine Angew. Math.}, {\bf 211} (1962), 215--220.

\bibitem{Gra73}
D. D. Grant, On linear forms whose coefficients are in arithmetic progression, {\it Israel J. Math.}, {\bf 15} (1973), 204--209.

\bibitem{Joh60}
S. M. Johnson, A linear diophantine problem, {\it Canad. J. Math.}, {\bf 12} (1960), 390--398.

\bibitem{Ram05}
J. L. Ram\'{i}rez Alfons\'{i}n, {\it The Diophantine Frobenius Problem}, Oxford Lecture Series in Mathematics and its Applications, No. 30, Oxford University Press, 2005.

\bibitem{Rob56}
J. B. Roberts, Note on linear forms, {\it Proc. Amer. Math. Soc.}, {\bf 7} (1956), 465--469.

\bibitem{Rod78}
{\O}. J. R{\o}dseth, On a linear diophantine problem of Frobenius, {\it J. Reine Angew. Math.}, {\bf 301} (1978), 171--178.

\bibitem{Sel77}
E. S. Selmer, On the linear diophantine problem of Frobenius, {\it J. Reine Angew. Math.}, {\bf 293/294} (1977), 1--17.

\bibitem{Syl84}
J. J. Sylvester, Problem 7382, in W. J. C. Miller, ed., \emph{Mathematical
Questions, with their Solutions, from the \emph{``Educational Times''}}, {\bf 41} (1884), p.\ 21.  Solution by W. J. Curran Sharp.  Available
at \url{http://tinyurl.com/oe344rs}.

\bibitem{Tri94}
A. Tripathi, The coin exchange problem for arithmetic progressions, {\it Amer. Math. Monthly}, {\bf 101} (1994), 779--781.

\bibitem{Tri03}
A. Tripathi, On a variation of the coin exchange problem for arithmetic progressions, {\it Integers}, {\bf 3} (2003), Article A01, 1--5.

\bibitem{Tri06}
A. Tripathi, On a linear diophantine problem of Frobenius, {\it Integers}, {\bf 6} (2006), Article A14, 1--6.

\end{thebibliography}

\end{document}


\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11D04.

\noindent \emph{Keywords: } 
Frobenius problem, modified arithmetic progression.

\bigskip
\hrule
\bigskip

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

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