Sublinear O(N^(1/3)) Computation of Quotient Collisions via Interval Grouping

This paper addresses the problem of exactly computing the number of quotient collisions E(N), defined as the number of index pairs i < j for which the integer parts of N/i and N/j coincide, as well as computing the exact distribution of quotient block sizes. The standard approach requires iterating over approximately sqrt(N) blocks. We propose a novel sublinear algorithm based on two key structural observations: the block size c_w takes one of two adjacent values m or m+1, where m = floor(N/(w(w+1))), and the sum of block sizes over an interval of constant m can be evaluated telescopically using only two values of the integer part. This allows evaluating the contribution of an entire interval in O(1) arithmetic operations, reducing the number of processed intervals to at most 2*ceil(N^(1/3)). We present the mathematical foundations, the algorithmic implementation, complexity bounds, and verification procedures. Empirical benchmarks in Python demonstrate a practical speedup ranging from 1.21x to 51.33x for N between 10^6 and 10^16, with the performance gain increasing asymptotically with N.