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
-
0Do 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
-
4For 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
-
1Let $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
-
0Because $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
-
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}$.