# On the number of divisors within given bounds

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

• of course it is well defined. Commented Jan 26, 2017 at 2:18
• does checking every divisor count? Commented Jan 26, 2017 at 2:19
• well, that counts for an algorithm however my question is what would that function be. Commented Jan 26, 2017 at 2:20
• You might as well ask for a function $d'(n,b)$ that counts divisors below $b$. Then $d(n,a,b)=d'(n,b)-d'(n,a)$ Commented Jan 26, 2017 at 3:14
• @KonKan Sure thing. Fix any $a<b$. There are only finitely many integers in the range $[a,b]$. Let $L$ be the lcm of the set $\{a,a+1,\ldots,b\}$. Then any integer $c$ with $a\le c \le b$ by definition divides $L$. In particular, $c \mid x \iff c \mid x+L$. It follows that $d(n,a,b) = d(n+L,a,b)$, so $d(\cdot,a,b)$ is periodic with period at most $L$. Commented Feb 2, 2017 at 7:27

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