# A note on the restricted partition function $p_{\mathcal{A}}(n,k)$

Krystian Gajdzica  Institute of Mathematics
Faculty of Mathematics and Computer Science
Jagiellonian University in Cracow<EMAIL_ADDRESS>
###### Abstract.

Let $\mathcal{A}=(a_{n})_{n\in\mathbb{N}_{+}}$ be a sequence of positive
integers. Let $p_{\mathcal{A}}(n,k)$ denote the number of multi-color
partitions of $n$ into parts in $\\{a_{1},\ldots,a_{k}\\}$. We examine several
arithmetic properties of the sequence $(p_{\mathcal{A}}(n,k)\mkern
4.0mu({\operator@font mod}\mkern 6.0mum))_{n\in\mathbb{N}}$ for an arbitrary
fixed integer $m\geqslant 2$. We investigate periodicity of the sequence and
lower and upper bounds for the density of the set
$\\{n\in\mathbb{N}:p_{\mathcal{A}}(n,k)\equiv i\mkern 4.0mu({\operator@font
mod}\mkern 6.0mum)\\}$ for a fixed positive integer $k$ and
$i\in\\{0,1,\ldots,m-1\\}$. In particular, we apply our results to the special
cases of the sequence $\mathcal{A}$. Furthermore, we present some results
related to restricted $m$-ary partitions.

###### Key words and phrases:

partitions, divisibility properties of $p_{\mathcal{A}}(n,k)$, odd density of
restricted partition function, partition function of a finite set, $m$-ary
partitions

The research of the author was supported by a grant of the National Science
Centre (NCN), Poland, no. UMO-2019/34/E/ST1/00094

##  1\. Introduction

Let $n$ be a positive integer. A partition of $n$ is a non-increasing sequence
of positive integers $n_{1},n_{2},\ldots,n_{k}$ such that

$n_{1}+\ldots+n_{k}=n.$

For example, there are seven partitions of $n=5$, namely, $(5)$, $(4,1)$,
$(3,2)$, $(3,1,1)$, $(2,2,1)$, $(2,1,1,1)$ and $(1,1,1,1,1)$. By $p(n)$ we
denote the number of partitions of $n$. As we see from the above example,
$p(5)=7.$ In addition, we assume that $p(n)=0$ for $n<0$, and $p(0)=1$,
because the empty partition is the only one in this case. In $1748$ Euler
showed that the generating function for $p(n)$ takes the form

$\displaystyle\sum_{n=0}^{\infty}p(n)x^{n}=\prod_{i=1}^{\infty}\frac{1}{1-x^{i}}.$

There is a wealth of literature related to the theory of partitions. Hence,
for more details and information see Andrews’ books [4, 3]. Nowadays, the most
examined issues in this branch are asymptotic formulas and divisibility
properties. The papers written by Ramanujan [17], Ono [16] and Atkin [6] are
just a few examples of research devoted to arithmetic properties of $p(n)$.
However, there are still many unsolved problems, for example the question
about the convergence of the limit of odd density of the function $p(n)$ to
$\frac{1}{2}$, that is to say

$\displaystyle\lim_{N\to\infty}\frac{\\#\\{n\leqslant N:p(n)\equiv 1\mkern
4.0mu({\operator@font mod}\mkern 6.0mu2)\\}}{N}=\frac{1}{2},$

remains open.

Now, let $\mathcal{A}=(a_{n})_{n\in\mathbb{N}_{+}}$ be a sequence of non-
decreasing positive integers. We can consider the multi-color partition
function which enumerates only those partitions of $n$ that parts appear at
$\mathcal{A}$. It has to be underlined that we assign the original colors for
those elements $a_{i},a_{j}$ which satisfy $a_{i}=a_{j}$ for distinct $i$ and
$j$, or simply distinguish such parts. We denote function of this kind by
$p_{\mathcal{A}}(n)$. For instance, let $\mathcal{A}$ denote the sequence of
the form $\mathcal{A}=(1,2,2,3,3,3,4,4,4,4,\ldots)$, in which an element of
size $l$ can come in $l$ distinct colours. In this case $p_{\mathcal{A}}(n)$
counts the number of so called plane partitions (see Andrews [4, Chapter 10]
or [3, Chapter 11] ). Furthermore, we may restrict the function $p(n)$ even
more by looking only on these partitions of $n$, which parts are among the
first $k$ positions of $\mathcal{A}$, in other words we introduce a function
$p_{\mathcal{A}}(n,k):=p_{\mathcal{A}_{k}}(n)$, where
$\mathcal{A}_{k}=(a_{i})_{i=1}^{k}$. The generating function for
$p_{\mathcal{A}}(n,k)$ is given by

(1.1)
$\displaystyle\sum_{n=0}^{\infty}p_{\mathcal{A}}(n,k)x^{n}=\prod_{i=1}^{k}\frac{1}{1-x^{a_{i}}}.$

Arithmetic properties of $p_{\mathcal{A}}(n,k)$ were explored especially by
Nathanson [14], Almkvist [1] and Rødseth and Sellers [20]. In this paper we
mainly investigate periodicity and both upper and lower bounds for odd density
of the function $p_{\mathcal{A}}(n,k)$ for a fixed positive integer $k$. In
particular, we generalize results obtained in [11] by Karhadkar. Additionally,
we present results of computations of some densities of the function
$p_{\mathcal{A}}(n,k)$ in special cases of the sequence $\mathcal{A}$ and
small values of $k$.

This paper is organized as follows. In Sec. 2 we introduce both concepts and
tools which are systematically used afterwards. In Sec. 3 we derive a
recurrent relation for $p_{\mathcal{A}}(n,k)$ and recall theorems related to
its periodicity. Sec. 4 concerns the upper bound for the odd density of
$p_{\mathcal{A}}(n,k)$. In Sec. 5 we examine the lower bound for the density
of the set $\\{n\in\mathbb{N}:p_{\mathcal{A}}(n,k)\not\equiv 0\mkern
4.0mu({\operator@font mod}\mkern 6.0mum)\\}$. In Sec. 6 we present some
results related to restricted $m$-ary partitions. Finally, Sec. 7 is devoted
to precise values of some (in particular odd) densities of
$p_{\mathcal{A}}(n,k)$ in special cases, and problems arising from them.

##  2\. Preliminaries

At first, we need to introduce some conventions and symbols, which are
systematically used in our further examination. The symbols
$\mathbb{N}=\\{0,1,2,\ldots\\},\mathbb{N}_{+}=\mathbb{N}\setminus\\{0\\}$,
$\mathbb{N}_{\geqslant 2}=\mathbb{N}_{+}\setminus\\{1\\}$ and $\mathbb{P}$
denote the natural numbers, positive integers, integers greater than $1$ and
prime numbers. Let $\mathcal{A}=(a_{n})_{n\in\mathbb{N}_{+}}$ be a sequence of
positive integers. Let $k\in\mathbb{N}_{+}$ and $n\in\mathbb{N}$. The function
$p_{\mathcal{A}}(n,k)$ enumerates those partitions of $n$, which can be
expressed as a sum of the $k$ first terms in $\mathcal{A}$, namely,
$a_{1},\ldots,a_{k}$. We assume that $p_{\mathcal{A}}(n,k)=0$ for $n<0$ and
$p_{\mathcal{A}}(0,k)=1$ for $k\in\mathbb{N}$. By $T$ we denote the
fundamental period of an infinite integer sequence. For a prime number $p$ and
non-negative integers $s$ and $t>0$, we write $p^{s}||t$ if and only if
$p^{s}\mid t$ and $p^{s+1}\nmid t$. Moreover, for a positive integer $i$ such
that $i=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\ldots p_{s}^{\alpha_{s}}$, where
$s\in\mathbb{N}_{+}$, $p_{j}\in\mathbb{P}$ for every $j\in\\{1,2,\ldots,s\\}$
and $p_{j_{1}}\neq p_{j_{2}}$ for all $j_{1},j_{2}\in\\{1,2,\ldots,s\\}$ with
$j_{1}\neq j_{2}$, we define the radical of $i$ as
$\text{rad}(i)=p_{1}p_{2}\ldots p_{s}$. Finally, let $S$ be a subset of
$\mathbb{N}_{+}$. We define the asymptotic (natural) density of $S$ as

$\displaystyle d(S)=\lim_{n\to\infty}\frac{\\#S\cap\\{1,2,\ldots,n\\}}{n}.$

In particular, if $(x_{n})_{n\in\mathbb{N}}$ is a fixed sequence of non-
negative integers, then by odd density of $(x_{n})_{n\in\mathbb{N}_{+}}$ we
mean the value

$\displaystyle\lim_{n\to\infty}\frac{\\#\\{i\leqslant n:x_{i}\equiv 1\mkern
4.0mu({\operator@font mod}\mkern 6.0mu2)\\}}{n}.$

This notation will simplify the formulation of our statements.

##  3\. Periodicity of $p_{\mathcal{A}}(n,k)\mkern 4.0mu({\operator@font
mod}\mkern 6.0mum)$

At the beginning, we prove a result, which is relevant in estimation of the
lower bound for the density of the set

$\displaystyle\\{n\in\mathbb{N}:p_{\mathcal{A}}(n,k)\not\equiv 0\mkern
4.0mu({\operator@font mod}\mkern 6.0mum)\\}.$

In order to achieve the goal, let us first find a recurrence relation for
$p_{\mathcal{A}}$ and recall theorems related to the fundamental period of
$p_{\mathcal{A}}(n,k).$ We will use them in two final sections in order to
compute densities of some sets connected with the restricted partition
function. For given $k$, these results reduce determining the odd density of
$p_{\mathcal{A}}(n,k)$ to a finite task.

######  Lemma 3.1.

For all $n\in\mathbb{N}$ and $k\in\mathbb{N}_{+}$, the following equality
holds

(3.1) $\displaystyle
p_{\mathcal{A}}(n,k)=p_{\mathcal{A}}(n-a_{k},k)+p_{\mathcal{A}}(n,k-1).$

###### Proof.

We assume that $p_{\mathcal{A}}(0,k)=1$ and $p_{\mathcal{A}}(n,k)=0$ for
$n<0$. Let us consider the generating function for $p_{\mathcal{A}}(n,k)$.
Obviously, we have

(3.2)
$\sum_{n=0}^{\infty}p_{\mathcal{A}}(n,k)x^{n}=\prod_{i=1}^{k}\frac{1}{1-x^{a_{i}}}.$

Multiplying both sides of the equality by $1-x^{a_{k}}$ we obtain the
following:

$\displaystyle(1-x^{a_{k}})\sum_{n=0}^{\infty}p_{\mathcal{A}}(n,k)x^{n}=\prod_{i=1}^{k-1}\frac{1}{1-x^{a_{i}}}=\sum_{n=0}^{\infty}p_{\mathcal{A}}(n,k-1)x^{n}.$

If we rearrange the left-sided terms above, we deduce

$\displaystyle\sum_{n=0}^{\infty}p_{\mathcal{A}}(n,k)x^{n}-\sum_{n=0}^{\infty}p_{\mathcal{A}}(n-a_{k},k)x^{n}=\sum_{n=0}^{\infty}p_{\mathcal{A}}(n,k-1)x^{n}.$

Since $p_{\mathcal{A}}(0,k)=1$ and $p_{\mathcal{A}}(j,k)=0$ for $j<0$, the
equality
$p_{\mathcal{A}}(n,k)-p_{\mathcal{A}}(n-a_{k},k)=p_{\mathcal{A}}(n,k-1)$ holds
for all $n\in\mathbb{N}$. ∎

Let us recall that a sequence $(x_{n})_{n\in\mathbb{N}}$ is periodic, if there
exists a positive integer $s$ such that $x_{n}=x_{n+s}$ for all sufficiently
large $n$. The number $s$ is called the period of the infinite sequence. The
least positive constant $s$ with this property is called the fundamental (or
minimal period). Additionally, if $x_{n}=x_{n+s}$ holds for all $n$, then the
sequence is called purely periodic.

The following two theorems were proven by Kwong in [13, 12], respectively. It
is worth to note that a slightly weaker version of the Theorem $3.3$
originally appeared in [15].

######  Theorem 3.2.

Let $m>1$ be a positive integer and let
$(x_{n})_{n\in\mathbb{N}}\in\mathbb{N}^{\infty}$ be fixed. If
$m=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\ldots p_{k}^{\alpha_{k}}$ is the prime
factorization of $m$, then the period $T_{m}$ of $\\{x_{n}\mkern
4.0mu({\operator@font mod}\mkern 6.0mum)\\}_{n\in\mathbb{N}}$ satisfies

(3.3) $T_{m}=\text{lcm}\\{T_{p_{i}^{\alpha_{i}}}:1\leqslant i\leqslant k\\},$

where $T_{p_{j}^{\alpha_{j}}}$ denotes the period of $\\{x_{n}\mkern
4.0mu({\operator@font mod}\mkern 6.0mup_{j}^{\alpha_{j}})\\}_{n\in\mathbb{N}}$
for each $j\in\\{1,\ldots,k\\}$.

The second theorem gives us an explicit recipe, how to determine the
fundamental period $(p_{\mathcal{A}}(n,k)\mkern 4.0mu({\operator@font
mod}\mkern 6.0mup^{N}))_{n\in\mathbb{N}_{+}}$ for a fixed positive integer $N$
and prime number $p$.

Before stating the claim let us remind that for a given positive integer $n$
and prime number $p$, the $p-$free part of $n$ is the number $n/p^{\alpha}$,
where $\alpha$ satisfies $p^{\alpha}||n$.

######  Theorem 3.3.

Let $p\in\mathbb{P}$ and $N\in\mathbb{N}_{+}$ be arbitrary. Let $L$ be the
$p$-free part of $\text{lcm}\\{a_{i}:i\in\\{1,\ldots,k\\}\\}$, and $b$ be the
least integer such that

(3.4) $p^{b}\geqslant\sum_{i=1}^{k}p^{e(a_{i})},$

where $p^{e(a_{i})}||a_{i}$ for each $i\in\\{1,\ldots,k\\}$. Then
$(p_{\mathcal{A}}(n,k)\mkern 4.0mu({\operator@font mod}\mkern
6.0mup^{N}))_{n\in\mathbb{N}}$ is purely periodic with minimal period

(3.5) $p^{N+b-1}L.$

######  Remark 3.4.

The above theorems assert that the density of the set
$\\{n\in\mathbb{N}:p_{\mathcal{A}}(n,k)\equiv i\mkern 4.0mu({\operator@font
mod}\mkern 6.0mum)\\}$ for $i\in\\{0,1,\ldots,m-1\\}$, is determined by the
number of values of $n$ such that $p_{\mathcal{A}}(n,k)\equiv i\mkern
4.0mu({\operator@font mod}\mkern 6.0mum)$ over a finite range of $n$.

The next result is a consequence of theorems mentioned above. We take its
advantage to determine the lower bound for density in Sec. $5$.

######  Corollary 3.5.

If $k$ and $m$ are fixed positive integers with $m\geqslant 2$, then the
function $p_{\mathcal{A}}(n,k)\mkern 4.0mu({\operator@font mod}\mkern 6.0mum)$
is periodic on $n$. Moreover, $m^{k-1}\text{lcm}\\{a_{1},\ldots,a_{k}\\}$ is a
period of $p_{\mathcal{A}}(n,k)\mkern 4.0mu({\operator@font mod}\mkern
6.0mum)$.

###### Proof.

Let $m\geqslant 2$ be a fixed positive integer. We consider two cases.

First, we assume that $k=1$. Then

$p_{\mathcal{A}}(n,1)=\begin{cases}0,&\text{if }a_{1}\nmid n\\\ 1,&\text{if
}a_{1}\mid n.\end{cases}$

and we obtain periodicity of the function $p_{\mathcal{A}}(n,1)\mkern
4.0mu({\operator@font mod}\mkern 6.0mum)$ on $n$ with the period $T=a_{1}.$
This completes the proof for $k=1$. Now, let $k\geqslant 2$. We assume that
$m=p_{1}^{\alpha_{1}}\ldots p_{l}^{\alpha_{l}}$ is a prime factorization of
$m$ and we represent parts in the form

$\displaystyle a_{1}=p_{1}^{\beta_{1,1}}\ldots
p_{l}^{\beta_{1,l}}p_{l+1}^{\beta_{1,l+1}}\ldots p_{l+s}^{\beta_{1,l+s}}$
$\displaystyle a_{2}=p_{1}^{\beta_{2,1}}\ldots
p_{l}^{\beta_{2,l}}p_{l+1}^{\beta_{2,l+1}}\ldots p_{l+s}^{\beta_{2,l+s}}$
$\displaystyle\vdots$ $\displaystyle a_{k-1}=p_{1}^{\beta_{k-1,1}}\ldots
p_{l}^{\beta_{k-1,l}}p_{l+1}^{\beta_{k-1,l+1}}\ldots
p_{l+s}^{\beta_{k-1,l+s}}$ $\displaystyle a_{k}=p_{1}^{\beta_{k,1}}\ldots
p_{l}^{\beta_{k,l}}p_{l+1}^{\beta_{k,l+1}}\ldots p_{l+s}^{\beta_{k,l+s}},$

where $p_{j}$ are all possible distinct prime divisors of
$m,a_{1},\ldots,a_{k}$, and $\beta_{i,j}\geqslant 0$ for any $1\leqslant
i\leqslant k$ and $1\leqslant j\leqslant l+s$. Due to equation $(3.3)$ in
Theorem $3.2$, we concentrate on periodicity modulo $p_{t}^{\alpha_{t}}$,
where $1\leqslant t\leqslant l$. Let $\gamma_{j}=\max\\{\beta_{i,j}:1\leqslant
i\leqslant k\\}$. Then the $p_{t}$-free part of
$\text{lcm}\\{a_{i}:i\in\\{1,\ldots,k\\}\\}$ can be expressed as

$\displaystyle
L_{t}=\frac{\prod_{i=1}^{l+s}p_{i}^{\gamma_{i}}}{p_{t}^{\gamma_{t}}}.$

Next, let $b_{t}$ be the smallest natural number such that

$\displaystyle p_{t}^{b_{t}}\geqslant\sum_{i=1}^{k}p_{t}^{\beta_{i,t}}.$

The right side of the above inequality can be bounded from above in the
following way

$\displaystyle\sum_{i=1}^{k}p_{t}^{\beta_{i,t}}\leqslant\sum_{i=1}^{k}p_{t}^{\gamma_{t}}=kp_{t}^{\gamma_{t}}\leqslant
p_{t}^{k-1}p_{t}^{\gamma_{t}}=p_{t}^{k-1+\gamma_{t}}.$

Hence, $b_{t}\leqslant k-1+\gamma_{t}$ and the fundamental period modulo
$p_{t}^{\alpha_{t}}$ satisfies

$\displaystyle p_{t}^{\alpha_{t}+b_{t}-1}L_{t}\mid
p_{t}^{\alpha_{t}+k-2+\gamma_{t}}L_{t}.$

Thus, the sequence $p_{\mathcal{A}}(n,k)\mkern 4.0mu({\operator@font
mod}\mkern 6.0mup_{t}^{\alpha_{t}})$ is periodic in $n$ with the period
$p_{t}^{\alpha_{t}+k-2+\gamma_{t}}L_{t}$. Moreover, Theorem $3.2$ and our
prior consideration maintain that

$\displaystyle T_{m}$
$\displaystyle=\text{lcm}\\{p_{t}^{\alpha_{t}+b_{t}-1}L_{t}:1\leqslant
t\leqslant
l\\}\mid\text{lcm}\\{p_{t}^{\alpha_{t}+k-2+\gamma_{t}}L_{t}:1\leqslant
t\leqslant n\\}$
$\displaystyle=\prod_{j=1}^{l}p_{j}^{\alpha_{j}+k-2}\prod_{j=1}^{l+s}p_{j}^{\gamma_{j}}.$

In particular, we have
$\prod_{j=1}^{l+s}p_{j}^{\gamma_{j}}=\text{lcm}\\{a_{1},\ldots,a_{k}\\}.$
Hence, to complete the proof, we just need to show that
$\prod_{j=1}^{l}p_{j}^{\alpha_{j}+k-2}\mid\prod_{j=1}^{l}p_{j}^{\alpha_{j}(k-1)}=m^{k-1}.$
However, it can be easily verified that the inequality
$\alpha_{j}+k-2\leqslant\alpha_{j}(k-1)$ holds for each $j\in\\{1,\ldots,l\\}$
and $k\geqslant 2$, as desired. ∎

##  4\. Upper bound for the density of
$\\{n\in\mathbb{N}:p_{\mathcal{A}}(n,k)\equiv 1\mkern 4.0mu({\operator@font
mod}\mkern 6.0mu2)\\}$

In this section, we will take advantage of Lemma $3.1$ to find a special
relation between certain densities, which gives us the ability to determine
the upper bound for odd density of $p_{\mathcal{A}}(n,k)$.

######  Lemma 4.1.

If $k\in\mathbb{N}_{\geqslant 2}$, then the following equality holds

$\displaystyle\lim_{N\to\infty}$ $\displaystyle\frac{\\#\\{n\leqslant
N:p_{\mathcal{A}}(n,k)\equiv p_{\mathcal{A}}(n,k-1)\equiv 1\mkern
4.0mu({\operator@font mod}\mkern 6.0mu2)\\}}{N}$
$\displaystyle=\lim_{N\to\infty}\frac{\\#\\{n\leqslant
N:p_{\mathcal{A}}(n,k)\not\equiv p_{\mathcal{A}}(n,k-1)\equiv 1\mkern
4.0mu({\operator@font mod}\mkern 6.0mu2)\\}}{N}.$

###### Proof.

Fix $k\in\mathbb{N}_{\geqslant 2}$. On the one hand, we can easily notice that

$\displaystyle\lim_{N\to\infty}$ $\displaystyle\frac{\\#\\{n\leqslant
N:p_{\mathcal{A}}(n,k)\equiv 1\mkern 4.0mu({\operator@font mod}\mkern
6.0mu2)\\}}{N}$ $\displaystyle=\lim_{N\to\infty}\frac{\\#\\{n\leqslant
N:p_{\mathcal{A}}(n,k)\equiv p_{\mathcal{A}}(n,k-1)\equiv 1\mkern
4.0mu({\operator@font mod}\mkern 6.0mu2)\\}}{N}$
$\displaystyle+\lim_{N\to\infty}\frac{\\#\\{n\leqslant
N:p_{\mathcal{A}}(n,k)\not\equiv p_{\mathcal{A}}(n,k-1)\equiv 0\mkern
4.0mu({\operator@font mod}\mkern 6.0mu2)\\}}{N}.$

On the other hand, applying $(3.1)$, we get

$\displaystyle\lim_{N\to\infty}$ $\displaystyle\frac{\\#\\{n\leqslant
N:p_{\mathcal{A}}(n,k)\equiv 1\mkern 4.0mu({\operator@font mod}\mkern
6.0mu2)\\}}{N}$ $\displaystyle=\lim_{N\to\infty}\frac{\\#\\{n\leqslant
N:p_{\mathcal{A}}(n+a_{k},k)-p_{\mathcal{A}}(n+a_{k},k-1)\equiv 1\mkern
4.0mu({\operator@font mod}\mkern 6.0mu2)\\}}{N}.$

We can replace terms of $n+a_{k}$ with $n$, since we consider the limit as
$N\to\infty.$ Therefore, we obtain

$\displaystyle\lim_{N\to\infty}$ $\displaystyle\frac{\\#\\{n\leqslant
N:p_{\mathcal{A}}(n,k)\equiv 1\mkern 4.0mu({\operator@font mod}\mkern
6.0mu2)\\}}{N}$ $\displaystyle=\lim_{N\to\infty}\frac{\\#\\{n\leqslant
N:p_{\mathcal{A}}(n,k)-p_{\mathcal{A}}(n,k-1)\equiv 1\mkern
4.0mu({\operator@font mod}\mkern 6.0mu2)\\}}{N}$
$\displaystyle=\lim_{N\to\infty}\frac{\\#\\{n\leqslant
N:p_{\mathcal{A}}(n,k)\not\equiv p_{\mathcal{A}}(n,k-1)\equiv 1\mkern
4.0mu({\operator@font mod}\mkern 6.0mu2)\\}}{N}$
$\displaystyle+\lim_{N\to\infty}\frac{\\#\\{n\leqslant
N:p_{\mathcal{A}}(n,k)\not\equiv p_{\mathcal{A}}(n,k-1)\equiv 0\mkern
4.0mu({\operator@font mod}\mkern 6.0mu2)\\}}{N}$

Finally, if we compare the last equality with the first in the proof, we
conclude the required result. ∎

The next result generalizes findings of Karhadkar in [11], namely, the case of
$\mathcal{A}=(n)_{n\in\mathbb{N}_{+}}$, to any sequence $\mathcal{A}$ of
positive integers.

######  Theorem 4.2.

The inequality

$\displaystyle\lim_{N\to\infty}$ $\displaystyle\frac{\\#\\{n\leqslant
N:p_{\mathcal{A}}(n,k)\equiv 1\mkern 4.0mu({\operator@font mod}\mkern
6.0mu2)\\}}{N}\leqslant\frac{2}{3}$

holds for infinitely many positive integers $k$. More precisely, if the above
inequality is not satisfied for some positive integer $k$, then it holds for
$k+1$.

###### Proof.

Let us assume that the odd density of $p_{\mathcal{A}}(n,k)$ is grater than
$\frac{2}{3}$, that is

$\displaystyle\lim_{N\to\infty}$ $\displaystyle\frac{\\#\\{n\leqslant
N:p_{\mathcal{A}}(n,k)\equiv 1\mkern 4.0mu({\operator@font mod}\mkern
6.0mu2)\\}}{N}>\frac{2}{3}.$

By Lemma $4.1$, we can rewrite the left-sided term as

$\displaystyle\lim_{N\to\infty}$ $\displaystyle\frac{\\#\\{n\leqslant
N:p_{\mathcal{A}}(n,k)\equiv 1\mkern 4.0mu({\operator@font mod}\mkern
6.0mu2)\\}}{N}$ $\displaystyle=\lim_{N\to\infty}\frac{\\#\\{n\leqslant
N:p_{\mathcal{A}}(n,k)\not\equiv p_{\mathcal{A}}(n,k+1)\equiv 0\mkern
4.0mu({\operator@font mod}\mkern 6.0mu2)\\}}{N}$
$\displaystyle+\lim_{N\to\infty}\frac{\\#\\{n\leqslant
N:p_{\mathcal{A}}(n,k)\equiv p_{\mathcal{A}}(n,k+1)\equiv 1\mkern
4.0mu({\operator@font mod}\mkern 6.0mu2)\\}}{N}$
$\displaystyle=2\lim_{N\to\infty}\frac{\\#\\{n\leqslant
N:p_{\mathcal{A}}(n,k+1)\not\equiv p_{\mathcal{A}}(n,k)\equiv 1\mkern
4.0mu({\operator@font mod}\mkern 6.0mu2)\\}}{N}.$

Hence, we observe that

$\displaystyle\lim_{N\to\infty}\frac{\\#\\{n\leqslant
N:p_{\mathcal{A}}(n,k+1)\not\equiv p_{\mathcal{A}}(n,k)\equiv 1\mkern
4.0mu({\operator@font mod}\mkern 6.0mu2)\\}}{N}>\frac{1}{3},$

and, in particular,

$\displaystyle\lim_{N\to\infty}\frac{\\#\\{n\leqslant
N:p_{\mathcal{A}}(n,k+1)\equiv 0\mkern 4.0mu({\operator@font mod}\mkern
6.0mu2)\\}}{N}>\frac{1}{3}.$

Therefore, we conclude that the following inequality holds

$\displaystyle\lim_{N\to\infty}\frac{\\#\\{n\leqslant
N:p_{\mathcal{A}}(n,k+1)\equiv 1\mkern 4.0mu({\operator@font mod}\mkern
6.0mu2)\\}}{N}\leqslant\frac{2}{3}$

and thereby there exist infinitely many natural numbers $k$ such that the odd
density of $p_{\mathcal{A}}(n,k)$ is not grater than $\frac{2}{3}$, which was
to prove. ∎

As we will see in the sequel, the inequality in Theorem $4.2$ is not optimal.
The reason is simple: it does not depend on the elements of the sequence
$\mathcal{A}$. On the other hand, we will find lower bound for the odd density
of $p_{\mathcal{A}}(n,k)$.

##  5\. Lower bound for the density of
$\\{n\in\mathbb{N}:p_{\mathcal{A}}(n,k)\not\equiv 0\mkern
4.0mu({\operator@font mod}\mkern 6.0mum)\\}$

In spite of consideration in Sec. $4$, we will generalize our reasonings to
any positive integer $m>1$. Theorems $3.2$ and $3.3$ provide that
$p_{\mathcal{A}}(n,k)\mkern 4.0mu({\operator@font mod}\mkern 6.0mum)$ is
periodic on $n$ for every positive integer $k\geqslant 1$. Thus, we can
represent its generating function in the form

$\displaystyle\sum_{n=0}^{\infty}p_{\mathcal{A}}(n,k)x^{n}=\prod_{i=1}^{k}\frac{1}{1-x^{a_{i}}}\equiv\frac{a(x)}{1-x^{T}}\mkern
4.0mu({\operator@font mod}\mkern 6.0mum),$

where $T$ is the fundamental period of $p_{\mathcal{A}}(n,k)\mkern
4.0mu({\operator@font mod}\mkern 6.0mum)$ and $\deg(a)<T$. Multiplying both
sides of the above congruence by the denominators, we get

$\displaystyle a(x)\prod_{i=1}^{k}(1-x^{a_{i}})\equiv 1-x^{T}\mkern
4.0mu({\operator@font mod}\mkern 6.0mum),$

which implies that

$\deg(a)=T-\sum_{i=1}^{k}a_{i}.$

It means that the last $\sum_{i=0}^{k}a_{i}-1$ terms of a period of
$p_{\mathcal{A}}(n,k)$ must be zero modulo $m$. Hence, for each positive
integer $k$, we have $\sum_{i=0}^{k}a_{i}-1$ consecutive values of $n$, which
are divisible by $m$. Moreover, we get even stronger consequence of this fact.

######  Theorem 5.1.

For any $k\in\mathbb{N_{+}}$ and $m\in\mathbb{N}_{\geqslant 2}$, there exist
at most $\sum_{i=1}^{k}a_{i}-1$ consecutive values of $n$ such that
$p_{\mathcal{A}}(n,k)\equiv 0\mkern 4.0mu({\operator@font mod}\mkern 6.0mum)$.

###### Proof.

We prove the theorem by induction on $k$, for any fixed $m\geqslant 2.$ If
$k=1$, then

$p_{\mathcal{A}}(n,1)=\begin{cases}0,&\text{if }a_{1}\nmid n\\\ 1,&\text{if
}a_{1}\mid n,\end{cases}$

so there exist at most $a_{1}-1$ consecutive values of $n$ such that
$p_{\mathcal{A}}(n,1)\equiv 0\mkern 4.0mu({\operator@font mod}\mkern 6.0mum)$.
This establishes the basis case. Let us assume that the statement holds for
$k=l-1$. If

(5.1) $\displaystyle p_{\mathcal{A}}(i,l)\equiv
p_{\mathcal{A}}(i+1,l)\equiv\ldots\equiv
p_{\mathcal{A}}\left(i+\sum_{j=1}^{l}a_{j}-2,l\right)\equiv 0\mkern
4.0mu({\operator@font mod}\mkern 6.0mum),$

then

$\displaystyle p_{\mathcal{A}}(i+a_{l},l)-p_{\mathcal{A}}(i,l),$
$\displaystyle p_{\mathcal{A}}(i+1+a_{l},l)-p_{\mathcal{A}}(i+1,l),$
$\displaystyle\vdots$ $\displaystyle
p_{\mathcal{A}}\left(i+\sum_{j=1}^{l}a_{j}-2,l\right)-p_{\mathcal{A}}\left(i+\sum_{j=1}^{l-1}a_{j}-2,l\right)$

are all divisible by $m$. Next, Lemma $3.1$ implies that

$\displaystyle p_{\mathcal{A}}(i+a_{l},l-1)$ $\displaystyle\equiv
p_{\mathcal{A}}(i+1+a_{l},l-1)\equiv\ldots$ $\displaystyle\ldots$
$\displaystyle\equiv
p_{\mathcal{A}}\left(i+\sum_{j=1}^{l}a_{j}-2,l-1\right)\equiv 0\mkern
4.0mu({\operator@font mod}\mkern 6.0mum).$

However, the sequence consists of $\sum_{j=1}^{l-1}a_{j}-1$ consecutive
numbers, which are divisible by $m$. Therefore, by the induction hypothesis,
$p_{\mathcal{A}}(i+\sum_{j=1}^{l}a_{j}-1,l-1)\not\equiv 0\mkern
4.0mu({\operator@font mod}\mkern 6.0mum)$. On the other hand, $(5.1)$ asserts
that

$\displaystyle p_{\mathcal{A}}\left(i+\sum_{j=1}^{l-1}a_{j}-1,l\right)\equiv
0\mkern 4.0mu({\operator@font mod}\mkern 6.0mum).$

If we apply Lemma $3.1$ once again, we conclude that

$\displaystyle p_{\mathcal{A}}\left(i+\sum_{j=1}^{l}a_{j}-1,l\right)$
$\displaystyle=p_{\mathcal{A}}\left(i+\sum_{j=1}^{l-1}a_{j}-1,l\right)+p_{\mathcal{A}}\left(i+\sum_{j=1}^{l}a_{j}-1,l-1\right)$
$\displaystyle\not\equiv 0\mkern 4.0mu({\operator@font mod}\mkern 6.0mum).$

This completes the inductive step and thereby ends the proof. ∎

The next theorem directly implies the lower bound for the considered density.

######  Theorem 5.2.

Let $m>1$ be a fixed positive integer. For each positive integer $k$, we have

(5.2) $\lim_{N\to\infty}\frac{\\#\\{n\leqslant
N:p_{\mathcal{A}}(n,k)\not\equiv 0\mkern 4.0mu({\operator@font mod}\mkern
6.0mum)\\}}{N}\geqslant\frac{1}{\sum_{i=1}^{k}a_{i}}.$

###### Proof.

Let us fix positive integers $k$ and $m$ with $m>1$. By the previous theorem,
we know that there can be at most $\sum_{i=1}^{k}a_{i}-1$ consecutive values
of $n$ such that $p_{\mathcal{A}}(n,k)\equiv 0\mkern 4.0mu({\operator@font
mod}\mkern 6.0mum)$. Thus, in any collection of $\sum_{i=1}^{k}a_{i}$
consecutive terms of $(p_{\mathcal{A}}(n,k))_{n\in\mathbb{N}}$, there exist at
least one index, say for example $n_{k}$, such that
$p_{\mathcal{A}}(n_{k},k)\not\equiv 0\mkern 4.0mu({\operator@font mod}\mkern
6.0mum).$ Therefore,

$\displaystyle\lim_{N\to\infty}\frac{\\#\\{n\leqslant
N:p_{\mathcal{A}}(n,k)\not\equiv 0\mkern 4.0mu({\operator@font mod}\mkern
6.0mum)\\}}{N}\geqslant\frac{1}{\sum_{i=1}^{k}a_{i}}.$

∎

Clearly, Theorem $5.2$ automatically asserts that for $m=2$ we obtain the
lower bound for the odd density of $p_{\mathcal{A}}(n,k)$. In contrast to
Theorem $4.2$, the above inequality depends on the sequence $\mathcal{A}$.
However, it is independent of $m$, and consequently is not optimal as well.

##  6\. Some results on restricted $m$-ary partitions

Now, we focus on some properties of so called restricted $m$-ary partition
function. First, let us introduce a definition which simplify the notation.

######  Definition 6.1.

Let $\mathcal{A}$ be a sequence of positive integers. For any arbitrarily
fixed $m\in\mathbb{N}_{\geqslant 2}$, $k\in\mathbb{N}_{+}$ and
$i\in\\{0,1,\ldots,m-1\\}$ let $S_{\mathcal{A}}(i,m,k)$ denote

$\displaystyle
S_{\mathcal{A}}(i,m,k)=\\{n\in\mathbb{N}:p_{\mathcal{A}}(n,k)\equiv i\mkern
4.0mu({\operator@font mod}\mkern 6.0mum)\\}.$

In this section we consider the sequence
$\mathcal{M}=(m^{n-1})_{n\in\mathbb{N}_{+}}$ for a given positive integer
$m>1$. The generating function for $p_{\mathcal{M}}(n,k)$ is given by

$\displaystyle\sum_{n=0}^{\infty}p_{\mathcal{M}}(n,k)x^{n}=\prod_{i=0}^{k-1}\frac{1}{1-x^{m^{i}}}.$

From Lemma $3.1$ we immediately obtain a recurrence relation of the form

(6.1) $\displaystyle
p_{\mathcal{M}}(n,k)=p_{\mathcal{M}}(n-m^{k-1},k)+p_{\mathcal{M}}(n,k-1).$

The study of congruence properties of the binary partition function (the case
of $m=2$) was initiated in the late 1960’s by Churchhouse [7, 8]. Afterwards,
among others, Gupta [9, 10], Andrews [2, 5], Rødseth [18, 19] and Sellers [5,
19] widely developed theory related to $m-$ary partitions. Now, we perform an
analogous fact to the theorem obtained in [5], for the restricted partition
function $p_{\mathcal{M}}(n,k)$.

######  Theorem 6.2.

Let $m>1$, $k$ and $n$ be fixed positive integers. If we represent $n$ in base
$m$, that is

(6.2)
$n=c_{N}m^{N}+c_{N-1}m^{N-1}+\ldots+c_{k}m^{k}+c_{k-1}m^{k-1}+\ldots+c_{1}m+c_{0},$

and we put $\mathcal{M}=(m^{i-1})_{i\in\mathbb{N}_{+}}$, then

(6.3) $\displaystyle
p_{\mathcal{M}}(n,k)\equiv(c_{1}+1)(c_{2}+1)\ldots(c_{k-1}+1)\mkern
4.0mu({\operator@font mod}\mkern 6.0mum).$

###### Proof.

We perform induction on $k$ to prove the statement. Clearly,
$p_{\mathcal{M}}(n,1)=1$ for all $n\in\mathbb{N}_{+}.$ This establishes the
basic case. Further, let us assume that $(6.3)$ holds for $j=k-1\geqslant 1$,
and check the truth of the statement for $j=k$. Theorem $3.3$ provides that
the fundamental period of the sequence $(p_{\mathcal{M}}(n,k)\mkern
4.0mu({\operator@font mod}\mkern 6.0mum))_{n\in\mathbb{N}}$ is $m^{k}$. Thus,
we only need to examine $p_{\mathcal{M}}(n,k)\mkern 4.0mu({\operator@font
mod}\mkern 6.0mum)$ for all $0\leqslant n\leqslant m^{k}-1.$ Therefore, we
arbitrarily fix $n$ between $0$ and $m^{k-1}$, and present it in base $m$:

$\displaystyle n=c_{k-1}m^{k-1}+c_{k-2}m^{k-2}+\ldots+c_{1}m+c_{0},$

i.e., $c_{j}\in\\{0,1,\ldots,m-1\\}$ for $j\in\\{0,1,\ldots,k-1\\}$. Now, if
we apply the recurrence equation $(6.1)$ $c_{k-1}$ times, then we get

$\displaystyle p_{\mathcal{M}}(n,k)$
$\displaystyle=p_{\mathcal{M}}(n-m^{k-1},k)+p_{\mathcal{M}}(n,k-1)$
$\displaystyle=p_{\mathcal{M}}(n-2m^{k-1},k)+p_{\mathcal{M}}(n-m^{k-1},k-1)+p_{\mathcal{M}}(n,k-1)$
$\displaystyle=\ldots=p_{\mathcal{M}}(n-c_{k-1}m^{k-1},k)+p_{\mathcal{M}}(n-(c_{k-1}-1)m^{k-1},k-1)$
$\displaystyle\hskip
36.98866pt+\ldots+p_{\mathcal{M}}(n-m^{k-1},k-1)+p_{\mathcal{M}}(n,k-1).$

It is easy to verify that
$p_{\mathcal{M}}(n-c_{k-1}m^{k-1},k)=p_{\mathcal{M}}(n-c_{k-1}m^{k-1},k-1)$,
since $n-c_{k-1}m^{k-1}<m^{k-1}$. Thus, by both these fact and the induction
hypothesis, we deduce

$\displaystyle p_{\mathcal{M}}(n,k)=$ $\displaystyle
p_{\mathcal{M}}(n-c_{k-1}m^{k-1},k-1)+p_{\mathcal{M}}(n-(c_{k-1}-1)m^{k-1},k-1)$
$\displaystyle+\ldots+p_{\mathcal{M}}(n-m^{k-1},k-1)+p_{\mathcal{M}}(n,k-1).$
$\displaystyle\equiv$
$\displaystyle(c_{k-1}+1)\prod_{i=1}^{k-2}(c_{i}+1)\equiv\prod_{i=1}^{k-1}(c_{i}+1)\mkern
4.0mu({\operator@font mod}\mkern 6.0mum).$

This completes the inductive step and the proof. ∎

There are many consequences of this result. For instance, if we assume that
$m$ is a prime number and $k$ is fixed positive integer, then we may easily
determine the number of solutions of the congruence
$p_{\mathcal{M}}(n,k)\equiv i\mkern 4.0mu({\operator@font mod}\mkern 6.0mum)$
for any $i\in\\{0,1,\ldots,m-1\\}$.

######  Corollary 6.3.

Let $m\in\mathbb{P}$, $i\in\\{1,2,\ldots,m-1\\}$ and
$k\in\mathbb{N}_{\geqslant 2}$ be fixed. The congruence

$\displaystyle p_{\mathcal{M}}(n,k)\equiv i\mkern 4.0mu({\operator@font
mod}\mkern 6.0mum)$

has $m(m-1)^{k-2}$ distinct solutions $\pmod{m^{k}}$. If $k=1$, then
$p_{\mathcal{M}}(n,1)=1$ for all $n\in\mathbb{N}$.

###### Proof.

Let $m\in\mathbb{P}$, $i\in\\{1,2,\ldots,m-1\\}$ and $k\in\mathbb{N}_{+}$ be
given. The claim is clear for $k=1$. Hence, we assume that $k\geqslant 2$.
Since, we want to determine those $n\in\\{0,1,\ldots,m^{k}-1\\}$ which satisfy
$p_{\mathcal{M}}(n,k)\equiv i\mkern 4.0mu({\operator@font mod}\mkern 6.0mum)$,
we may represent $n$ in the base $m$, as

$n=c_{k-1}m^{k-1}+c_{k-2}m^{k-2}+\ldots+c_{1}m+c_{0}.$

From Theorem $6.2$ we know that

$p_{\mathcal{M}}(n,k)\equiv(c_{1}+1)(c_{2}+1)\ldots(c_{k-1}+1)\mkern
4.0mu({\operator@font mod}\mkern 6.0mum).$

Therefore, we have $m$ ways to choose $c_{0}$ and $m-1$ possibilities to
select $c_{j}$ for each $j\in\\{1,2,\ldots,k-2\\}$ – we have to omit those
cases in which at least one of them is equal to $m-1$, otherwise we
automatically get $p_{\mathcal{M}}(n,k)\equiv 0\mkern 4.0mu({\operator@font
mod}\mkern 6.0mum)$. The last coefficient $c_{k-1}$ is uniquely determined, as
a consequence of elementary property of congruences. Finally, we conclude that
$p_{\mathcal{M}}(n,k)\equiv i\mkern 4.0mu({\operator@font mod}\mkern 6.0mum)$
has $m(m-1)^{k-2}$ distinct solutions $\mkern 4.0mu({\operator@font mod}\mkern
6.0mum^{k})$. ∎

Due to the above fact, we can immediately deduce some information about
$d(S_{\mathcal{M}}(i,m,k))$ for fixed prime number $m$.

######  Corollary 6.4.

Let $m$ be a fixed prime number and let $i\in\\{1,2,\ldots,m-1\\}$ be given.
If $\mathcal{M}=(m^{n-1})_{n\in\mathbb{N}_{+}}$, then

$\displaystyle\lim_{N\to\infty}\frac{\\#\\{n\leqslant
N:p_{\mathcal{M}}(n,k)\equiv i\mkern 4.0mu({\operator@font mod}\mkern
6.0mum)\\}}{N}=\frac{(m-1)^{k-2}}{m^{k-1}}$

for any positive integer $k\geqslant 2$.

###### Proof.

The prior corollary provides that among any collection of $m^{k}$ consecutive
values of $n$, we have exactly $m(m-1)^{k-2}$ indexes such that
$p_{\mathcal{M}}(n,k)\equiv i\mkern 4.0mu({\operator@font mod}\mkern 6.0mum)$.
Therefore, the equality in the statement holds. ∎

Additionally, we are able to describe explicitly characterization of those
non-negative integers, which satisfy $p_{\mathcal{M}}(n,k)\equiv i\mkern
4.0mu({\operator@font mod}\mkern 6.0mum)$ for some small values of $m$.

######  Example 6.5.

Let $k$ and $n$ be non-negative integers. If
$\mathcal{M}=(2^{i-1})_{i\in\mathbb{N}_{+}}$ and

$n\equiv c_{k-1}2^{k-1}+c_{k-2}2^{k-2}+\ldots+c_{1}2+c_{0}\mkern
4.0mu({\operator@font mod}\mkern 6.0mu2^{k}),$

then the following conditions are equivalent:

  1. (1)

$p_{\mathcal{M}}(n,k)\equiv 1\mkern 4.0mu({\operator@font mod}\mkern 6.0mu2)$;

  2. (2)

$c_{j}\neq 1\text{ for all }j\in\\{1,2,\ldots,k-1\\}$;

  3. (3)

$n\equiv 0,1\pmod{2^{k}}$.

######  Example 6.6.

If $k$ and $n$ are fixed non-negative integers,
$\mathcal{M}=(3^{i-1})_{i\in\mathbb{N}_{+}}$ and $n$ satisfies

$n\equiv c_{k-1}3^{k-1}+c_{k-2}3^{k-2}+\ldots+c_{1}3+c_{0}\mkern
4.0mu({\operator@font mod}\mkern 6.0mu3^{k}),$

then $p_{\mathcal{M}}(n,k)\equiv 1\mkern 4.0mu({\operator@font mod}\mkern
6.0mu3)$ if and only if the number of non-zero coefficients $c_{j}$ for $j>0$
is even, and all of them are equal to $1$. Symmetrically,
$p_{\mathcal{M}}(n,k)\equiv 2\mkern 4.0mu({\operator@font mod}\mkern 6.0mu3)$
if and only if the number of non-zero coefficients $c_{j}$ for $j>0$ is odd,
and all of them are equal to $1$.

For $m=4$ the description becomes slightly more complex.

######  Example 6.7.

Let $k$ and $n$ be arbitrarily fixed non-negative integers. If
$\mathcal{M}=(4^{i-1})_{i\in\mathbb{N}_{+}}$ and $n$ satisfies

$n\equiv c_{k-1}4^{k-1}+c_{k-2}4^{k-2}+\ldots+c_{1}4+c_{0}\mkern
4.0mu({\operator@font mod}\mkern 6.0mu4^{k}),$

then $p_{\mathcal{M}}(n,k)\equiv 1\mkern 4.0mu({\operator@font mod}\mkern
6.0mu4)$ if and only if the number of non-zero coefficients $c_{j}$ for $j>0$
is even, and all of them are equal to $2$. Analogously,
$p_{\mathcal{M}}(n,k)\equiv 3\mkern 4.0mu({\operator@font mod}\mkern 6.0mu4)$
if and only if the number of non-zero coefficients $c_{j}$ for $j>0$ is odd,
and all of them are equal to $2$. Moreover, $p_{\mathcal{M}}(n,k)\equiv
2\mkern 4.0mu({\operator@font mod}\mkern 6.0mu4)$ if and only if there exists
a unique index $i_{0}\in\\{1,2,\ldots,k-1\\}$ such that $c_{i_{0}}=1$ and all
of the remaining coefficients except $c_{0}$ are equal to either $0$ or $2.$

A similar characterization could be presented in the case of $m=6$. Evidently,
as the value of $m$ grows, the descriptions like above become more and more
intricate. At the moment, we try to generalize the result obtained in
Corollary $6.3$. To do that let us fix positive integer $m>1$ and introduce
the following notation.

######  Definition 6.8.

For a fixed non-negative integers $m>1,k>0$ and $i\in\\{0,1,\ldots,\linebreak
m-1\\}$, $r_{\mathcal{M}}(i,m,k)$ is a number of those $n\mkern
4.0mu({\operator@font mod}\mkern 6.0mum^{k})$, which satisfy
$p_{\mathcal{M}}(n,k)\equiv i\mkern 4.0mu({\operator@font mod}\mkern 6.0mum)$,
that is

(6.4) $\displaystyle r_{\mathcal{M}}(i,m,k)=\\#\\{n\mkern
4.0mu({\operator@font mod}\mkern 6.0mum^{k}):p_{\mathcal{M}}(n,k)\equiv
i\mkern 4.0mu({\operator@font mod}\mkern 6.0mum)\\}.$

Undoubtedly, Theorem $6.2$ confirms that
$d(S_{\mathcal{M}}(i,m,k))=r_{\mathcal{M}}(i,m,k)/m^{k}$ for any parameters
$i,k$ and $m$. Further, it is clear that

$\displaystyle r_{\mathcal{M}}(i,m,1)=\begin{cases}0,&\text{if }i\neq 1,\\\
m,&\text{if }i=1.\end{cases}$

Hence, we may consider the case of $k>1.$ Due to Theorem $6.2$ the congruence

$\displaystyle p_{\mathcal{M}}(n,k)\equiv i\mkern 4.0mu({\operator@font
mod}\mkern 6.0mum)$

can be rearranged to

(6.5) $\displaystyle(c_{1}+1)(c_{2}+1)\ldots(c_{k-1}+1)\equiv
p_{\mathcal{M}}(n,k-1)(c_{k-1}+1)\equiv i\mkern 4.0mu({\operator@font
mod}\mkern 6.0mum),$

where the coefficients $c_{j}$ satisfy

$\displaystyle n\mkern 4.0mu({\operator@font mod}\mkern
6.0mum^{k})=c_{k-1}m^{k-1}+c_{k-2}m^{k-2}+\ldots+c_{1}m+c_{0}.$

If we treat $c_{k-1}+1$ as a variable, then $(6.5)$ has a solution if and only
if $\gcd(p_{\mathcal{M}}(n,k-1),m)\mid i$. Moreover, if the condition holds,
we get exactly $\gcd(p_{\mathcal{M}}(n,k-1),m)$ distinct solutions $\mkern
4.0mu({\operator@font mod}\mkern 6.0mum)$, and, since $\gcd(i,m)\mid i$ we
additionally obtain that $\gcd(p_{\mathcal{M}}(n,k-1),m)\mid\gcd(i,m)$. In
conclusion, we deduce a subsequent recurrence relation.

######  Proposition 6.9.

For fixed non-negative integers $k,m>1$ and $i\in\\{0,1,\ldots,\linebreak
m-1\\}$, the value $r_{\mathcal{M}}(i,m,k)$ may be expressed as

(6.6) $\displaystyle r_{\mathcal{M}}(i,m,k)=\sum_{\begin{subarray}{c}l=0\\\
\gcd(l,m)\mid\gcd(i,m)\end{subarray}}^{m-1}r_{\mathcal{M}}(l,m,k-1)\gcd(l,m).$

In addition, if $k=1$, then

$\displaystyle r_{\mathcal{M}}(i,m,1)=\begin{cases}0,&\text{if }i\neq 1\\\
m,&\text{if }i=1.\end{cases}$

Now, we deduce a few consequences of the relation $(6.6)$. First, we observe
that a number $i$ may be immediately replaced by $\gcd(i,m)$.

######  Corollary 6.10.

If $k,m>1$ and $i\in\\{0,1,\ldots,m-1\\}$ are arbitrary integers, then

$\displaystyle r_{\mathcal{M}}(i,m,k)=r_{\mathcal{M}}(\gcd(i,m),m,k).$

###### Proof.

Clearly, the sum in $(6.6)$ does not change, if we substitute $i$ by
$\gcd(i,m)$. ∎

######  Corollary 6.11.

The equality

$\displaystyle r_{\mathcal{M}}(i,m,2)=m$

holds for all $m>1$ and $i\in\\{0,1,\ldots,m-1\\}$.

###### Proof.

The sum in $(6.6)$ is reduced only to the case of $l=1$, and since
$r_{\mathcal{M}}(1,m,1)=m$, we obtain the equation from the statement, as
desired. ∎

Another one consequence is an alternative formula for
$r_{\mathcal{M}}(i,m,k)$. By Corollary $6.10$, we may assume without loss of
generality that $i\mid m$.

######  Corollary 6.12.

If $k>2,m>1$ and $i$ are positive integers such that $i\mid m$, then

$\displaystyle r_{\mathcal{M}}(i,m,k)=\sum_{l\mid
i}l\varphi(m/l)r_{\mathcal{M}}(l,m,k-1),$

where $\varphi$ denotes Euler’s totient function.

###### Proof.

Let us fix $i,k$ and $m$ as above. Proposition $6.9$ states that

$\displaystyle r_{\mathcal{M}}(i,m,k)$
$\displaystyle=\sum_{\begin{subarray}{c}l=0\\\ \gcd(l,m)\mid\
i\end{subarray}}^{m-1}r_{\mathcal{M}}(l,m,k-1)\gcd(l,m)$
$\displaystyle=\sum_{l\mid i}l\sum_{\begin{subarray}{c}j=1\\\
\gcd(lj,m)=l\end{subarray}}^{\frac{m}{l}}r_{\mathcal{M}}(jl,m,k-1).$

Due to Corollary $6.10$, $r_{\mathcal{M}}(jl,m,k-1)$ can be replaced by
$r_{\mathcal{M}}(l,m,k-1)$. Moreover, $\gcd(lj,m)=l\gcd(j,m/l)$. Thus,

$\displaystyle r_{\mathcal{M}}(i,m,k)=\sum_{l\mid
i}lr_{\mathcal{M}}(l,m,k-1)\sum_{\begin{subarray}{c}j=1\\\
\gcd(j,m/l)=1\end{subarray}}^{\frac{m}{l}}1=\sum_{l\mid
i}l\varphi(m/l)r_{\mathcal{M}}(l,m,k-1),$

so the proof is complete. ∎

It is worth to see, how the above corollary works in practice. Hence, let us
apply it and calculate $r_{\mathcal{M}}(i,m,k)$ for $m=6$.

######  Example 6.13.

For all positive integers $k\geqslant 2$, we have

$\displaystyle r_{\mathcal{M}}(i,6,k)=\begin{cases}3\cdot 2^{k-1},&\text{if
}i\in\\{1,5\\}\\\ 3\cdot 2^{k-1}(2^{k-1}-1),&\text{if }i\in\\{2,4\\}\\\
6\cdot(3^{k-1}-2^{k-1}),&\text{if }i=3.\end{cases}$

###### Proof.

By Corollary $6.11$, we can easily notice that the equality holds for $k=2$
and all the values of $i$. For $k>2$, let us first assume that $\gcd(i,6)=1,$
that is $i\in\\{1,5\\}$. Since
$r_{\mathcal{M}}(i,6,k)=r_{\mathcal{M}}(\gcd(i,6),6,k)$, it is enough to
compute $r_{\mathcal{M}}(1,6,k)$. Now, we may take advantage of Corollary
$6.12$ and deduce:

$\displaystyle r_{\mathcal{M}}(1,m,k)$
$\displaystyle=\varphi(6)r_{\mathcal{M}}(1,6,k-1)=\varphi^{2}(6)r_{\mathcal{M}}(1,6,k-2)=\ldots$
$\displaystyle=\varphi^{k-2}(6)r_{\mathcal{M}}(1,6,2)=6\cdot\varphi^{k-2}(6)=3\cdot
2^{k-1},$

so the proof is complete for $i\in\\{1,5\\}$. Next, we consider the case, in
which $\gcd(i,6)=2$. Once again Corollary $6.10$ provides that it is enough to
derive the formula for $r_{\mathcal{M}}(2,6,k)$. Clearly, by Corollary $6.12$
we obtain

$\displaystyle r_{\mathcal{M}}(2,6,k)$
$\displaystyle=\varphi(6)r_{\mathcal{M}}(1,6,k-1)+2\varphi(3)r_{\mathcal{M}}(2,6,k-1)=\varphi(6)r_{\mathcal{M}}(1,6,k-1)$
$\displaystyle\phantom{=}+2\varphi(3)\varphi(6)r_{\mathcal{M}}(1,6,k-2)+2^{2}\varphi^{2}(3)r_{\mathcal{M}}(2,6,k-3)=\ldots$
$\displaystyle=\varphi(6)r_{\mathcal{M}}(1,6,k-1)+2\varphi(3)\varphi(6)r_{\mathcal{M}}(1,6,k-2)+\ldots$
$\displaystyle\phantom{=}+2^{k-3}\varphi^{k-3}(3)\varphi(6)r_{\mathcal{M}}(1,6,2)+2^{k-2}\varphi^{k-2}(3)r_{\mathcal{M}}(2,6,2).$

Since $\varphi(3)=\varphi(6)=2$, $r_{\mathcal{M}}(2,6,2)=6$ and
$r_{\mathcal{M}}(1,6,j)=6\cdot\varphi^{j-2}(6)$ for all $2\leqslant j\leqslant
k-1$, we can rewrite $r_{\mathcal{M}}(2,6,k)$ in the following way

$\displaystyle r_{\mathcal{M}}(2,6,k)$ $\displaystyle=\varphi(6)\cdot
6\cdot\varphi^{k-3}(6)+2\varphi(3)\varphi(6)\cdot
6\cdot\varphi^{k-4}(6)+\ldots$
$\displaystyle\phantom{=}+2^{k-3}\varphi^{k-3}(3)\varphi(6)\cdot
6+2^{k-2}\varphi^{k-2}(3)\cdot 6$ $\displaystyle=6\cdot 2^{k-2}+6\cdot
2^{k-1}+\ldots+6\cdot 2^{2k-5}+6\cdot 2^{2k-4}$ $\displaystyle=6\cdot
2^{k-2}(2^{k-1}-1)=3\cdot 2^{k-1}(2^{k-1}-1),$

as required. Finally, we have to determine $r_{\mathcal{M}}(3,6,k)$. As
before, we apply Corollary $6.12$ and get

$\displaystyle r_{\mathcal{M}}(3,6,k)$
$\displaystyle=\varphi(6)r_{\mathcal{M}}(1,6,k-1)+3\varphi(2)r_{\mathcal{M}}(3,6,k-1)=\varphi(6)r_{\mathcal{M}}(1,6,k-1)$
$\displaystyle\phantom{=}+3\varphi(2)\varphi(6)r_{\mathcal{M}}(1,6,k-2)+3^{2}\varphi^{2}(2)r_{\mathcal{M}}(3,6,k-3)=\ldots$
$\displaystyle=\varphi(6)r_{\mathcal{M}}(1,6,k-1)+3\varphi(2)\varphi(6)r_{\mathcal{M}}(1,6,k-2)+\ldots$
$\displaystyle\phantom{=}+3^{k-3}\varphi^{k-3}(2)\varphi(6)r_{\mathcal{M}}(1,6,2)+3^{k-2}\varphi^{k-2}(2)r_{\mathcal{M}}(3,6,2)$

In order to conclude the final formula for $r_{\mathcal{M}}(3,6,k)$, we need
to make analogous observations like in the previous case and, additionally,
recall that $3^{k-1}-2^{k-1}=3^{k-2}+2\cdot 3^{k-3}+\ldots+2^{k-3}\cdot
3+2^{k-2}$. Afterward, we obtain

$\displaystyle r_{\mathcal{M}}(3,6,k)$ $\displaystyle=\varphi(6)\cdot
6\cdot\varphi^{k-3}(6)+3\varphi(2)\varphi(6)\cdot
6\cdot\varphi^{k-4}(6)+\ldots$
$\displaystyle\phantom{=}+3^{k-3}\varphi^{k-3}(2)\varphi(6)\cdot
6+3^{k-2}\varphi^{k-2}(2)\cdot 6$ $\displaystyle=6\cdot 2^{k-2}+6\cdot 3\cdot
2^{k-3}+\ldots+6\cdot 3^{k-3}\cdot 2+6\cdot 3^{k-2}$
$\displaystyle=6\cdot(3^{k-1}-2^{k-1}),$

and we finish the proof. ∎

Obviously, it would be more convenient to possess an explicit formula for
$r_{\mathcal{M}}(i,m,k)$. However, it is difficult to determine such an
expression in general. Nevertheless, in some special cases we are able to
obtain an effective formula for $r_{\mathcal{M}}(i,m,k)$.

######  Example 6.14.

Let $m,k>1$ be fixed positive integers. If $i\in\\{0,1,\ldots,m-1\\}$
satisfies $\gcd(i,m)=1$, then

$\displaystyle r_{\mathcal{M}}(i,m,k)=\varphi^{k-2}(m)m$

and, in particular,

$d(S_{\mathcal{M}}(i,m,k))=\varphi^{k-2}(m)/m^{k-1}.$

###### Proof.

Let $i,k$ and $m$ be as above. The statement is clear for $k=2$, by Corollary
$6.11$. Thus, we may assume that $k>2$. Now, Corollary $6.10$ and $6.12$
assert that

$\displaystyle
r_{\mathcal{M}}(i,m,k)=r_{\mathcal{M}}(1,m,k)=\varphi(m)r_{\mathcal{M}}(1,m,k-1).$

Therefore, $r_{\mathcal{M}}(i,m,k)=\varphi^{k-2}(m)m$ and
$d(S_{\mathcal{M}}(i,m,k))=\varphi^{k-2}(m)/m^{k-1}$, as required. ∎

We can easily observe that the above result agrees with both Corollary $6.3$
and Corollary $6.4$. Moreover, it may be significantly generalized by the
following theorem.

######  Theorem 6.15.

Let $i,k$ and $m$ be positive integers such that $k\geqslant 2$ and
$i\cdot{\text{rad}(i)}\mid m$. If the prime factorization of $i$ is given by
$i=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\ldots p_{s}^{\alpha_{s}},$ where
$s\in\mathbb{N}_{+}$, $p_{j}\in\mathbb{P}$ for each $j\in\\{1,2,\ldots,s\\}$
and $p_{j_{1}}\neq p_{j_{2}}$ for all $j_{1},j_{2}\in\\{1,2,\ldots,s\\}$ with
$j_{1}\neq j_{2}$, then

(6.7) $\displaystyle
r_{\mathcal{M}}(i,m,k)=m\varphi^{k-2}(m)\prod_{j=1}^{s}\binom{\alpha_{j}+k-2}{\alpha_{j}}.$

###### Proof.

Let $i,k$ and $m$ be as above. We want to compute the number of solutions
$n\mkern 4.0mu({\operator@font mod}\mkern 6.0mum^{k})$ of

$\displaystyle p_{\mathcal{M}}(n,k)\equiv
p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\ldots p_{s}^{\alpha_{s}}\mkern
4.0mu({\operator@font mod}\mkern 6.0mum).$

Hence, it is enough to find all $n\in\\{0,1,\ldots,m^{k}-1\\}$, which satisfy
the foregoing condition. Thus, let $n\in\\{0,1,\ldots,m^{k}-1\\}$. By Theorem
$6.2$, we may represent $n$ in base $m$ as

$\displaystyle n=c_{k-1}m^{k-1}+c_{k-2}m^{k-2}+\ldots+c_{1}m+c_{0},$

for some $c_{0},c_{1},\ldots c_{k-1}\in\\{0,1,\ldots,m-1\\}$; and determine
the number of solutions of

(6.8) $\displaystyle(c_{1}+1)(c_{2}+1)\ldots(c_{k-1}+1)\equiv
p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\ldots p_{s}^{\alpha_{s}}\mkern
4.0mu({\operator@font mod}\mkern 6.0mum).$

First, we can immediately notice that the congruence does not depend on
$c_{0},$ so we have $m$ possibilities to choose this element. Now, let us fix
an index $j\in\\{1,2,\ldots,s\\}$ and consider, in how many ways we may split
$p_{j}^{\alpha_{j}}$ between $c_{1}+1,c_{2}+1,\ldots,c_{k-1}+1$ in order to
obtain that

$p_{j}^{\beta_{j,1}}||c_{1}+1,\quad
p_{j}^{\beta_{j,2}}||c_{2}+1,\quad\ldots,\quad
p_{j}^{\beta_{j,k-1}}||c_{k-1}+1,$

where $\beta_{j,t}\in\mathbb{N}$ for each $t\in\\{1,2,\ldots,k-1\\}$ and

$\beta_{j,1}+\beta_{j,2}+\ldots+\beta_{j,k-1}=\alpha_{j}.$

The number of non-negative integer solutions of the above Diophantine equation
is the number of multisubsets of size $\alpha_{j}$ from a $k-1$-element set –
that is
$\binom{\alpha_{j}+(k-1)-1}{\alpha_{j}}=\binom{\alpha_{j}+k-2}{\alpha_{j}}.$
Further, let us set such a partition for all $j\in\\{1,2,\ldots,s\\}$ and put

$\displaystyle\gamma_{t}=p_{1}^{\beta_{1,t}}p_{2}^{\beta_{2,t}}\ldots
p_{s}^{\beta_{s,t}},$

for every $t\in\\{1,2,\ldots,k-1\\}$. Therefore, we can interchange the
congruence $(6.8)$ with

$\displaystyle\gamma_{1}x_{1}\gamma_{2}x_{2}\ldots\gamma_{k-1}x_{k-1}\equiv
p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\ldots p_{s}^{\alpha_{s}}\mkern
4.0mu({\operator@font mod}\mkern 6.0mum),$

where all $x_{t}$ are new unknowns such that each of them is $p_{j}-$free for
every $j\in\\{1,2,\ldots,s\\}$, $\gcd(x_{t},m)=1$ and $0<x_{t}<m/\gamma_{t}$
for $t\in\\{1,2,\ldots,k-1\\}$. There are exactly $\varphi(m/\gamma_{t})$
possible values of $x_{t}$ for each $t\in\\{1,2,\ldots,k-2\\}$. We arbitrarily
fix them and replace $\gamma_{k-1}x_{k-1}$ by $x$ to get

$\displaystyle Q\gamma_{1}\gamma_{2}\ldots\gamma_{k-2}x\equiv
p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\ldots p_{s}^{\alpha_{s}}\mkern
4.0mu({\operator@font mod}\mkern 6.0mum),$

where $Q=\prod_{t=1}^{k-2}x_{t}$. Since
$i=\gamma_{1}\gamma_{2}\ldots\gamma_{k-1}$ and $i|m$, we deduce that
$\gcd(Q\gamma_{1}\gamma_{2}\ldots\gamma_{k-2},m)=\gamma_{1}\gamma_{2}\ldots\gamma_{k-2}|i$.
Thus, the congruence has exactly $\gamma_{1}\gamma_{2}\ldots\gamma_{k-2}$
distinct solutions $\mkern 4.0mu({\operator@font mod}\mkern 6.0mum)$. Now, let
us fix $t\in\\{1,2,\ldots,k-2\\}$ and recall that Euler’s totient function
satisfies

$\varphi(ab)=\varphi(a)\varphi(b)\cdot\frac{\gcd(a,b)}{\varphi(\gcd(a,b))}\quad\text{and}\quad\frac{a}{\varphi(a)}=\frac{\text{rad}(a)}{\varphi(\text{rad}(a))},$

where $a$ and $b$ are arbitrary positive integers. Hence, the following
equalities

$\displaystyle\varphi(m)=\varphi\left(\frac{m}{\gamma_{t}}\cdot\gamma_{t}\right)=\varphi\left(\frac{m}{\gamma_{t}}\right)\varphi(\gamma_{t})\cdot\frac{\gcd(m/\gamma_{t},\gamma_{t})}{\varphi(\gcd(m/\gamma_{t},\gamma_{t}))}$

hold. Since $\gamma_{t}\cdot\text{rad}(i)|i\cdot\text{rad}(i)|m$, we deduce
that $\text{rad}(\gcd(m/\gamma_{t},\gamma_{t}))=\text{rad}(\gamma_{t})$.
Applying the remaining property of $\varphi$ for the last two terms of the
above expression together with the equality from the previous sentence, we
obtain

$\displaystyle\varphi(\gamma_{t})\cdot\frac{\gcd(m/\gamma_{t},\gamma_{t})}{\varphi(\gcd(m/\gamma_{t},\gamma_{t}))}=\frac{\gamma_{t}\varphi(\text{rad}(\gamma_{t}))}{\text{rad}(\gamma_{t})}\cdot\frac{\text{rad}(\gamma_{t})}{\varphi(\text{rad}(\gamma_{t}))}=\gamma_{t}.$

Therefore, $\varphi(m/\gamma_{t})\gamma_{t}=\varphi(m)$ for all
$t\in\\{1,2,\ldots,k-2\\}$.

Summing up, we may select $c_{0}$ in $m$ ways; split each $p_{j}^{\alpha_{j}}$
between $c_{1}+1,c_{2}+1,\ldots,c_{k-1}+1$ in
$\binom{\alpha_{j}+k-2}{\alpha_{j}}$ ways for every $j\in\\{1,2,\ldots,s\\}$;
and for a fixed such a partition, determine exactly $\varphi^{k-2}(m)$
distinct solutions of the congruence $(6.8)$. Hence, we finally get that

$\displaystyle
r_{\mathcal{M}}(i,m,k)=m\binom{\alpha_{1}+k-2}{\alpha_{1}}\binom{\alpha_{2}+k-2}{\alpha_{2}}\ldots\binom{\alpha_{s}+k-2}{\alpha_{s}}\varphi^{k-2}(m),$

which completes the proof of Theorem $6.15$. ∎

Instead of determining similar formulae for such values of $i$ that
$\gcd(i,m)>1$ but $i\cdot\text{rad}(i)\nmid m$ — which becomes more and more
complex task — we focus now on estimation the limit of
$d(S_{\mathcal{M}}(0,m,k))$ as $k$ goes to infinity.

######  Proposition 6.16.

The equality

$\displaystyle\lim_{k\to\infty}d(S_{\mathcal{M}}(0,m,k))=1$

holds for any positive integer $m>1$.

###### Proof.

Let $k,m\in\mathbb{N}_{\geqslant 2}$ be fixed. By Theorem $6.2$ we get

$\displaystyle\frac{\\#\\{n\mkern 4.0mu({\operator@font mod}\mkern
6.0mum^{k}):p_{\mathcal{M}}(n,k)\not\equiv 0\mkern 4.0mu({\operator@font
mod}\mkern 6.0mum)\\}}{m^{k}}$ $\displaystyle=$
$\displaystyle\frac{\\#\\{n\mkern 4.0mu({\operator@font mod}\mkern
6.0mum^{k}):(c_{1}+1)(c_{2}+2)\ldots(c_{k-1}+1)\not\equiv 0\mkern
4.0mu({\operator@font mod}\mkern 6.0mum)\\}}{m^{k}},$

where the coefficients $c_{j}$ satisfy

$\displaystyle n\mkern 4.0mu({\operator@font mod}\mkern
6.0mum^{k})=c_{k-1}m^{k-1}+c_{k-2}m^{k-2}+\ldots+c_{1}m+c_{0},$

that is a representation $n\mkern 4.0mu({\operator@font mod}\mkern
6.0mum^{k})$ in base $m$. We can choose $c_{0}$ in $m$ ways and $c_{j}$ in at
most $m-1$ ways for $j\in\\{1,2,\ldots,k-1\\}$. Thus,

$\displaystyle\frac{\\#\\{n\mkern 4.0mu({\operator@font mod}\mkern
6.0mum^{k}):(c_{1}+1)(c_{2}+2)\ldots(c_{k-1}+1)\not\equiv 0\mkern
4.0mu({\operator@font mod}\mkern
6.0mum)\\}}{m^{k}}\leqslant\frac{m(m-1)^{k-1}}{m^{k}},$

which goes to zero as $k\to\infty$. Finally, we conclude that

$\displaystyle 1\geqslant\lim_{k\to\infty}d(S_{\mathcal{M}}(0,m,k))\geqslant
1-\lim_{k\to\infty}\frac{m(m-1)^{k-1}}{m^{k}}=1,$

which completes the proof. ∎

##  7\. Numerical computations and open problems

In the final section we present results of numerical computations of the
density of $\\{n\in\mathbb{N}:p_{\mathcal{A}}(n,k)\not\equiv 0\mkern
4.0mu({\operator@font mod}\mkern 6.0mum)\\}$ for some sequences $\mathcal{A}$
and values of parameter $m$. Theorems $3.2$ and $3.3$ state that the function
$p_{\mathcal{A}}(n,k)\mkern 4.0mu({\operator@font mod}\mkern 6.0mum)$ is
periodic on $n$. Thus, we can reduce our consideration to a finite set. The
following computations carried out in Wolfram Mathematica [22] give us exact
values of densities. First, if $\mathcal{A}_{2}=(n^{2})_{n\in\mathbb{N}_{+}}$,
then we find

$k$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$
---|---|---|---|---|---|---|---|---|---|---
$d(S_{\mathcal{A}_{2}}(1,2,k))$ | $1$ | $\frac{1}{2}$ | $\frac{13}{36}$ | $\frac{37}{144}$ | $\frac{1}{2}$ | $\frac{299}{600}$ | $\frac{253}{504}$ | $\frac{14113}{28224}$ | $\frac{317311}{635040}$ | $\frac{264659}{529200}$

Table 1. The values of $d(S_{\mathcal{A}_{2}}(1,2,k))$ for $1\leqslant
k\leqslant 10$.

Moreover let us present results for $m=3,4,5$ in the table below, in which the
densities for distinct values of $m$ are separated by double lines.

$k$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$
---|---|---|---|---|---|---|---|---
$d(S_{\mathcal{A}_{2}}(0,3,k))$ | $0$ | $\frac{1}{3}$ | $\frac{5}{12}$ | $\frac{17}{36}$ | $\frac{587}{1800}$ | $\frac{361}{1080}$ | $\frac{58741}{176400}$ | $\frac{22061}{66150}$
$d(S_{\mathcal{A}_{2}}(1,3,k))$ | $1$ | $\frac{1}{3}$ | $\frac{11}{36}$ | $\frac{19}{72}$ | $\frac{59}{180}$ | $\frac{719}{2160}$ | $\frac{58711}{176400}$ | $\frac{44089}{132300}$
$d(S_{\mathcal{A}_{2}}(2,3,k))$ | $0$ | $\frac{1}{3}$ | $\frac{5}{18}$ | $\frac{19}{72}$ | $\frac{623}{1800}$ | $\frac{719}{2160}$ | $\frac{14737}{44100}$ | $\frac{44089}{132300}$
$d(S_{\mathcal{A}_{2}}(0,4,k))$ | $0$ | $\frac{1}{4}$ | $\frac{13}{36}$ | $\frac{107}{288}$ | $\frac{179}{720}$ | $\frac{113}{450}$ | $\frac{17551}{70560}$ | $\frac{352999}{1411200}$
$d(S_{\mathcal{A}_{2}}(1,4,k))$ | $1$ | $\frac{1}{4}$ | $\frac{5}{24}$ | $\frac{37}{288}$ | $\frac{21}{80}$ | $\frac{299}{1200}$ | $\frac{4433}{17640}$ | $\frac{14113}{56448}$
$d(S_{\mathcal{A}_{2}}(2,4,k))$ | $0$ | $\frac{1}{4}$ | $\frac{5}{18}$ | $\frac{107}{288}$ | $\frac{181}{720}$ | $\frac{451}{1800}$ | $\frac{5863}{23520}$ | $\frac{117517}{470400}$
$d(S_{\mathcal{A}_{2}}(3,4,k))$ | $0$ | $\frac{1}{4}$ | $\frac{11}{72}$ | $\frac{37}{288}$ | $\frac{19}{80}$ | $\frac{299}{1200}$ | $\frac{737}{2940}$ | $\frac{14113}{56448}$
$d(S_{\mathcal{A}_{2}}(0,5,k))$ | $0$ | $\frac{1}{5}$ | $\frac{41}{180}$ | $\frac{17}{60}$ | $\frac{56}{225}$ | $\frac{1}{5}$ | $\frac{3917}{19600}$ | $\frac{352327}{1764000}$
$d(S_{\mathcal{A}_{2}}(1,5,k))$ | $1$ | $\frac{1}{5}$ | $\frac{1}{5}$ | $\frac{73}{360}$ | $\frac{281}{1800}$ | $\frac{1}{5}$ | $\frac{8843}{44100}$ | $\frac{706799}{3528000}$
$d(S_{\mathcal{A}_{2}}(2,5,k))$ | $0$ | $\frac{1}{5}$ | $\frac{13}{60}$ | $\frac{7}{45}$ | $\frac{199}{900}$ | $\frac{1}{5}$ | $\frac{11801}{58800}$ | $\frac{117479}{588000}$
$d(S_{\mathcal{A}_{2}}(3,5,k))$ | $0$ | $\frac{1}{5}$ | $\frac{1}{6}$ | $\frac{7}{45}$ | $\frac{377}{1800}$ | $\frac{1}{5}$ | $\frac{1459}{7350}$ | $\frac{117479}{588000}$
$d(S_{\mathcal{A}_{2}}(4,5,k))$ | $0$ | $\frac{1}{5}$ | $\frac{17}{90}$ | $\frac{73}{360}$ | $\frac{37}{225}$ | $\frac{1}{5}$ | $\frac{8839}{44100}$ | $\frac{706799}{3528000}$

Table 2. The values of $d(S_{\mathcal{A}_{2}}(i,m,k))$ for $3\leqslant
m\leqslant 5,$ $0\leqslant i\leqslant m-1$ and $1\leqslant k\leqslant 8$.

On the one hand, the foregoing instances can suggest us the following bold
question, which agrees with computational results obtained by Ulas in [21].

######  Question 7.1.

Let $\mathcal{A}_{d}=(n^{d})_{n\in\mathbb{N}_{+}}$ for
$d\in\mathbb{N}_{\geqslant 2}$. Does the following equality hold

$\displaystyle\lim_{k\to\infty}\lim_{N\to\infty}\frac{\\#\\{n\leqslant
N:p_{\mathcal{A}_{d}}(n,k)\equiv i\mkern 4.0mu({\operator@font mod}\mkern
6.0mum)\\}}{N}=\frac{1}{m},$

for any arbitrarily fixed parameters $m\geqslant 2$ and
$i\in\\{0,1,\ldots,m-1\\}$?

Our numerical data suggest that, if $2|k$, then
$d(S_{\mathcal{A}_{2}}(j,m,k))=\linebreak d(S_{\mathcal{A}_{2}}(m-j,m,k))$ for
all $j\in\\{1,2,\ldots,m-1\\}$ and $m\in\\{2,3,4,5\\}$. Therefore, the
following general question arises.

######  Question 7.2.

For a given positive integer $d$, let
$\mathcal{A}_{d}=(n^{d})_{n\in\mathbb{N}_{+}}$. Does the formula

$\displaystyle d(S_{A_{d}}(j,m,k))=d(S_{A_{d}}(m-j,m,k))$

hold for any arbitrarily fixed parameters $k,m\geqslant 2$ and
$j\in\\{1,2,\ldots,m-1\\}$ such that $2\mid k$?

Now, we focus only on the odd density of the function $p_{\mathcal{A}}(n,k)$
for some special cases of the sequence $\mathcal{A}$. Consequently, let us
denote by

$\mathcal{T}=\left(\frac{n(n+1)}{2}\right)_{n\in\mathbb{N}_{+}},\hskip
28.45274pt\mathcal{P}=\left(\frac{3n^{2}-n}{2}\right)_{n\in\mathbb{N}_{+}},\hskip
28.45274pt\mathcal{H}=\left(2n^{2}-n\right)_{n\in\mathbb{N}_{+}}$

sequences of positive triangular, pentagonal and hexagonal numbers,
respectively. Additionally, we assume that
$\mathcal{S}=((n-1)^{2}+1)_{n\in\mathbb{N}_{+}}$, that is a collection of
square numbers increased by one. The next table demonstrates our results of
computations.

$k$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$
---|---|---|---|---|---|---|---|---
$d(S_{\mathcal{T}}(1,2,k))$ | $1$ | $\frac{1}{2}$ | $\frac{1}{4}$ | $\frac{2}{5}$ | $\frac{7}{20}$ | $\frac{129}{280}$ | $\frac{11}{24}$ | $\frac{2453}{5040}$
$d(S_{\mathcal{P}}(1,2,k))$ | $1$ | $\frac{1}{2}$ | $\frac{2}{5}$ | $\frac{219}{440}$ | $\frac{1}{2}$ | $\frac{713}{1496}$ | $\frac{1867}{3740}$ | $\frac{516287}{1032240}$
$d(S_{\mathcal{H}}(1,2,k))$ | $1$ | $\frac{1}{2}$ | $\frac{7}{20}$ | $\frac{83}{168}$ | $\frac{1}{2}$ | $\frac{2311}{4620}$ | $\frac{22559}{45045}$ | $\frac{39931}{80080}$
$d(S_{\mathcal{S}}(1,2,k))$ | $1$ | $\frac{1}{2}$ | $\frac{7}{20}$ | $\frac{3}{10}$ | $\frac{149}{340}$ | $\frac{1}{2}$ | $\frac{81851}{163540}$ | $\frac{102196}{204425}$

Table 3. The values of $d(S_{\mathcal{A}}(1,2,k))$ for
$\mathcal{A}\in\\{\mathcal{T,P,H,S}\\}$ and $1\leqslant k\leqslant 8$.

These results can misled us to believe that

$\displaystyle\lim_{k\to\infty}\lim_{N\to\infty}\frac{\\#\\{n\leqslant
N:p_{\mathcal{A}}(n,k)\equiv 1\mkern 4.0mu({\operator@font mod}\mkern
6.0mu2)\\}}{N}=\frac{1}{2},$

for any arbitrarily fixed sequence $\mathcal{A}$ of positive integers such
that $\gcd\mathcal{A}=1$. However, in Sec. 6 we point out that for binary
partitions this limit goes to zero. Nevertheless, we can add another one
assumption, which eliminate counterexamples from the previous section. We
state the following open question.

######  Question 7.3.

Let $\mathcal{A}$ be a fixed sequence of positive integers such that
$\gcd\mathcal{A}=1$ and the set of prime divisors of $\mathcal{A}$ is
infinite. Does the equality

$\displaystyle\lim_{k\to\infty}\lim_{N\to\infty}$
$\displaystyle\frac{\\#\\{n\leqslant N:p_{\mathcal{A}}(n,k)\equiv 1\mkern
4.0mu({\operator@font mod}\mkern 6.0mu2)\\}}{N}=\frac{1}{2}$

hold?

Finally, we may ask about both the possibility of achieving lower bound of the
odd density and the existence of a special family of sequences such that the
above equality holds for its elements.

######  Question 7.4.

Is it possible to find such a sequence $\mathcal{A}$ of positive integers that
$\gcd\mathcal{A}=1$ and

$\displaystyle\lim_{N\to\infty}$ $\displaystyle\frac{\\#\\{n\leqslant
N:p_{\mathcal{A}}(n,k)\equiv 1\mkern 4.0mu({\operator@font mod}\mkern
6.0mu2)\\}}{N}=\frac{1}{\sum_{i=1}^{k}a_{i}}$

for some $k\geqslant 1$?

######  Question 7.5.

Is it possible to determine an infinite family of sequences $\mathfrak{A}$
such that for each $\mathcal{A}\in\mathfrak{A}$, $\mathcal{A}$ is a sequence
of positive integers, $\gcd\mathcal{A}=1$ and

$\displaystyle\lim_{k\to\infty}\lim_{N\to\infty}$
$\displaystyle\frac{\\#\\{n\leqslant N:p_{\mathcal{A}}(n,k)\equiv 1\mkern
4.0mu({\operator@font mod}\mkern 6.0mu2)\\}}{N}=\frac{1}{2}?$

## Acknowledgements

The author would like to thank Maciej Ulas and Piotr Miska for their time,
effort and guidance.

## References

  * [1] G. Almkvist, Partitions with parts in a finite set and with parts outside a finite set, Experiment. Math. 11 (2002) 449–456.
  * [2] G. E. Andrews, Congruence properties of the $m-$ary partition function, J. Number Theory 3 (1971) 104–110.
  * [3] G. E. Andrews, The Theory of Partitions, the Encyclopedia of Mathematics and Its Applications Series, Addison-Wesley, New York (1976), reissued, Cambridge University Press, New York (1998).
  * [4] G. E. Andrews, K.Eriksson, Integer Partitions, Cambridge University Press, Cambridge, 2004.
  * [5] G.E. Andrews, A.S. Fraenkel, J.A. Sellers, Characterizing the Number of $m-$ary Partitions Modulo $m$, Am.Math. Mon. 122(9), 880–885 (2015).
  * [6] A. O. L. Atkin, Proof of conjecture of Ramanujan, Glasgow Math. J. 8 (1967), 14-32.
  * [7] R. F. Churchhouse, Congruence properties of the binary partition function, Proc. Cambridge Philos. Soc. 66 (1969) 371–376.
  * [8] R. F. Churchhouse, Binary partitions, in Computers in Number Theory, Eds. A. O. L. Atkin and B. J. Birch. Academic Press, London, 1971.
  * [9] H. Gupta, A simple proof of the Churchhouse conjecture concerning binary partitions, Indian J. Pure Appl. Math. 3 (1972) 791–794.
  * [10] H. Gupta, On $m-$ary partitions, Proc. Cambridge Philos. Soc. 71 (1972) 343–345.
  * [11] K. Karhadkar, Parity of the partition function $p(n,k)$, Int. J. Number Theory 15 (2019), no. 4, 799-805.
  * [12] Y. H. Kwong, Minimum periods of partition functions modulo $M$, Util. Math. 35, 3-8 (1989).
  * [13] Y. H. Kwong, Periodicities of a class of infinite integer sequences modulo $M$, J. Number Theory 31, 64-79 (1989).
  * [14] M. B. Nathanson, Partitions with parts in a finite set, Proc. Amer. Math. Soc. 128 (2000) 1269–1273.
  * [15] A. Nijenhuis, H. S. Wilf Periodicities of partitions functions and Stirling numbers modulo $p$, J. Number Theory 25, 308-312 (1987).
  * [16] K. Ono Distribution of the partition function modulo $m$, Annals of Math. 151 (2000), 293-307.
  * [17] S. Ramanujan, Collected Papers, Cambridge University Press, London (1927), reprinted: AMS, Chelsea (2000) with new preface and extensive commentary by B. Berndt.
  * [18] Ø. J. Rødseth, Some arithmetical properties of $m-$ary partitions, Proc. Camb. Philos. Soc. 68, 447–453 (1970).
  * [19] Ø. J. Rødseth and J. A. Sellers, On m-ary partition function congruences: A fresh look at a past problem, J. Number Theory 87, 270–281 (2001).
  * [20] Ø. J. Rødseth and J. A. Sellers, Partitions With Parts In A Finite Set, Int. J. Number Theory 2 (2006), no. 3, 455–468.
  * [21] M. Ulas, Some observations and speculations on partitions into $d-$th powers, Bull. Aust. Math. Soc., to appear.
  * [22] Wolfram Research, Inc., Mathematica, Version 11.3, Champaign, IL, 2018.