Re: Number of factors/divisors question

From: Arturo Magidin (magidin_at_math.berkeley.edu)
Date: 07/15/04 

Date: Thu, 15 Jul 2004 18:29:44 +0000 (UTC)

In article <cd6go6$ma7$2@oravannahka.helsinki.fi>,
Joona I Palaste <palaste@cc.helsinki.fi> wrote:
>For a natural number n, we can express three different numbers:
>- The number of its prime factors, i.e. if we write n as a product of
>prime numbers, this is the number of terms in the product.
>- The number of its unique prime factors, which is how many different
>primes appear in the above.
>- The number of its divisors, i.e. how many numbers can n be divided
>with and get an integer result.

Do you mean to include negative integers as well, or only the positive
ones? (No real difference, just curious)

>Let's define that n itself qualifies as a prime factor (if it's prime in
>the first place) and a divisor, but 1 doesn't qualify as either.
>Can any of these three numbers be expressed as a function of the two
>others?

You can find the number of divisors (in your restricted sense) from
the prime factorization: if

n = p_1^{a1} * ... * p_r^{ar}

with p_i pairwise distinct primes, and ai>0 for each i, then the
number of positive divisors of n is equal to

(a1+1)*(a2+1)*...*(ar+1)

To see this, note that any divisor of n must have a prime
factorization which uses only primes from {p_1,....,p_r}, and such that
the exponent of p_i is no more than ai. So there are a1+1 possible
choices for the exponent of p1, namely 0, 1, 2, ..., a1; a2+1 for p_2;
etc.

So the number of positive divisors in your restricted sense is
(a1+1)*(a2+1)*...*(ar+1) - 1.

The three answers for n are then given by:

(i) a1+a2+...+ar
(ii) r
(iii) (a1+1)*(a2+1)*...*(ar+1) - 1.

I assume that your question means: is there a function f(x,y), such
that if we let x and y be the value of two of these numbers, f(x,y)
will be the value of the third?

For example, to see that the third is not a function of the first two,
it is enough to find two numbers n and m for which the first two
values are equal but the third is different.

(I assume for simplicity that p_1 < p_2 < ... < p_r.

An easy example would be n=36, which has r=2, a1=2, a2=2, and so the
three values are

  (i) 4
  (ii) 2
  (iii) 3*3 - 1 = 8.

And m=24, which has r=2, a1=3, a2=1, and so
  (i) 4
  (ii) 2
  (iii) 4*2 - 1 = 7.

So (iii) is not a function of (i) and (ii).

To see that (i) is not a function of (ii) and (iii), compare
n=2^3*3^8, which has r=2, 4*9-1 = 35 divisors, and 11 factors; with
m=2^5*3^5, which has r=2, 6*6-1 = 35 divisors, and 10 factors.

To be honest, I'm having a bit of trouble with whether (ii) is a
function of (i) and (iii)... I'll think on it. 

-- 
======================================================================
"It's not denial. I'm just very selective about
 what I accept as reality."
    --- Calvin ("Calvin and Hobbes")
======================================================================
Arturo Magidin
magidin@math.berkeley.edu

Relevant Pages