Take the 2-minute tour ×

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

share|improve this question
Do you suppose you can rephrase this so it doesn't sound like you are giving us an order? And while you're at it, indicate what thoughts you've had about the problem, what progress you've made, where you got stuck, how the problem attracted your attention, etc., etc.? –  Gerry Myerson Jun 4 '12 at 0:48

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

share|improve this answer

Your Answer


