Summing [Formula: see text] : a faster elementary algorithm

We present a new elementary algorithm that takes [Formula: see text] (measured bitwise) for computing [Formula: see text] where [Formula: see text] is the Möbius function. This is the first improvement in the exponent of x for an elementary algorithm since 1985. We also show that it is possible to r...

Descripción completa

Detalles Bibliográficos
Autores principales: Helfgott, Harald Andrés, Thompson, Lola
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Springer International Publishing 2022
Materias:
Research
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9731940/
https://www.ncbi.nlm.nih.gov/pubmed/36511765
http://dx.doi.org/10.1007/s40993-022-00408-8
_version_ 1784846014076682240
author Helfgott, Harald Andrés
Thompson, Lola
author_facet Helfgott, Harald Andrés
Thompson, Lola
author_sort Helfgott, Harald Andrés
collection PubMed
description We present a new elementary algorithm that takes [Formula: see text] (measured bitwise) for computing [Formula: see text] where [Formula: see text] is the Möbius function. This is the first improvement in the exponent of x for an elementary algorithm since 1985. We also show that it is possible to reduce space consumption to [Formula: see text] by the use of (Helfgott in: Math Comput 89:333–350, 2020), at the cost of letting time rise to the order of [Formula: see text] .
format Online
Article
Text
id pubmed-9731940
institution National Center for Biotechnology Information
language English
publishDate 2022
publisher Springer International Publishing
record_format MEDLINE/PubMed
spelling pubmed-97319402022-12-10 Summing [Formula: see text] : a faster elementary algorithm Helfgott, Harald Andrés Thompson, Lola Res Number Theory Research We present a new elementary algorithm that takes [Formula: see text] (measured bitwise) for computing [Formula: see text] where [Formula: see text] is the Möbius function. This is the first improvement in the exponent of x for an elementary algorithm since 1985. We also show that it is possible to reduce space consumption to [Formula: see text] by the use of (Helfgott in: Math Comput 89:333–350, 2020), at the cost of letting time rise to the order of [Formula: see text] . Springer International Publishing 2022-12-08 2023 /pmc/articles/PMC9731940/ /pubmed/36511765 http://dx.doi.org/10.1007/s40993-022-00408-8 Text en © The Author(s) 2022 https://creativecommons.org/licenses/by/4.0/Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/ (https://creativecommons.org/licenses/by/4.0/) .
spellingShingle Research
Helfgott, Harald Andrés
Thompson, Lola
Summing [Formula: see text] : a faster elementary algorithm
title Summing [Formula: see text] : a faster elementary algorithm
title_full Summing [Formula: see text] : a faster elementary algorithm
title_fullStr Summing [Formula: see text] : a faster elementary algorithm
title_full_unstemmed Summing [Formula: see text] : a faster elementary algorithm
title_short Summing [Formula: see text] : a faster elementary algorithm
title_sort summing [formula: see text] : a faster elementary algorithm
topic Research
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9731940/
https://www.ncbi.nlm.nih.gov/pubmed/36511765
http://dx.doi.org/10.1007/s40993-022-00408-8
work_keys_str_mv AT helfgottharaldandres summingformulaseetextafasterelementaryalgorithm
AT thompsonlola summingformulaseetextafasterelementaryalgorithm

Ejemplares similares