is any faster algorithm to calculate this series? ∑∑ai​/aj

Question

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

Answer 1

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.

Answer 2

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.