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

DOI10.1007/S00453-008-9221-ZzbMATH Open1191.68835OpenAlexW1997489418MaRDI QIDQ834601FDOQ834601

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

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

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)

Cites Work

• Title not available (Why is that?)
• On the primitive circle problem
• Distribution of lattice points visible from the origin
• Title not available (Why is that?)
• A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
• Optimal search for rationals
• Scaled density models for binary response data and their \(D\)- and \(D_s\)-optimal designs
• Rational search
• Efficient search for rationals
• On the number of primitive lattice points in plane domains
• Primitive lattice points in rational ellipses and related arithmetic functions
• Primitive lattice points in starlike planar sets
• 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
• Title not available (Why is that?)
• On primitive lattice points in planar domains
• 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

Cited In (4)

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

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)