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

DOI10.1007/S00453-008-9221-ZMaRDI QIDQ834601zbMATH OpenOpenAlexFDO

Authors Jakub Pawlewicz, Mihai Patrascu

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

Farey sequenceMertens functionprimitive lattice pointsMöbius inversion

Mathematics Subject Classification ID

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

Recommendations

• Order Statistics in the Farey Sequences in Sublinear Time
• Algorithmic Number Theory
• On the Farey sequence and its augmentation for applications to image analysis
• Primitive Points in Rational Polygons
• On Farey table and its compression for space optimization with guaranteed error bounds

Cites work

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

Cited in

(4)

• Order Statistics in the Farey Sequences in Sublinear Time
• 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
• From prima quadraginta octant to lattice sphere through primitive integer operations

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q834601)