2
$\begingroup$

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$?

  • 0
    Do you want the number of prime factors of $n^2$ or all of its factors?2011-08-19
  • 0
    @Robert, anon is right, I want the number of factors (i.e., divisors) of $n^2$ that are less than $n$.2011-08-19
  • 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$?2011-08-19
  • 0
    @Artem, do you want to write that up as a an answer?2011-08-19
  • 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$.2011-08-19
  • 0
    @Andre, why is it $2a_i$ instead of $a_i$?2011-08-19
  • 0
    Because $n^2=\prod p_i^{2a_i}$.2011-08-19
  • 0
    @Andre, yes of course. Thanks.2011-08-19
  • 0
    @Artem: You have to subtract $1$ out from $\sigma_0(n^2)$ before you divide by $2$ because $d=n$ is a divisor of $n^2$ that is neither greater than nor less than $n$. Nice symmetry observation btw.2011-08-19
  • 0
    I forgot to mention (back in August), but this question inspired another [question on cstheory](http://cstheory.stackexchange.com/q/7862/1037) about how one would count the number of factors without factoring the number.2012-01-28

2 Answers 2

3

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.

0

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}$.