\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} \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 On the Partitions of a Number\\ \vskip .13in into Arithmetic Progressions } \vskip 1cm \large Augustine O. Munagi and Temba Shonhiwa\\ The John Knopfmacher Centre for Applicable Analysis and Number Theory\\ School of Mathematics\\ University of the Witwatersrand \\ Private Bag 3, Wits 2050\\ South Africa\\ \href{Augustine.Munagi@wits.ac.za}{\tt Augustine.Munagi@wits.ac.za} \\ \href{Temba.Shonhiwa@maths.wits.ac.za}{\tt Temba.Shonhiwa@maths.wits.ac.za} \\ \end{center} \vskip .2in \begin{abstract} The paper investigates the enumeration of the set $\textrm{AP}(n)$ of partitions of a positive integer $n$ in which the nondecreasing sequence of parts form an arithmetic progression. We establish formulas for such partitions, and characterize a class of integers $n$ with the property that the length of every member of $\textrm{AP}(n)$ divides $n$. We prove that the number of such integers is small. \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]{Example} \newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}} \newcommand{\noi}{\noindent} \newcommand{\dsp}{\displaystyle} \def\dis{\displaystyle} \def\scr{\scriptstyle} \section{Introduction}\label{sec1} A partition of a positive integer $n$ is a nondecreasing sequence of positive integers whose sum is $n$. The summands are called parts of the partition. We will denote the partition $n_1,n_2,\dots,n_k$ as the $k$-tuple ($n_1,n_2,\dots,n_k$). We consider the problem of enumerating the set $\textrm{AP}(n)$ of partitions of $n$ in which the nondecreasing sequence of parts form an arithmetic progression (AP). Our investigation was in part motivated by sequence \seqnum{A049988} in Sloane's table \cite{S}, that is, the number of arithmetic progressions of positive, integers, nondecreasing with sum $n$. Cook and Sharpe \cite{CS} obtained necessary and sufficient conditions for a positive integer to possess a partition into arithmetic progressions with a prescribed common difference. Nyblom and Evans \cite{NE} undertook the enumeration problem and found the following representation for the number $\dis p_{d}(n)$ of partitions of $n$ with common difference $d$. \[p_{d}(n)= \left\{\begin{array}{ll} \tau_1(n)-2-f(n), & \textrm{if $n=d\frac{m(m+1)}{2}$ for some $m>1$};\\ \tau_1(n)-1-f(n), & \textrm{otherwise}, \end{array} \right.\] where $f(n)=|A_n|$ with $A_n=\{c: c|n, c\; \textrm{odd,}\; c^20$, and $\textrm{AP}(n,2)\ne \emptyset,\; n>1$, since $(n)\in \textrm{AP}(n,1)$ and $(1,n-1)\in \textrm{AP}(n,2)$ respectively. The set $\textrm{DP}(n)$ of partitions using a single integer (divisor of $n$) forms a distinguished subset of $\textrm{AP}(n)$. The cardinality $\textrm{dp}(n)=|\textrm{DP}(n)|$ is given by the number $f(n,2)$ of ordered factorizations of $n$ into two factors plus 2 (counting the partitions $(1,1,\dots,1)$ and $(n)$): each factorization $n=rs,\; r,s>0,$ gives the $s$-tuple $(r,r,\dots,r)\in \textrm{DP}(n)$, and $n=sr$ gives the $r$-tuple $(s,s,\dots,s)\in \textrm{DP}(n)$. Since the first factor runs over the divisors of $n$, we have \begin{equation} {\rm dp}(n)=f(n,2)+2=\tau(n), \end{equation} where $\tau(n)$ is the number of positive integral divisors of $n$. If $p$ is an odd prime then each $\pi \in \textrm{AP}(p)$ can have at most two distinct parts since the sum of a $k$-term AP with a positive common difference is composite if $k\ge 3$. Since $\textrm{dp}(n)=2$ for prime $p$, observe that \[ |{\rm AP}(p)\setminus {\rm DP}(p)|=\left|\left\{(i,p-i)\mid 1\leq i\leq \frac{p-1}{2}\right\}\right|=\frac{p-1}{2}. \] Consequently $\textrm{ap}(p)=2+(p-1)/2=(p+3)/2$, from which we obtain the following result on the enumeration of $\textrm{AP}(n)$ for prime $n$. \begin{proposition}\label{prop1} % 1 ${\rm ap}(2)=2$, and if $p$ is an odd prime, then $\dsp {\rm ap}(p)=\frac{p+3}{2}.$ \end{proposition} Proposition \ref{prop1} has the following extension. Let $\textrm{AP}_t(n)$ denote the subset of $\textrm{AP}(n)$ containing partitions with at most $t$ distinct parts and $\textrm{ap}_t(n)=|\textrm{AP}_t(n)|$. Then $\textrm{ap}_2(n)=\tau(n)+\frac{n}{2} -1$ if $n$ is even, and $\textrm{ap}_2(n)=\tau(n)+\frac{(n-1)}{2}$ if $n$ is odd. Hence we have the following result. \begin{proposition} % 2 If $n$ is a positive integer, then $\dsp {\rm ap}_2(n)=\tau(n) + \left\lfloor \frac{n-1}{2}\right\rfloor, $ where $\dsp \left\lfloor x\right\rfloor$ is the greatest integer $\le x$. \end{proposition} The next-step result follows from the summation of the parts of a partition in $\textrm{AP}(n)$. \begin{equation} a+(a+d)+\cdots +(a+(k-1)d)=ka+ {k\choose 2} d=n,\quad d\ge 0, \end{equation} for some integers $a,\, d,\, k,\, a\ge 1,\, d\ge 0,\, 1\le k\le n.$ Then $k=3$ implies $3a+3d=n$. Hence $\textrm{ap}(n,3)>0$ if and only if $n$ is a multiple of 3. If $3|n$, the solution set of $a+d=n/3$ is clearly $ \{(a,d)=(r,(n-3r)/3)\mid 1\le r\le n/3\}$. Thus $\textrm{ap}_3(n)=\textrm{ap}_2(n)+n/3$. \begin{proposition} % 3 If $n$ is a positive integer such that $3|n$, then $\dsp {\rm ap}_3(n)=\tau(n) + \left\lfloor \frac{(5n-3)}{6}\right\rfloor.$ \end{proposition} The formula for $\textrm{ap}_t(n),\, t\ge 4$, is uneconomical, $(2,5,8,11)\in \textrm{AP}(26)$ but $4 \nmid 26$. Let $\textrm{Div}(n)$ denote the set of divisors of $n$. Since $k\in \textrm{Div}(n)\text{ implies } \textrm{ap}(n,k)>0$, we define the set $\textrm{APDiv}(n)=\{k \mid \textrm{ap}(n,k)>0\}$. Then $\textrm{Div}(n)\subseteq \textrm{APDiv}(n)$ in general. In Section \ref{sec2}, we derive the general formula for $\textrm{ap}(n,k)$. This will make it possible, in Section \ref{sec3}, to obtain more inclusive formulas in the spirit of those stated above, bearing in mind $\textrm{Div}(n)\subseteq \textrm{APDiv}(n)$. In particular, we characterize the class of numbers $n$ for which $\textrm{Div}(n)=\textrm{APDiv}(n)$, and show that such numbers are few. \section{The formula for $\textrm{ap}(n,k)$}\label{sec2} % 2 We present the main theorem of this section. \begin{theorem} \begin{enumerate} \item Let $n$ be a positive integer and $k>0$ an even number such that $\textrm{ap}(n,k)>0$. Then \begin{equation} {\rm ap}(n,k)= \left \lfloor \frac{n+k(k-2)}{ k(k-1)} \right \rfloor,\quad \text{ if } k|n \text{ and } \end{equation} \begin{equation} {\rm ap}(n,k)=\left \lfloor \frac{2n+k(k-3)}{2k(k-1)}\right\rfloor,\quad \text{ if } k \nmid n. \end{equation} \item Let $n$ be a positve integer and $k$ an odd number such that ${\rm ap}(n,k)>0,\; k>1$. Then \begin{equation} {\rm ap}(n,k)=\left\lfloor \frac{2n+k(k-3)}{k(k-1)}\right\rfloor. \end{equation} \end{enumerate} \end{theorem} \medskip \begin{proof} The proof makes use of the following result [2]. \noi {\it The linear Diophantine equation $ax +by=c$ has a solution if and only if $ g|c$, where $g=\gcd(a,b).$ If $(x_{0},y_{0})$ is any particular solution of this equation, then all other solutions are given by, $$x=x_{0}+\left(\frac{b}{g}\right)t, \, y=y_{0}-\left(\frac{a}{g}\right)t$$ where $t$ is an arbitrary integer. } \end{proof} \medskip In view of equation $(2)$, the enumerative function $\textrm{ap}(n,k)$ is given by \[ {\rm ap}(n,k)=\sum_{\scriptstyle ka+\ell d=n \atop \scriptstyle a\ge 1,\, d\ge 0}1, \] where $\dsp \ell=k\frac{(k-1)}{2}$. However, $ka+ \ell d=n$ has a solution if and only if $\gcd(k,\ell)|n$. For the case $k$ odd, it follows that $\gcd(k,\ell)=k$ leading to a solution if and only if $k|n$, that is, $n$ is a multiple of $k$. In which case one particular solution is $d_{0}=0 \text{ and } a_{0}=\frac{n}{k}$, an integer. And hence, the other solutions are given by \[ a=\frac{n}{k}+\frac{\ell}{\gcd(k,\ell)}t \geq 1 \text{ and } d=-\frac{k}{\gcd(k,\ell)}t \geq 0, \] where $t$ is an integer. Thus, \begin{eqnarray*} {\rm ap}(n,k) &=& \sum_{\scriptstyle a=\frac{n}{k}+\frac{\ell}{\gcd(k,\ell)}\,t \ge 1 \atop \scriptstyle d=-\frac{k}{\gcd(k,\ell)}\,t \ge 0}1 \\ &=& \sum_{(1-\frac{n}{k})\frac{\gcd(k,\ell)}{\ell}\leq t \leq 0}1 \;=\; \left\lfloor \frac{2(n-k)}{k(k-1)}\right\rfloor + 1, \end{eqnarray*} a result equivalent to formula (5). Next we consider the case when $k$ is even and note that \[ \gcd(k,\ell)= \gcd\left(2\frac{k}{2}, \frac{k}{2}(k-1)\right)=\frac{k}{2}, \] that is, $ka+\ell d=n$ has a solution if and only if $\frac{k}{2}\mid n$, which implies $n=s\frac{k}{2}$, for some positive integer $s$. Clearly, for $s$ even, the previous argument goes through save for a minor adjustment, leading to the result, \[ {\rm ap}(n,k)=\left\lfloor \frac{(n-k)}{k(k-1)}\right\rfloor +1, \] where $n$ is a multiple of $k$, a result equivalent to formula (3). On the other hand, if $s$ is odd, then one valid solution is \[ d_{0}=1\text{ which implies } a_{0}=\frac{(s\frac{k}{2}-\ell)}{k}=\frac{\frac k2(s-(k-1))}{k}, \text{ which is an integer when } s \text{ is odd }. \] The condition $a\geq 1$ implies the condition $n\geq \frac{k}{2}(k+1)$. Therefore, \begin{eqnarray*} {\rm ap}(n,k) &=& \sum_{\scriptstyle a=\frac{n-\ell}{k}+\frac{\ell}{\gcd(k,\ell)}t\ge 1 \atop \scriptstyle d=1-\frac{k}{\gcd(k,\ell)}t\ge 0}1 \\ &=& \sum_{\frac{\gcd(k,\ell)}{\ell} \left(1-\frac{(n-\ell)}{k}\right)\leq t\leq \frac{\gcd(k,\ell)}{k}}1. \end{eqnarray*} Since $\gcd(k,\ell)=k/2$, this gives $t\leq \frac 12$ and hence, \[ {\rm ap}(n,k)=\left\lfloor \frac{(2n-k(k+1))}{2k(k-1)}\right\rfloor + 1, \] where $n=s\frac{k}{2} \geq \frac{k}{2}(k+1)$, a result equivalent to formula (4). This exhausts all possible outcomes. \section{The formula for ${\rm ap}(n)$}\label{sec3} % 3 Using the results of Section \ref{sec2}, we can write the sum of $\textrm{ap}(n,k)$ over all divisors $k$ of $n$, denoted $\textrm{divap}(n)$. Thus, \begin{theorem}\label{main} \[ {\rm divap}(n)=1+\sum_{k|n,\ k>1 \text{ \rm is even }}\left\lfloor \frac{n+k(k-2)}{k(k-1)} \right\rfloor +\sum_{k|n,\ k>1 \text{ \rm is odd }}\left\lfloor \frac{2n+k(k-3)}{k(k-1)}\right\rfloor. \] Alternatively, \[ {\rm divap}(n)=\tau(n)+n - \sigma(n) + \sum_{\scriptstyle k|n \atop \scriptstyle k>1,\ k \text{ \rm even}} \left\lfloor\frac{n-1}{k-1}\right\rfloor + \sum_{\scriptstyle k|n \atop \scriptstyle k>1,\ k \text{ \rm odd}}\left\lfloor \frac{n+k(n-2)}{k(k-1)}\right\rfloor. \] \end{theorem} \medskip \begin{proof} \begin{eqnarray*} {\rm divap}(n) &=& \sum_{k|n}{\rm AP}(n,k)= \sum_{k|n,\ k \text{ odd}}{\rm AP}(n,k)+\sum_{k|n,\ k \text{ even}}{\rm AP}(n,k) \\[.1in] &=& 1+\sum_{ {\scriptstyle k|n} \atop \scriptstyle k>1,\ k \text{ \rm odd}} \left(\left\lfloor\frac{2(n-k)}{k(k-1)}\right\rfloor +1\right) + \sum_{\scriptstyle k|n \atop \scriptstyle k>1,\ k \text{ \rm even}} \left(\left\lfloor\frac{n-k}{k(k-1)}\right\rfloor+1\right) \\[.1in] &=&1+\sum_{\scriptstyle k|n \atop \scriptstyle k>1,\ k \text{ \rm odd}} 1+ \sum_{\scriptstyle k|n \atop \scriptstyle k>1,\ k \text{ \rm even}} 1 + \sum_{\scriptstyle k|n \atop \scriptstyle k>1,\ k \text{ \rm odd}} \left\lfloor\frac{2(n-k)}{k(k-1)}\right\rfloor + \sum_{\scriptstyle k|n \atop \scriptstyle k>1,\ k \text{ \rm even}} \left\lfloor\frac{n-k}{k(k-1)}\right\rfloor \\[.1in] &=& \tau(n)- \left(\sum_{\scriptstyle k|n \atop \scriptstyle k1,\ k \text{ \rm odd}} \left\lfloor\frac{2(n-1)}{k-1}-\frac{n}{k}\right\rfloor+ \sum_{\scriptstyle k|n \atop \scriptstyle k>1,\ k \text{ \rm even}} \left\lfloor \frac{n-1}{k-1}\right\rfloor \\[.1in] &=& \tau(n)-\big(\sigma(n)-n\big) + \sum_{\scriptstyle k|n \atop \scriptstyle k>1,\ k \text{ \rm even}} \left\lfloor\frac{n-1}{k-1}\right\rfloor + \sum_{\scriptstyle k|n \atop \scriptstyle k>1,\ k \text{ \rm odd}} \left\lfloor \frac{n+k(n-2)}{k(k-1)}\right\rfloor. \end{eqnarray*} \end{proof} \medskip Note that since $\dsp n=\frac{k}{2}\big(2a+(k-1)d\big)$ by (2), it follows that if $k$ is odd and $\textrm{ap}(n,k)> 0$, then $k|n$, and if $k\nmid n$ and $\textrm{ap}(n,k)> 0$, then $k$ is even and $n\equiv 0$ $\left(\mbox{mod }\frac{k}{2}\right)$. Hence the set-difference $\textrm{APDiv}(n)\setminus \textrm{Div}(n)$ is given by $$ \textrm{Ek}(n)=\textrm{APDiv}(n) \setminus \textrm{Div}(n)= \left\{k=2v \mid k\nmid n, v|n, n\ge \binom{k+1}{2}\right\}.$$ That is, \begin{equation}\label{setcrit} {\rm Ek}(n)=\big\{2v\in 2^{\alpha+1}{\rm Div}(m)\mid n\ge v(2v+1)\big\}, \end{equation} where $m$ is the unique odd number satisfying $n=2^{\alpha} m,\alpha\ge 0$, and $rS=\{rs \mid s\in S\}$. The importance of $\textrm{Ek}(n)$ lies in the following statement. \begin{equation}\label{crit} {\rm ap}(n)={\rm divap}(n)\ \text{ if and only if } \ {\rm Ek}(n)=\emptyset. \end{equation} In the case $\textrm{Ek}(n)\ne \emptyset$ we have \begin{equation}\label{genform} {\rm ap}(n)={\rm divap}(n)+{\rm extap}(n), \text{ where},\quad {\rm extap}(n)=\sum_{k\in {\rm Ek}(n)}\left\lfloor \frac{2n+k(k-3)}{2k(k-1)}\right\rfloor. \end{equation} Since $1\in \textrm{Div}(m)$, we obtain \begin{equation}\label{crit2} {\rm Ek}(n)=\emptyset \ \text{ if and only if }\ m<2^{\alpha+1}+1. \end{equation} In particular $\textrm{Ek}(2^{\alpha})=\emptyset,\,\alpha\ge 0$. Hence the next result follows from Theorem \ref{main} and (\ref{crit}). \begin{proposition}\label{prop6} % 6 If $\alpha$ is a nonnegative integer, then $$ {\rm ap}(2^{\alpha})=1+\sum_{j=1}^{\alpha}\left\lfloor \frac{2^{\alpha -j}+2^j-2}{2^j-1} \right\rfloor =1+\alpha +\sum_{j=1}^{\alpha}\left\lfloor \frac{2^{\alpha -j}-1}{2^j-1} \right\rfloor.$$ \end{proposition} Proposition \ref{prop6} is a special case of the next result. \begin{theorem}\label{thm7} The following assertions are equivalent for any even integer $n$. \begin{itemize} \item[(i)] ${\rm ap}(n)={\rm divap}(n)$. \item[(ii)] $n$ can be expressed in the form $n=2^j(r+2^{j-1}),\, r=0,1,\dots,3 \cdot 2^{j-1}$, where $j$ is a positive integer. \end{itemize} \end{theorem} \begin{proof} Let $n=2^j(r+2^{j-1})=2^{\alpha}m,\,\alpha\ge j$, where $m$ is odd.\\ $m=2^{j-\alpha}(r+2^{j-1})\le 2^{j-\alpha}(3 \cdot 2^{j-1}+2^{j-1})=2^{2j-\alpha+1}<2^{\alpha+1}+1$. So ${\rm Ek}(n)= \emptyset$ by (\ref{crit2}). Hence $(ii)\Rightarrow (i)$. Conversely, notice that $3 \cdot 2^{j-1}\textrm{apdiv}(n)$, a contradiction of $(i)$. \end{proof} \bigskip \noindent{\bf Remarks} \begin{itemize} \item[(i) ] The special even numbers of Theorem \ref{thm7} form an AP from $2^{2j-1}$ to $2^{2j+1}$ for each $j$ (with common difference $2^j$), say $R(j)$. For example, $R(1)=(2,4,6,8)$ and $R(2)=(8,12,16,20,24,28,32)$. \item[(ii) ] Theorem \ref{thm7} implies Proposition \ref{prop6} since $2^{2j-1},\,2^{2j}\in R(j)$, when $r=0,\, 2^{j-1}$. \item[(iii) ] For fixed $j$, there are integers $n=2^j(r+2^{j-1})$ with $r\notin \{0,1,\ldots,3 \cdot 2^{j-1}\}$ which satisfy Theorem \ref{thm7}(i). However, this is not a violation of the theorem since $n\in R(j)$ for some (legal) $j$ and $r$. For example if $j=1$, then $n=12$ corresponds to $r=5>3$. So $12\notin R(1)$ even though ${\rm ap}(12)={\rm apdiv}(12)$. But note that $12\in R(2)$. This phenomenon is explained by removing the restriction on $r$ and observing that $i0$ for each $n>1$, including prime $n$. So, for odd numbers, we can skip the $1\in \textrm{Div}(m)$ and use the least prime factor of $n$, to obtain the adjusted version of (\ref{crit2}). Let $n>1$ be an odd positive integer, and let $p$ denote the least prime divisor of $n$. \begin{equation}\label{crit3} {\rm Ek}(n)=\{2\}\ \text{ if and only if }\ \frac{n}{p}<2p+1. \end{equation} The next theorem characterizes odd numbers $n$ satisfying (\ref{crit3}), i.e., $\textrm{ap}(n)=\textrm{divap}(n)+ \textrm{ap}(n,2)$. \begin{theorem}\label{oddthm} The following assertions are equivalent for any odd integer $n>1$. \begin{itemize} \item[(i)] ${\rm ap}(n)={\rm divap}(n)+ \frac{(n-1)}{2}$. \item[(ii)] $n$ is prime, or $n=p_1p_2$, where $p_1,p_2$ are primes such that $p_2< 2p_1+1$. \end{itemize} \end{theorem} \begin{proof} Clearly (i) is true if $n$ is prime, since there are $\frac{(n-1)}{2}$ partitions of $n$ into two parts (see Proposition \ref{prop1}). The proof follows from (\ref{crit3}) and the observation that $n=p_1p_2\cdots p_r,\,r>2$, implies $\frac{n}{p_1} \ge 2p_1+1$, which implies that $\textrm{Ek}(n)$ properly contains $\{2\}$. \end{proof} \begin{corollary}\label{cor9} If $p$ is an odd prime, then $${\rm ap}(p^2)=\frac{p^2+9}{2}.$$ \end{corollary} Corollary \ref{cor9} is also a corollary of the next theorem. \begin{theorem}\label{thm10} If $p$ is an odd prime and $\alpha$ is a positive integer, then $$ {\rm ap}(p^{\alpha})=1+\sum_{i=1}^{\alpha}\left\lfloor \frac{2p^{\alpha -i}+p^i-3}{p^i-1} \right\rfloor +\sum_{i=0}^{\left\lfloor \frac{\alpha-1}{2}\right\rfloor}\left\lfloor \frac{p^{\alpha -i}+2p^i-3}{2(2p^i-1)} \right\rfloor.$$ \end{theorem} \begin{proof} $ \textrm{Div}(p^{\alpha})=\{1,p,\dots,p^{\alpha}\}$. So for each $i,\, 0\le i\le \alpha$, we have $p^{\alpha-i}\ge 2p^i+1$ if and only if $\alpha>2i$ if and only if $0\le i\le \left\lfloor (\alpha-1)/2 \right\rfloor$. Thus $\textrm{Ek}(p^{\alpha})= \big\{2p^i\mid 0\le i\le \left\lfloor (\alpha-1)/2 \right\rfloor\big\}$. Substituting for $p^i$ in (\ref{crit}) and (\ref{genform}), and simplifying the following summations gives the theorem. $${\rm ap}(p^{\alpha})=1+\sum_{i=1}^{\alpha}\textrm{divap}(p^{\alpha},p^i)+ \sum_{i=0}^{\left\lfloor \frac{\alpha-1}{2}\right\rfloor}\textrm{extap}(p^{\alpha},2p^i).$$ \end{proof} \medskip Given an odd prime $p$ let $\alpha$ and $c$ be nonnegative integers, $0\le c\le \alpha$. We claim that \begin{equation}\label{poly} \left\lfloor \frac{2p^{\alpha -c}+p^c-3}{p^c-1} \right\rfloor = 1+ \frac{2p^r(p^{(q-1)c}-1)}{p^c-1},\quad \alpha=qc+r,\, 0\le r0)=\alpha -2,\, \alpha>1$. The polynomials $\textrm{apdiv}(p^{\alpha})$ are given below for $\alpha=2,3,\ldots,9$. \[{\rm divap}(p^2)=5\] \[{\rm divap}(p^3)=2p+6\] \[{\rm divap}(p^4)=2p^2+2p+9\] \[{\rm divap}(p^5)=2p^3+2p^2+4p+8\] \[{\rm divap}(p^6)=2p^4+2p^3+4p^2+2p+13\] \[{\rm divap}(p^7)=2p^5+2p^4+4p^3+2p^2+6p+10\] \[{\rm divap}(p^8)=2p^6+2p^5+4p^4+2p^3+6p^2+2p+15\] \[{\rm divap}(p^9)=2p^7+2p^6+4p^5+2p^4+6p^3+2p^2+6p+14.\] On the other hand, given an odd prime $p$, the set of numbers $n=pp_2,\, p_2\ge p$ ($p_2$ a prime) which satisfy Theorem \ref{oddthm} is nicely bounded: $p^2 \le n < 2p^2$. So let $S(p)$ denote the set of all numbers $n$ between $ p^2$ and $ 2p^2$ inclusive which satisfy Theorem \ref{oddthm}. We deduce that \begin{equation} |S(p)|=\big|\big\{p_2\, \textrm{prime} \mid p \le p_2 < 2p\big\}\big|+ \big|\big\{p_2\, \textrm{prime}\mid p^2 \le p_2 < 2p^2\big\}\big|. \end{equation} In terms of the sequence $a(n)$ = number of primes between $n$ and $2n$ inclusive [4, A035250], a concise expression is $|S(p)|=a(p)+a(p^2)$. We examine the size of the set of numbers which satisfy the ``closure'' relation $\textrm{ap}(n) = \textrm{divap}(n)$. By Theorem \ref{thm7} all such numbers ($>1$) are even. For a fixed positive integer $j$ define $\textrm{AE}(j)=\big\{2c\mid 2^{2j-2}\le c\le 2^{2j}\big\}$. Recalling the sets $R(j)$ defined in the remarks following Theorem \ref{thm7}, we have $$ |R(j)|=3 \cdot 2^{j-1}+1,\quad \textrm{and}\quad |\textrm{AE}(j)-R(j)|= 3 \cdot 2^{j-1}(2^{j-1}-1).$$ Note that $\textrm{AE}(j)\setminus R(j)$ is the set of even numbers $n$ within the range of elements of $R(j)$ which satisfy $\textrm{ap}(n) > \textrm{divap}(n)$. It follows that, for sufficiently large j, $$ \frac{|R(j)|}{|\rm{AE}(j)|}\le \frac{1}{2^{j-1}}\longrightarrow 0,\quad \textrm{and}\quad \frac{|\rm{AE}(j) \setminus R(j)|}{|\rm{AE}(j)|}\le \frac{2^{j-1}-1}{2^{j-1}} \longrightarrow 1.$$ We conclude that practically all even numbers satisfy the strict inequality ${\rm ap}(n) > {\rm divap}(n)$. Thus more readily so for all positive integers. \section{Conclusion}\label{sec4} We close with some remarks on the set $\textrm {Ek}(n)$. It follows from (\ref{setcrit}) that if $k\in \textrm{Ek}(n)$, then $\dsp n=M(\frac{k}{2})$ for some odd integer $M$. Writing $\dsp n=2^{\alpha}m$ as previously, and $\dsp k=2^{\alpha+1}m_i$ ($m_i$ odd), we have $\dsp n=M\frac{k}{2}=M(2^{\alpha}m_i)=Mm_i \cdot 2^{\alpha},\, \textrm{where}\quad Mm_i=m,\, m_i\ge 1.$ Thus each element of $\textrm{Ek}(n)$ corresponds to a decomposition of $m$ into two factors. This gives $\dsp |\textrm{Ek}(n)|\le \frac{\tau(m)}{2}$. \noi That is, \[ |\textrm{Ek}(n)|\le \left\lfloor \frac{\tau(m)}{2}\right\rfloor,\quad \textrm{where}\quad m=\frac{n}{2^{\alpha}}\,\, \textrm{is odd},\,\alpha\ge 0.\] The case of prime powers (see Theorem \ref{thm10}) shows that this upper bound is sharp.\\ The determination of the exact value of $|\textrm{Ek}(n)|$ remains an open problem. \section*{Acknowledgment} We wish to thank Jeffrey Shallit for bringing the Nyblom-Evans paper to our attention. \begin{thebibliography}{99} \bibitem {AN} G. E. Andrews,{\it The Theory of Partitions}, Encyclopedia of Mathematics and its Applications, Vol.\ 2, Addison-Wesley, 1976. \bibitem{Ap} T. M. Apostol, {\it Introduction to Analytic Number Theory}, Springer-Verlag, New York Inc., 1976. \bibitem{CS}R. Cook and D. Sharp, Sums of arithmetic progressions, \emph{Fib. Quart.} {\bf 33} (1995), 218--221. \bibitem{GKP} R. L. Graham, D. E. Knuth and O. Patashnik, {\it Concrete Mathematics}, Second Edition, Addison-Wesley, 1994. \bibitem{NE} M. A. Nyblom and C. Evans, On the enumeration of partitions with summands in arithmetic progression, \emph{Australas. J. Combin.} {\bf 28} (2003), 149--159. \bibitem{S} N. J. A. Sloane, {\it The On-Line Encyclopedia of Integer Sequences,} published electronically at \href{http://www.research.att.com/~njas/sequences/}{\tt http://www.research.att.com/$\sim$njas/sequences/}. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 11P81; Secondary 05A15, 05A17. \medskip \noindent {\it Keywords}: partition, arithmetic progression, divisor function, Diophantine equation. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A004119}, \seqnum{A035250}, and \seqnum{A049988}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received October 8 2007; revised version received October 10 2007; December 5 2008. Published in {\it Journal of Integer Sequences}, December 13 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}