Farey Statistics in Time n^{2/3} and Counting Primitive Lattice Points in Polygons

Abstract

We present algorithms for computing ranks and order statistics in the Farey sequence, taking time O (n^{2/3}). This improves on the recent algorithms of Pawlewicz [European Symp. Alg. 2007], running in time O (n^{3/4}). We also initiate the study of a more general algorithmic problem: counting primitive lattice points in planar shapes.

arXiv commentFixed a technical error. Added reference to latest work (joint version with Pawlewicz)