Order statistics in the Farey sequences in sublinear time and counting primitive lattice points in polygons

DOI10.1007/s00453-008-9221-zzbMath1191.68835OpenAlexW1997489418MaRDI QIDQ834601

Jakub Pawlewicz, Mihai Pǎtraşcu

Publication date: 27 August 2009

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-008-9221-z

zbMATH Keywords

Möbius inversionFarey sequenceMertens functionprimitive lattice points

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Number-theoretic algorithms; complexity (11Y16) Farey sequences; the sequences (1^k, 2^k, dots) (11B57)

Related Items (3)

From prima quadraginta octant to lattice sphere through primitive integer operations ⋮ On the Farey sequence and its augmentation for applications to image analysis ⋮ Improved pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Scaled density models for binary response data and their \(D\)- and \(D_s\)-optimal designs
• On the number of primitive lattice points in plane domains
• Optimal search for rationals
• Primitive lattice points in rational ellipses and related arithmetic functions
• Rational search
• Efficient search for rationals
• Primitive lattice points in starlike planar sets
• Distribution of lattice points visible from the origin
• On the primitive circle problem
• Explicit and efficient formulas for the lattice point count in rational polygons using Dedekind-Rademacher sums
• The number of lattice points within a contour and visible from the origin
• Primitive lattice points in a thin strip along the boundary of a large convex planar domain
• Primitive lattice points inside an ellipse
• Order Statistics in the Farey Sequences in Sublinear Time
• Computing the Summation of the Möbius Function
• On primitive lattice points in planar domains
• A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
• On the number of coprime integer pairs within a circle
• On sums and differences of two relative prime cubes
• Primitive lattice points in convex planar domains
• Approximating Rational Numbers by Fractions

This page was built for publication: Order statistics in the Farey sequences in sublinear time and counting primitive lattice points in polygons