Results 1 to 2 of 2

Math Help - 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 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).
    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 <br />
\sum\limits_{k = 1}^n {\omega \left( k \right)} <br />
each s\in S is counted as many times as multiples it has in <br />
\left\{ {1,...,n} \right\}<br />
, which is exactly: <br />
\left\lfloor {\tfrac{n}<br />
{s}} \right\rfloor <br />
.

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

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

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

    - If we also had <br />
\frac{{\left| {S_n } \right|}}<br />
{n} \to 0<br />
then <br />
\left| {\sum\limits_{s \in S_n } {\tfrac{1}<br />
{s}}  - \tfrac{1}<br />
{n} \cdot \sum\limits_{k = 1}^n {\omega \left( k \right)} } \right| = o\left( 1 \right)<br />
(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: August 17th 2011, 11:04 AM
  2. divisors of a number
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: April 8th 2010, 08:34 AM
  3. Replies: 2
    Last Post: December 18th 2008, 05:28 PM
  4. Number of odd divisors
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: September 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