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


2 Answers 2


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.

  • $\begingroup$ would you please mention, what is d, and how to calculate it? $\endgroup$
    – Mehdi M
    Oct 2, 2020 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$
    – user114966
    Oct 2, 2020 at 13:33
  • $\begingroup$ And the results 10,5,3 can only be achieved if you divide by 1, 2 or 3. There are abouts sqrt(10) such numbers. The results 2, 1, 0 can be achieved by division by several numbers, like 1 = 10 / (10, 9, 8, 7, 6), there are sqrt(1) such numbers. $\endgroup$
    – gnasher729
    May 10, 2021 at 10:50

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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