Count the number of integer solutions for $a \times b \geq k$?

Question

count the number of integer solution for $a \times b \geq k$

given the conditions

1) $1 \leq a \leq p$

2) $1 \leq b \leq q$

(k, p, and q are constant).

Answer 1

In graphical terms, you're counting the number of lattice points (i.e., points with integer components) that are within or on the boundary of the rectangle with opposite corners $(0, 0)$ and $(p, q)$ and which lie above or on the hyperbola $xy=k$. With this in mind we have three cases:

1. If $pq < k$ the rectangle lies below the hyperbola, so there are no solutions.

2. If $pq = k$ only the upper-right corner of the rectangle will intersect the hyperbola, so there will be a single solution, $a=p, b=q.$

3. If $pq > k$ there are at least two possible ways to go. The easiest is to get an upper bound for the number of solutions. Certainly the number of solutions will be no larger than the area above the curve $xy=k,$ below the line $y=q,$ and to the left of the line $x=p$. The curve and the line intersect when $x=k/q$ so the area will be

$$ A = \int_{k/q}^p k-\frac{k}{x} dx = pq+k\left(\ln\frac{k}{pq}-1\right) $$

For most values of $p$ and $q,$ this turns out to be pretty close to the actual number of solutions.

On the other hand, if you want an exact answer you can find the convex hull of your set of solution points and then use Pick's Theorem. Although it will do what you want, the answer won't be nearly as simple as the estimate above.