# Clustering numbers by factors count

Is there a formula (or an efficient approach) for counting amount of positive numbers in range up to $N$ which have exactly $K$ divisors?

P.S.

Initial problem was to cluster number in range [1..N] according to the number of divisors. Then find multiplication of clusters' sizes factorials. So we just need compute the answer according to this scheme. The final result is a amount of sequencies formed such that first group has 1 divisor, second one has 2 and so on.

-

While I don't know of an explicit formula giving what you want, there are good ways to simplify the problem.

First, let $\tau(n)$ be the number of divisors of $n$. If $n=ab$ with $\operatorname{GCD}(a,b)=1$, then every divisor of $n$ can be uniquely factored as a divisor of $a$ and a divisor of $b$. Because of this, $\tau(ab)=\tau(a)\tau(b)$. By induction, if we factor $n$ as a product of powers of primes $n=\prod p_i^{a_i}$, then

$$\tau(n)=\prod \tau(p_i^{a_i})=\prod (a_i+1)$$ because $p^k$ has divisors $1,p,p^2,\ldots p^k$. Thus, the number of divisors a number has is determined by the exponents of its prime factorization (and not the individual factors).

With this in mind, we can solve the original problem as follows.

1. Find all possible factorizations of $K$. Note that there will be $\tau(K)$ of them.
2. For each factorization of $K$, subtract $1$ from each of the factors to write $K=\prod (a_i+1)$ for some collection of positive integers $a_i$.
3. For each collection of $a_i$, look at the possible assignment of primes such that $\prod p_i^{a_i}$ is less than $N$.

This is dependent on having a good way to generate all the primes, and the third step probably needs to be fleshed out a little, especially if one wants to be efficient, but overall, this is probably the best approach to the problem.

Note that (as mentioned in the other comments), if you let $K=2$, the problem simplifies to counting the number of primes less than $N$, and so a general formula is going to be more complicated than computing $\pi(N)$. I don't think anything less involved than the procedure above is likely to be fruitful (although you might be able to get asymptotics for specific values of $K$).

-

No, there's no such formula. If there were, then finding new primes would not be an interesting problem.

-

It rather depends on what other functions you have to hand.

If $K$ is prime then you want to count the primes up to the $K-1^{\text{th}}$ root of $N$, i.e. $$\pi(\sqrt[K-1]{N})$$ where $\pi(x)$ is the prime counting function.

But for $K=4$ you also want to count the numbers up to $N$ which are the product of distinct primes to add to $\pi(\sqrt[3]{N})$ and I am not aware of an explicit function notation for that.

-
Initial problem was to cluster number in range $[1..N]$ according to the number of divisors. Then find multiplication of clusters' sizes factorials. –  Jane Feb 3 '12 at 9:11
@Jane Was the problem a computation problem? Or something else? It's possible that calculating the size of individual clusters is hard, but some functions of all the clusters (e.g., the product of the factorials) has some other interpretation/characterization that makes it possible to calculate without calculating the individual cluster sizes. –  Aaron Feb 3 '12 at 9:21
@Aaron Yes, we just need compute the answer according to the scheme. So the final result is a amount of sequencies formed such that first group has 1 divisor, second one has 2 and so on. –  Jane Feb 3 '12 at 9:41
@Jane You should edit your question to include the added context so that people can consider whether there are indirect solutions that don't require computing individual cluster sizes. Unless this was a homework problem and you explicitly needed to compute the cluster sizes? However, this sounds more like a project euler type problem, which generally uses math to go from intractable to solvable-but-only-with-significant-computer-assistance. –  Aaron Feb 3 '12 at 10:05

There is another generalization of the problem, according to using of factorials of clusters sizes.

One wants to find amount of permutations of $1..N$ which have the following property -$\tau(A_i)=\tau(i)$, where $A_i$ are the elements of permutation.

-