Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I need to find the number of factors of a large number $n^2$ that are less than $n$. Supposing I can find the prime factorization, it is simple to find the total number of factors as a combinatorial sum, but how do I enforce the inequality that the factors should be less than $n$?

share|improve this question
    
Do you want the number of prime factors of $n^2$ or all of its factors? –  user12998 Aug 19 '11 at 2:50
    
@Robert, anon is right, I want the number of factors (i.e., divisors) of $n^2$ that are less than $n$. –  highBandWidth Aug 19 '11 at 3:02
4  
For every $a$ factor of $n^2$ that is less than $n$ there is a factor $b = n^2/a$ that is greater than $n$. Thus, if it is "simple to find the total number of factors as a combinatorial sum", then why not just divide that by $2$ to get the number of factors less than $n$? –  Artem Kaznatcheev Aug 19 '11 at 3:22
    
@Artem, do you want to write that up as a an answer? –  highBandWidth Aug 19 '11 at 3:38
1  
Let $n=\prod p_i^{a_i}$ where the $p_i$ are distinct primes. Then the number of divisors less than $n$ is $((\prod (2a_i+1)) -1)/2$. –  André Nicolas Aug 19 '11 at 3:40

2 Answers 2

up vote 3 down vote accepted

Moving my comment to an answer:

For every factor $a$ of $n^2$ such that $a < n$ there is a factor $b = n^2/a$ that is greater than $n$. As @anon mentioned, it is important to not forget the boundary condition of $a = n$, where we would also have $b = n$. Thus, if it is "simple to find the total number of factors as a combinatorial sum", then just subtract one from this and divide by two. If you want to also count $n$ then add 1 back in after the division.

share|improve this answer

The sum of powers of divisors of a number $\sigma_k(n) = \sum_{d \ge 1, d \vert n} d^k$ could be used to find the number of divisors. It is known as divisor function. The number of divisors of $n^2$ is $\sigma_0(n^2)$.

Because for every divisor $d$, $\frac{n^2}{d}$ is also a divisor, hence we split the sum over divisor into $d=n$, $1 \le d < n$ and $n < d \le n^2$:

$$ \sigma_0(n^2) = \sum_{d \ge 1, d \vert n^2} d^0 = 1 + 2 \sum_{n > d \ge 1, d\vert n} d^0 $$

Thus the number you seek is $\frac{\sigma_0(n^2)-1}{2}$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.