Re: the number of divisors, number theory

On Dec 5, 2006 2:26 PM CT, W. Schols wrote:

is it true and when yes, can someone prove that

2 exp( omega (n)) <= tau (n) < 2 sqrt (n),

with the following definitions,

n is a positive integer
omega (n) denotes the number of distinct prime
factors of n
tau (n) is the number of divisors of n
sqrt (n) is the square root of n.

Can someone help me with the second part of the
statement ? (the first part is clear for me, but I
have problems to prove the second part, that tau(n)
is always smaller than 2 time the sqrt of n).

thanks and greetings, Wim

I'm not sure if this is the proper way to proceed, but
this is what I thought of. I'm going to use elementary
calculus, but maybe induction would work too.

By the fundamental theorem of arithmetic we have

n = (p_1)^(k_1) * ... * (p_r)^(k_r),

for some primes p_i and integers k_i. Recall that

tau(n) = (k_1 + 1) * ... * (k_r + 1),

and that tau is a multiplicative function. Since the
square root is a completely multiplicative function it
suffices to show the inequality

tau(p^k) < 2 sqrt(p^k),

for some prime p and integer k. In other words, we must
show that

k + 1 < 2 * p^(k/2),

for all k >= 1 for any given p. Now define

f(k) := 2 p^(k/2) - k - 1,

then the derivative w.r.t. k is

f'(k) = ln(p) p^(k/2) - 1.

Note that since p >= 2 and fixed, f'(k) is increasing on
the inverval [1,oo). Moreover, f(1) = 2 p^(1/2) - 2 > 0
for all primes p >= 2.

Thus, f(k) > 0 for all p >= 2 on the interval [1, oo), in
other words

2 p^(k/2) - k - 1 > 0

2 p^(k/2) > k + 1

2 sqrt(p^k) > tau(p^k)

for all p >= 2, k >= 1. Unless of course I made a
mistake somewhere up there.

Regards,
Kyle Czarnecki
.

Relevant Pages

  • Re: Forth PARANOIA
    ... Addition/Subtraction neither rounds nor chops. ... Test for sqrt monotonicity. ... "Square root is neither chopped nor correctly rounded", ...
    (comp.lang.forth)
  • Re: Riemann surface
    ... function is the projection taking the x value. ... So, the sqrt function *is* ... globally defined analytic square root on C or on C without the origin. ... instead of just Z the complex plane that represents the y-component only. ...
    (sci.math)
  • Re: read string to float
    ... It can represent square root of 2 and any other real number. ... doesn't use (sqrt 2) as representation though. ... digit, untested) ... That's something like that reallib does. ...
    (comp.lang.lisp)
  • Re: solution to nonlinear eq
    ... b and g are unknown ... The following finds all possible non-negative integer solutions. ... I have assumed here that the 'sqrt' function gives an exact answer for the ... square root of any integer squared. ...
    (comp.soft-sys.matlab)
  • Re: solution to nonlinear eq
    ... b and g are unknown ... The following finds all possible non-negative integer solutions. ... I have assumed here that the 'sqrt' function gives an exact answer for the ... square root of any integer squared. ...
    (comp.soft-sys.matlab)