On the number of divisors within given bounds

895 Views Asked by At

It is well known, that given an integer $n$ whose prime factorization is $$ n = p_1^{a_1} \times p_2^{a_2} \times \ldots \times p_n^{a_n} $$ the number of its positive divisors is given by $$ d(n) = (a_1+1) \times (a_2+1) \times \ldots \times (a_k+1) $$ Now the question is the following: How many of the above divisors of $n$ lie between given bounds $a$ and $b$? Is there a systematic method for answering this question ?

In other words: given two positive integers $a<b$, and a positive integer $n$, is there a well defined function $d(n,a,b)$ having as its values the number of positive divisors of $n$, lying between $a$ and $b$ ?

2

There are 2 best solutions below

2
On BEST ANSWER

Here is an approximation that works well when $n$ is enormous, has few factors, and $b$ is large but small compared with $n$. We will look for a function $d'(n,b)$ that counts divisors of $n$ that are below $b.$ As an example, we will consider the case where $n=2^k3^m$ and assume that $2^k, 3^m \gt b.$ At each of the lattice points $(x,y)$ in the first quadrant we can associate the log of one potential factor, so at $(x,y)$ we associate $x \log 2 + y \log 3$. The factors less than $b$ are the lattice points below the line $x \log 2 + y \log 3 =\log b$. The area of the triangle is $\frac {(\log b)^2}{2 \log 2 \log 3}$ so we would expect that many factors less than $b$. The extension to more factors is clear. If there were prime factors $2,3,5$ the number of factors less than $b$ would be $\frac {(\log b)^3}{3! \log 2 \log 3 \log 5}$ because we would have a tetrahedron in a $3D$ lattice.

The limitations are easy to see. If there are not enough factors of $2$ or $3$ to exceed $b$ our triangular region can become a rectangle with the corner cut off. The line or plane dividing the factors below $b$ from those above will pass between lattice points, so there is uncertainty at the boundary. As the boundary is one dimension lower than the bulk of the lattice points this error reduces as $n$ gets large. A feel for the error comes from the fact that for $b=10^6$ the area formula gives $125$ factors while there really are $142$. For $b=10^9$ the area formula gives $282$ compared to $306$.

1
On

Several mathematicians have done research on this very topic. A good place to start might be this paper of Kevin Ford: "The distribution of integers with divisors in a given interval."