Results 1 to 2 of 2

Thread: Average number of divisors of a certain type

  1. #1
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    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)$.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    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) -
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Number of positive divisors of n
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: Aug 17th 2011, 11:04 AM
  2. divisors of a number
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: Apr 8th 2010, 08:34 AM
  3. Replies: 2
    Last Post: Dec 18th 2008, 05:28 PM
  4. Number of odd divisors
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Sep 17th 2008, 07:00 AM
  5. number of divisors
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 15th 2008, 08:34 PM

Search Tags


/mathhelpforum @mathhelpforum