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$?
Number of factors less than a number
-
0I 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
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.
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}$.