\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) & = & \ds\max_{\bf C \in \C}\: {\m}_{\bf C} - a \\ & = & \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] & = & 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) & = & \frac{1}{a}\ds\sum_{\bf C \in \C}\: {\m}_{\bf C} - \ts\frac{1}{2}(a-1) \\ & = & \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] & = & 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] & = & h \big( k(1+2+\cdots+q) + (q+1)(r+1) \big) \\[10pt] & & + \frac{1}{2}(a-1)(d-1) \\[10pt] & = & \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} .