# Discrete Optimization based on Integer Division and Remainder

General problem

Let $\mathrm{DIV}$ be the integer division and $\mathrm{MOD}$ the standard remainder calculation.

Given $k$ natural numbers $n_1, ... , n_k$, what natural number $m$ minimizes $$m+\sum_{i=1}^{k}\left(n_i\;\mathrm{DIV} \;m\right)+\left(n_i\;\mathrm{MOD} \;m\right) \;?$$ It is likely that there is no easy formula for $m$ in terms of the numbers $n_i$, but are there some lower and upper bounds for $m$ or at least an order of the size of $m$ in terms of the numbers $n_i$?

Base case ($k=1$)

For example consider the base case $k=1$, then there is a given number $n$ and I want to minimize

$$m+n\;\mathrm{DIV}\; m+n\;\mathrm{MOD} \;m.$$ By a comment of Hurkyl, the identity $n=m(n\;\mathrm{DIV}\; m)+n\;\mathrm{MOD} \;m$ leads to

$$m+n\;\mathrm{DIV}\; m+n\;\mathrm{MOD} \;m\;=\;m+n+(1-m)(n\;\mathrm{DIV}\; m).$$ I think here the choice of $m$ would be close to $\sqrt{n}$. But are there precise boundaries like $$\sqrt{n}-c_n\le m\le \sqrt{n}+c_n$$ for some small term $c_n\in o(\sqrt{n})$ ?

And for the general case, is there something similar like $$\sqrt{\sum_i n_i}-c_n\le m\le \sqrt{\sum_i n_i}+c_n\; ?$$

I have basically no idea how to even begin to prove (tight) bounds, so any help is welcome here!

• While calling it the "modulo" operation is common, the actual name for the operation is "remainder". – Hurkyl Sep 14 '17 at 10:42
• @Hurkyl Thank you, I edited the question. – Danny Sep 14 '17 at 10:46
• It may help to rewrite the formula using the identity $$n = m (n \operatorname{div} m) + (n \operatorname{mod} m)$$ – Hurkyl Sep 14 '17 at 10:57
• @Hurkyl At least it makes it possible to only have one of the operation (DIV or MOD) left in the goal function. – Danny Sep 15 '17 at 5:12