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!

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

Your Answer

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

Browse other questions tagged or ask your own question.