1
$\begingroup$

I am wondering if it is possible to calculate the following double sum, where $a_1,\ldots,a_n$ are positive integers, in time faster than the trivial $O(n^2)$: $$ \sum_{i=1}^n \sum_{j=1}^n \left\lfloor \frac{a_i}{a_j} \right\rfloor. $$

For example, if $a_1 = 1, a_2 = 2, a_3 = 3$ then the sum is $9$.

$\endgroup$
2
$\begingroup$

Assuming that your numbers $a_i$ are small enough and $n$ is large enough, the following algorithm may work better in practice.

For each $a_i$, for all possible division results $d_j$, find minimum $v_j$ such that $\lfloor \frac {a_i} {v_j} \rfloor = d_j$. The idea is the following:

  • There can't be too many different $d_j$. E.g. for $a=10^9$ there are about $6 \cdot 10^4$ possible $d_j$. It's possible to show that there are $O(\sqrt{a})$ possible values of $d_j$ (about $2 \sqrt a$). Note that it's possible to iterate all possible $d_j$'s in time linear of their amount.

  • All numbers between neighboring $v_j$'s give the same result after division.

Therefore, the algorithm is the following:

  • Sort $a_1, \ldots, a_n$
  • For each $a_i$, find all possible $\{(d_j, v_j)\}$ as described above. Using binary search on array of $a_i$, for all $j$ find the number of $a_i$ lying between $v_j$ and $v_{j+1}$. Division by any of them results in $d_j$.

P.S.: This algorithm can take exponential time (since it's polynomial on the numbers themselves), but it can have a guaranteed $O(n^2 \log n)$ time when we ignore $d_j$ which can't be achieved: when we've found the last number $a_k$ which lies between $v_j$ and $v_{j+1}$, we select the next $d$ to consider based on $a_{k+1}$. Additional $\log n$ comes from the binary search.

$\endgroup$
  • $\begingroup$ would you please mention, what is d, and how to calculate it? $\endgroup$ – Mehdi M Oct 2 '20 at 13:31
  • $\begingroup$ $d$ are all possible results of division. E.g. if you divide $10$ by any number, you can't get $7$ as a result. The only possible results are $10, 5, 3, 2, 1, 0$. $\endgroup$ – Dmitry Oct 2 '20 at 13:33
0
$\begingroup$

Dmitry’s idea will work very well for many sequences of integers. If I had to evaluate many different sums for values of n around a few million then I would use this approach to have a fighting chance to find the sum without doing trillions and trillions of operations.

But a hard case would be: About n/2 numbers randomly between n and 4n, and the remaining numbers randomly between 4n^2 and 16n^2. In this case it seems very hard to avoid doing about n^2/4 divisions. Still, note that a difficult worst case may never happen.

$\endgroup$

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.