Average number of divisors of a certain type

**Bruno J.** · August 18th 2009, 08:00 AM

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

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

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

Show that $\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 $1,2,...,n$ is asymptotically equal to $\sum_{p\leq n}\frac{1}{p}$ . The average number of square divisors is asymptotically equal to $\zeta(2)$ .

**PaulRS** · August 18th 2009, 10:17 AM

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

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

Let $S_n= \left\{ {s \in S/1 \leqslant s \leqslant n} \right\} $ then of course: $ \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: $ \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: $ \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| $ $ \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. $\square$

- If we also had $ \frac{{\left| {S_n } \right|}} {n} \to 0 $ then $ \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) -

Thread: Average number of divisors of a certain type

LinkBack

Thread Tools

Display

Average number of divisors of a certain type

Similar Math Help Forum Discussions

Number of positive divisors of n

divisors of a number

Number Theory type of problem--need help understanding number relationships. yikes.

Number of odd divisors

number of divisors

Search Tags