For how many $n < N$ is $d(n) \equiv 0 \pmod p$?

Question

I was researching about integer partitions and came across the equation $d(n) \equiv 0 \pmod p$. Here, $d(n)$ is the number of factors of $n$ and $p$ is a fixed prime. How many solutions does this have when $n<N$? I thought this might be solvable if I factor $n$, but couldn't solve it.

All I got was that when $p=2$, this is $N-\sqrt{N}$ (a number has an odd number of factors exactly when it's a perfect square).

How should I go from here?

Also, is there a solution to the same problem but with $\sigma(n)$?

Answer 1

Although this is not a complete answer, it might be useful to consider as a technique.

First of all, if $n=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot ... \cdot p_k^{\alpha_k}$ (prime factorisation of $n$), then $d(n)=(\alpha_1+1)(\alpha_2+1)...(\alpha_k+1)$, thus $$d(n)\equiv 0 \pmod{p} \iff \exists \alpha_i, i\in \{1,..,k\}: p \mid \alpha_i+1 \tag{1}$$

---

Proposition 1. There are no solutions for $N<2^{p-1}$.

From $(1)$ we have $\alpha_i=p\cdot t -1$ and because $\alpha_i \geq 1$ then $t \geq 1$ or $\alpha_i \geq p-1$ and $n\geq p_i^{\alpha_i}\geq 2^{p-1}$. As a result, $N\geq 2^{p-1}$, otherwise - there are no solutions.

---

Now, with more details:

• $\color{red}{2}^{p-1}\times 1, 2^{p-1}\times 3, 2^{p-1}\times 5, 2^{p-1}\times 7, 2^{p-1}\times 9, ..., 2^{p-1}\times n_2 < N$ or $$1<3<5<7<9<...<n_2<\frac{N}{2^{p-1}}$$ which are all the odd numbers $<\frac{N}{2^{p-1}}$, which is $\color{blue}{\approx\frac{N}{2^{p-1}}-\frac{N}{2\cdot2^{p-1}}}$.
• and so on for $2^{p\cdot t-1}=\color{red}{2^{p(t-1)}}\times 2^{p-1}$ to have $\color{blue}{\approx\frac{N}{2^{p(t-1)}\cdot 2^{p-1}}-\frac{N}{2\cdot 2^{p(t-1)}\cdot 2^{p-1}}}$
• $\color{red}{3}^{p-1}\times 1, 3^{p-1}\times 2, 3^{p-1}\times 4, 3^{p-1}\times 5, 3^{p-1}\times 7, ..., 3^{p-1}\times n_3 < N$ or $$1<2<4<5<7<8<...<n_3<\frac{N}{3^{p-1}}$$ or all the positive integers $<\frac{N}{3^{p-1}}$ not divisible by $3$, $\color{blue}{\approx \frac{N}{3^{p-1}}-\frac{N}{3\cdot3^{p-1}}}$
• and so on for $3^{p\cdot t-1}=\color{red}{3^{p(t-1)}}\times 3^{p-1}$ to have $\color{blue}{\approx\frac{N}{3^{p(t-1)}\cdot 3^{p-1}}-\frac{N}{3\cdot 3^{p(t-1)}\cdot 3^{p-1}}}$
• $\color{red}{5}^{p-1}\times 1, 5^{p-1}\times 2, 5^{p-1}\times 3, 5^{p-1}\times 4, 5^{p-1}\times 6, ..., 5^{p-1}\times n_5 < N$ or $$1<2<3<4<6<7<8<9<11<...<n_5<\frac{N}{5^{p-1}}$$ or all the positive integers $<\frac{N}{5^{p-1}}$ not divisible by $5$, $\color{blue}{\approx \frac{N}{5^{p-1}}-\frac{N}{5\cdot5^{p-1}}}$
• and so on for $5^{p\cdot t-1}=\color{red}{5^{p(t-1)}}\times 5^{p-1}$ to have $\color{blue}{\approx\frac{N}{5^{p(t-1)}\cdot 5^{p-1}}-\frac{N}{5\cdot 5^{p(t-1)}\cdot 5^{p-1}}}$
• and so on for $\color{red}{7}, \color{red}{11}, \color{red}{13}, ...$ i.e. primes.

This starts nicely to shape into something like

$$\sum\limits_{q-\text{prime}} \left( \sum\limits_{t=1} \left \lfloor \frac{(q-1)N}{q^{t\cdot p}} \right \rfloor \right) \tag{2}$$ But, there is a problem. For instance in the sequence for $\color{red}{2}$ we have $2^{p-1}\times 9$ and the sequence for $\color{red}{3}$ we have $3^{p-1}\times 4$. Depending on $N$, the sequence for $\color{red}{2}$ may contain $2^{p-1}\times 3^{p-1}$ and the sequence for $\color{red}{3}$ we have $3^{p-1}\times 2^{p-1}$. So we can have overlaps, leading to applying inclusion-exclusion principle which complicates the things. At least, the number of solutions should not exceed $(2)$.

Answer 2

I don't think this is easy. The integers $n$ with $d(n)\equiv0\bmod3$ are tabulated at http://oeis.org/A059269. It is mentioned there that Charles R Greathouse has conjectured that the $n$th term in the sequence is asymptotic to $kn$, where $$k = \left(1 - \prod_p\left(1 - {p-1\over p^{3k}}\right)\right)^{-1} = 3.743455\dots$$