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

The answer to your edited question is not quite as nice.

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

  • $\begingroup$ Thanks, now is there an algorithm to find the solution if $n$ is also bounded below by $l_0$? $\endgroup$
    – mchen
    May 8 '13 at 23:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.