Skip to main content

Voronoi, Sierpinski, Eratosthenes

Posted in
Harald Helfgott
U. Göttingen
Wed, 2017-07-05 15:00 - 15:50
MPIM Lecture Hall
Parent event: 
Number theory lunch seminar

We show how to carry out a sieve of Erastosthenes up to $N$ in space $O(N^{1/3})$ and essentially linear time.
This improves over the usual versions, which take space about $O(\sqrt{N})$ and essentially linear time.
The algorithm -- which, like the one in (Galway, 2000), is ultimately related to diophantine approximation --
can also be used to factorize integers $n$, and thus to give the values of arithmetical functions such as the
Möbius function $\mu$ and the Liouville function $\lambda$ for all integers up to $N$.

© MPI f. Mathematik, Bonn Impressum
-A A +A