pith. machine review for the scientific record. sign in

arxiv: 0708.0080 · v2 · submitted 2007-08-01 · 🧮 math.NT

Recognition: unknown

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

Mihai Patrascu
Authors on Pith no claims yet
classification 🧮 math.NT
keywords timealgorithmscountingfareylatticepointsprimitivestatistics
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Counting All Lattice Rectangles in the Square Grid in Near-Linear Time

    cs.CG 2026-04 unverdicted novelty 6.0

    Presents an O(n log² n) divisor-layer algorithm for counting lattice rectangles in an n×n grid and derives the asymptotic F(n) = ((4 log 2 - 1)/π²) n⁴ log n + B n⁴ + o(n⁴) with explicit B.