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

\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), &amp; \textrm{if $n=d\frac{m(m+1)}{2}$ for some $m&gt;1$};\\ 
\tau_1(n)-1-f(n), &amp; \textrm{otherwise},
\end{array} \right.\]
where $f(n)=|A_n|$ with $A_n=\{c: c|n, c\; \textrm{odd,}\; c^2&lt;d(2n-c),\, 2n&lt;dc(c-1)\}$,
and $\tau_1(n)$ is the number of odd positive divisors of $n$. 
The authors also state a closed formula for $p_2(n)$.

In what follows we count partitions directly, and mostly according to
the length $k$ of an AP, an approach which reduces our domain to the
natural subclass of $k$-partitions of $n$. This makes it possible to
obtain simpler results with certain new consequences.

Let $\textrm{AP}(n,k)=\{\pi\mid \pi\in \textrm{AP}(n) \text{ and } \pi
\text{ has } k  \text{ parts }\}$, and  let
$\textrm{ap}(n)=|\textrm{AP}(n)|$,
$\textrm{ap}(n,k)=|\textrm{AP}(n,k)|$ denote the cardinalities of the
respective sets.

Note that $\textrm{AP}(n,1)\ne \emptyset,\; n&gt;0$, and
$\textrm{AP}(n,2)\ne \emptyset,\; n&gt;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&gt;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)&gt;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)&gt;0$, we  
define the set $\textrm{APDiv}(n)=\{k \mid  \textrm{ap}(n,k)&gt;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&gt;0$ an even number such that 
$\textrm{ap}(n,k)&gt;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)&gt;0,\; k&gt;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) &amp;=&amp; \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
\\
&amp;=&amp; \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) &amp;=&amp; \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
\\
&amp;=&amp; \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&gt;1 \text{ \rm is even }}\left\lfloor \frac{n+k(k-2)}{k(k-1)} \right\rfloor
+\sum_{k|n,\ k&gt;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&gt;1,\ k \text{ \rm even}}
\left\lfloor\frac{n-1}{k-1}\right\rfloor +
\sum_{\scriptstyle k|n  \atop \scriptstyle k&gt;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) &amp;=&amp; \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]
&amp;=&amp;  1+\sum_{ {\scriptstyle k|n}  \atop \scriptstyle k&gt;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&gt;1,\ k \text{ \rm even}}
\left(\left\lfloor\frac{n-k}{k(k-1)}\right\rfloor+1\right) \\[.1in] 
&amp;=&amp;1+\sum_{\scriptstyle k|n  \atop \scriptstyle k&gt;1,\ k \text{ \rm odd}} 1+ 
\sum_{\scriptstyle k|n  \atop \scriptstyle k&gt;1,\ k \text{ \rm even}} 1 + 
\sum_{\scriptstyle k|n  \atop \scriptstyle k&gt;1,\ k \text{ \rm odd}} \left\lfloor\frac{2(n-k)}{k(k-1)}\right\rfloor 
+ \sum_{\scriptstyle k|n  \atop \scriptstyle k&gt;1,\ k \text{ \rm even}} \left\lfloor\frac{n-k}{k(k-1)}\right\rfloor
\\[.1in]
&amp;=&amp; \tau(n)- \left(\sum_{\scriptstyle k|n  \atop \scriptstyle k&lt;n,\ k \text{ \rm odd}} \frac{n}{k}
+ \sum_{\scriptstyle k|n  \atop \scriptstyle k&lt;n,\ k \text{ \rm even}} \frac{n}{k}\right)
\\[.1in]
&amp;&amp; +\;\sum_{\scriptstyle k|n  \atop \scriptstyle k&gt;1,\ k \text{ \rm odd}} \left\lfloor\frac{2(n-1)}{k-1}-\frac{n}{k}\right\rfloor+ 
\sum_{\scriptstyle k|n  \atop \scriptstyle k&gt;1,\ k \text{ \rm even}} \left\lfloor \frac{n-1}{k-1}\right\rfloor
\\[.1in]
&amp;=&amp; \tau(n)-\big(\sigma(n)-n\big) + \sum_{\scriptstyle k|n  \atop \scriptstyle k&gt;1,\ k \text{ \rm even}}
\left\lfloor\frac{n-1}{k-1}\right\rfloor +
\sum_{\scriptstyle k|n  \atop \scriptstyle k&gt;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)&gt; 0$, then $k|n$, and
if $k\nmid n$ and $\textrm{ap}(n,k)&gt; 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&lt;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}&lt;2^{\alpha+1}+1$.
So ${\rm Ek}(n)= \emptyset$ by (\ref{crit2}). Hence $(ii)\Rightarrow (i)$.

Conversely, notice that $3 \cdot 2^{j-1}&lt;r=3 \cdot 2^{j-1}+1$ gives 
$n=2^j(2^{j+1}+1)\equiv 2^jm$, which implies $\textrm{Ek}(n)\ne \emptyset$ or 
$\textrm{ap}(n)&gt;\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&gt;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 
$i&lt;j\Rightarrow R_{\infty}(i)\supset  R_{\infty}(j)$, where $R_{\infty}(j)=\big\{2^j(r+2^{j-1})\mid r\ge 0\big\}$.
\end{itemize}
\medskip

But if $n$ is odd, (\ref{crit2}) reduces to $n&lt;3$, owing to the fact that
$\textrm{ap}(n,2)&gt;0$ for each $n&gt;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&gt;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}&lt;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&gt;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&lt; 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&gt;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&gt;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 r&lt;c.
\end{equation}
Denote the left side of (\ref{poly}) by $u(\alpha,c)$, and write 
$h(\alpha,c)=\frac{(2p^{\alpha-c}-2p^c)}{(p^c-1)}$,
so that $ \left\lfloor h(\alpha,c) +3\right\rfloor=u(\alpha,c)$.
Then clearly, $u(2c,c)=1$ and $ \alpha&lt;2c$ implies $\alpha-c&lt;c$  which implies 
$\left\lfloor \frac{h(\alpha,c)}{2} \right\rfloor= -1$ which implies $u(\alpha,c)=1$. 
But if $2c&lt; \alpha&lt;3c$, we have 
$ \left\lfloor \frac{h(\alpha,c)}{2} \right\rfloor=p^{\alpha-2c}+\left\lfloor \frac{h(\alpha,2c)}{2} \right\rfloor$ 
which gives
$\left\lfloor \frac{h(\alpha,c)}{2} \right\rfloor=p^{\alpha-2c}-1$. 
Iterating the procedure we obtain an expression of the form
$\left\lfloor \frac{h(\alpha,c)}{2} \right\rfloor=p^{\alpha-2c}+p^{\alpha-3c}+\cdots+p^{\alpha-qc}+
\left\lfloor \frac{h(\alpha,qc)}{2} \right\rfloor$,
where $ q=\left\lfloor \frac{\alpha}{c}\right\rfloor$, giving $ \left\lfloor \frac{h(\alpha,qc)}{2}\right\rfloor=-1$.
If we compute $ \frac{\alpha}{c}$ and reverse the order of summation, we obtain
 $ \left\lfloor \frac{h(\alpha,c)}{2} \right\rfloor=p^{r}+p^{c+r}+\cdots+p^{(q-2)c+r}-1$, where 
$\alpha=qc+r$. 
Summing the finite geometric series gives the result.

Hence we obtain from Theorem \ref{thm10},   
\begin{equation} 
{\rm divap}(p^{\alpha})=
1+\alpha +\sum_{\scriptstyle c=1 \atop \scriptstyle \alpha=qc+r,\, 
0\le r&lt;c}^{\alpha} \frac{2p^r(p^{(q-1)c}-1)}{p^c-1}.
\end{equation}

This results in a sequence of polynomials in $p$ over the positive integers for $\textrm{apdiv}(p^{\alpha})$,  
$\alpha=0,1,2,\ldots$, and consequently yielding simplified forms of $\textrm{ap}(p^{\alpha})$. The degree of
$\textrm{apdiv}(p^{\alpha})$ is clearly $\max(\alpha -2c\mid c&gt;0)=\alpha -2,\, \alpha&gt;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 &lt; 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 &lt; 2p\big\}\big|+
\big|\big\{p_2\, \textrm{prime}\mid p^2 \le p_2 &lt; 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 ($&gt;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) &gt; \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) &gt; {\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}

                                                                                

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