Results 1 to 8 of 8

Math Help - Number Theoretic Function t(n) or "tao" Proof

  1. #1
    Newbie
    Joined
    Oct 2011
    Posts
    7

    Number Theoretic Function t(n) or "tao" Proof

    t(n) = number of positive divisors of n

    For n => 1, prove that t(n) <= 2sqrt(n)

    Hint: If d | n, then one of d or n/d is less than or equal to sqrt(n).

    I do not know where to start with this problem. This is a homework question so I just need some assistance getting started with this problem. Also, I'm not sure how to use the hint in this problem. Thanks for your help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485

    Re: Number Theoretic Function t(n) or "tao" Proof

    If you don't know how to handle a problem, you should try to look at a few examples first (and in this case, see how the hint plays a role in the example).

    Let's take a look at the problem for n=60. We'd like to count up the number of divisors for 60. We can just use the "elementary school" method, by looking at pairs of divisors (we get one "big" and one "small): 1 and 60, 2 and 30, 3 and 20, and so on. When can we stop checking? We stop at \lfloor \sqrt{60}\rfloor=7, since 8 and its corresponding "big" divisor would exceed 60. (In other words, they would have to multiply to 64 or more.) So with respect to the original problem, if we want to count up the divisors, we only need to find the divisors less that \sqrt{60} and double them (since everything comes in pairs). In this case, there are 12 divisors, which is less that 2 \sqrt{60}.

    Can you see how to apply this for the general n?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2011
    Posts
    7

    Re: Number Theoretic Function t(n) or "tao" Proof

    Ok, that makes sense. So here is what I'm thinking: Clearly, the result holds for prime numbers of n since t(n) = 2 if n is prime and 2 <= 2sqrt(n) holds for any prime n. Thus, if n is composite, then n = d*e for some integers d and e. Either d <= sqrt(n) or n/d = e <= sqrt(n) meaning that one of these divisors is less than or equal to sqrt(n). Then since divisors come in pairs, there are t(n)/2 many divisors each less than or equal to sqrt(n). But then, how would I show that t(n)/2 <= sqrt(n)? Now, this part I'm stuck on.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485

    Re: Number Theoretic Function t(n) or "tao" Proof

    You're almost there. You only have to consider the worst case scenario: maybe all of the numbers less than or equal to \sqrt{n} are divisors. (By the way, can you find an example where this happens?) Then, \tau(n)/2=\sqrt{n}. Otherwise, the number of divisors is less than that: \tau(n)/2<\sqrt{n}. In summary, we can say \tau(n)/2\leq \sqrt{n}, which gives the result.

    How does that sound?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,150
    Thanks
    591

    Re: Number Theoretic Function t(n) or "tao" Proof

    Quote Originally Posted by roninpro View Post
    You're almost there. You only have to consider the worst case scenario: maybe all of the numbers less than or equal to \sqrt{n} are divisors. (By the way, can you find an example where this happens?) Then, \tau(n)/2=\sqrt{n}. Otherwise, the number of divisors is less than that: \tau(n)/2<\sqrt{n}. In summary, we can say \tau(n)/2\leq \sqrt{n}, which gives the result.

    How does that sound?
    oh, oh i know this one! 6, right? or is it 12?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Oct 2011
    Posts
    7

    Re: Number Theoretic Function t(n) or "tao" Proof

    I'm having trouble making the connection that t(n)/2 <= sqrt(n). I see that there are t(n)/2 many divisors less than sqrt(n) but I don't see how I can determine that t(n)/2 itself is less than or equal to sqrt(n).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,150
    Thanks
    591

    Re: Number Theoretic Function t(n) or "tao" Proof

    suppose n is a perfect square. then n has exactly one divisor that occurs as its own quotient. all the others occur in pairs, one is less than √n, and the other is greater than √n.

    therefore, in this case τ(n) ≤ 2(√n-1) + 1 = 2√n - 1 < 2√n.

    on the other hand, suppose that n is not a perfect square. then all divisors of n occur in pairs, one is less than √n, one is greater than √n.

    if k is the greatest integer less than √n, then τ(n) ≤ 2k < 2√n

    the pairing we are making, is pairing d with n/d, for each divisor d ≤ √n.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Oct 2011
    Posts
    7

    Re: Number Theoretic Function t(n) or "tao" Proof

    I figured it out now. Thanks to all who responded to this!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: October 17th 2011, 02:50 PM
  2. Replies: 1
    Last Post: September 16th 2011, 01:08 AM
  3. Replies: 2
    Last Post: April 24th 2011, 07:01 AM
  4. Replies: 1
    Last Post: October 25th 2010, 04:45 AM
  5. Replies: 1
    Last Post: June 4th 2010, 10:26 PM

Search Tags


/mathhelpforum @mathhelpforum