Order Statistics in the Farey Sequences in Sublinear Time and Counting Primitive Lattice Points in Polygons
We present the first sublinear-time algorithms for computing order statistics in the Farey sequence and for the related problem of ranking. Our algorithms achieve a running times of nearly O(n (2/3)), which is a significant improvement over the previous algorithms taking time O(n). We also initiate the study of a more general problem: counting primitive lattice points inside planar shapes. For rational polygons containing the origin, we obtain a running time proportional to D (6/7), where D is the diameter of the polygon.
farey sequence primitive lattice points mobius inversion mertens function