# Thread: Average number of divisors of a certain type

1. ## Average number of divisors of a certain type

This problem is my own invention. I hope you enjoy it.

Suppose the infinite set $\displaystyle S$ has zero density in $\displaystyle \mathbb{N}$ (so that the proportion of elements of $\displaystyle S$ less than $\displaystyle n$ goes to 0 as $\displaystyle n \rightarrow \infty$).

Let $\displaystyle \omega(n)$ be the number of elements of $\displaystyle S$ which divide $\displaystyle n$.

Show that $\displaystyle \frac{1}{n}\sum_{j=1}^n\omega(j) = \sum_{s \in S, s\leq n}\frac{1}{s} + O(1)$.

For instance the average number of prime divisors of $\displaystyle 1,2,...,n$ is asymptotically equal to $\displaystyle \sum_{p\leq n}\frac{1}{p}$. The average number of square divisors is asymptotically equal to $\displaystyle \zeta(2)$.

2. Simply note that in the sum $\displaystyle \sum\limits_{k = 1}^n {\omega \left( k \right)}$ each $\displaystyle s\in S$ is counted as many times as multiples it has in $\displaystyle \left\{ {1,...,n} \right\}$ , which is exactly: $\displaystyle \left\lfloor {\tfrac{n} {s}} \right\rfloor$.

Thus: $\displaystyle \sum\limits_{k = 1}^n {\omega \left( k \right)} = \sum\limits_{s \in S} {\left\lfloor {\tfrac{n} {s}} \right\rfloor }$

Let $\displaystyle S_n= \left\{ {s \in S/1 \leqslant s \leqslant n} \right\}$ then of course: $\displaystyle \sum\limits_{s \in S} {\left\lfloor {\tfrac{n} {s}} \right\rfloor } = \sum\limits_{s \in S_n } {\left\lfloor {\tfrac{n} {s}} \right\rfloor }$ . By the definition of the floor function: $\displaystyle \sum\limits_{s \in S_n } {\left\lfloor {\tfrac{n} {s}} \right\rfloor } \leqslant \sum\limits_{s \in S_n } {\tfrac{n} {s}} < \sum\limits_{s \in S_n } {\left( {\left\lfloor {\tfrac{n} {s}} \right\rfloor + 1} \right)}$

Hence: $\displaystyle \sum\limits_{k = 1}^n {\omega \left( k \right)} \leqslant n \cdot \sum\limits_{s \in S_n } {\tfrac{1} {s}} < \sum\limits_{k = 1}^n {\omega \left( k \right)} + \left| {S_n } \right|$ $\displaystyle \therefore \left| {\sum\limits_{s \in S_n } {\tfrac{1} {s}} - \tfrac{1} {n} \cdot \sum\limits_{k = 1}^n {\omega \left( k \right)} } \right| < \tfrac{1} {n} \cdot \left| {S_n } \right| \leq 1$ and assertion is proven. $\displaystyle \square$

- If we also had $\displaystyle \frac{{\left| {S_n } \right|}} {n} \to 0$ then $\displaystyle \left| {\sum\limits_{s \in S_n } {\tfrac{1} {s}} - \tfrac{1} {n} \cdot \sum\limits_{k = 1}^n {\omega \left( k \right)} } \right| = o\left( 1 \right)$ (little O) -