# Is there an explicit solution to: $\arg \min mn : mn \geq k, l_0 \leq n \leq l_1$?

Is there an explicit solution or a fast algorithm to compute:

$$\underset{(m, \ n) \in \mathbb{N}_{+}^2}{\arg \min} \ mn \ : \ mn \geq k,\ l_0 \leq n \leq l_1$$

for given constants $k, l_0, l_1 \in \mathbb{N}_{+}$?

Edit: added $l_0$ constraint

Note that $(k,1)$ certainly minimizes $mn$ given the constraints. Hence the set you are looking for is in fact $\{(m,n)\in\mathbb{N}_+^2:mn=k,\, n\leq l\}$.
Thus, the argmin consists of all $(m,n)$, where $n$ is a divisor of $k$ less than or equal to $l$ and $m=\frac{k}{n}$.
Let $k^\prime$ be the smallest number greater than or equal to $k$ having a divisor in the range $l_0,\ldots,l_1$. Then your argmin is given by all $(m,n)$ where $n$ is a divisor of $k^\prime$ in the range $l_0,\ldots,l_1$ and $m=\frac{k^\prime}{n}$.
Unfortunately I don't see a particularly efficient way to determining $k^\prime$.
• Thanks, now is there an algorithm to find the solution if $n$ is also bounded below by $l_0$? May 8 '13 at 23:31