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

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

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.

• would you please mention, what is d, and how to calculate it? – Mehdi M Oct 2 '20 at 13:31
• $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$. – Dmitry Oct 2 '20 at 13:33

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.