Formulas and algorithms for the length of a Farey sequence

Abstract This paper proves several novel formulas for the length of a Farey sequence of order n. The formulas use different trade-offs between iteration and recurrence and they range from simple to more complex. The paper also describes several iterative algorithms for computing the length of a Fare...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Vladimir Sukhoy, Alexander Stoytchev
Formato:	article
Lenguaje:	EN
Publicado:	Nature Portfolio 2021
Materias:	Medicine R Science Q
Acceso en línea:	https://doaj.org/article/1148cd0c5d324973877551f9cf25a9f3
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:1148cd0c5d324973877551f9cf25a9f3
record_format	dspace
spelling	oai:doaj.org-article:1148cd0c5d324973877551f9cf25a9f32021-11-21T12:23:01ZFormulas and algorithms for the length of a Farey sequence10.1038/s41598-021-99545-w2045-2322https://doaj.org/article/1148cd0c5d324973877551f9cf25a9f32021-11-01T00:00:00Zhttps://doi.org/10.1038/s41598-021-99545-whttps://doaj.org/toc/2045-2322Abstract This paper proves several novel formulas for the length of a Farey sequence of order n. The formulas use different trade-offs between iteration and recurrence and they range from simple to more complex. The paper also describes several iterative algorithms for computing the length of a Farey sequence based on these formulas. The algorithms are presented from the slowest to the fastest in order to explain the improvements in computational techniques from one version to another. The last algorithm in this progression runs in $$O(n^{2/3})$$ O ( n 2 / 3 ) time and uses only $$O(\sqrt{n})$$ O ( n ) memory, which makes it the most efficient algorithm for computing $$\|F_n\|$$ \| F n \| described to date. With this algorithm we were able to compute the length of the Farey sequence of order $$10^{18}$$ 10 18 .Vladimir SukhoyAlexander StoytchevNature PortfolioarticleMedicineRScienceQENScientific Reports, Vol 11, Iss 1, Pp 1-18 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	Medicine R Science Q
spellingShingle	Medicine R Science Q Vladimir Sukhoy Alexander Stoytchev Formulas and algorithms for the length of a Farey sequence
description	Abstract This paper proves several novel formulas for the length of a Farey sequence of order n. The formulas use different trade-offs between iteration and recurrence and they range from simple to more complex. The paper also describes several iterative algorithms for computing the length of a Farey sequence based on these formulas. The algorithms are presented from the slowest to the fastest in order to explain the improvements in computational techniques from one version to another. The last algorithm in this progression runs in $$O(n^{2/3})$$ O ( n 2 / 3 ) time and uses only $$O(\sqrt{n})$$ O ( n ) memory, which makes it the most efficient algorithm for computing $$\|F_n\|$$ \| F n \| described to date. With this algorithm we were able to compute the length of the Farey sequence of order $$10^{18}$$ 10 18 .
format	article
author	Vladimir Sukhoy Alexander Stoytchev
author_facet	Vladimir Sukhoy Alexander Stoytchev
author_sort	Vladimir Sukhoy
title	Formulas and algorithms for the length of a Farey sequence
title_short	Formulas and algorithms for the length of a Farey sequence
title_full	Formulas and algorithms for the length of a Farey sequence
title_fullStr	Formulas and algorithms for the length of a Farey sequence
title_full_unstemmed	Formulas and algorithms for the length of a Farey sequence
title_sort	formulas and algorithms for the length of a farey sequence
publisher	Nature Portfolio
publishDate	2021
url	https://doaj.org/article/1148cd0c5d324973877551f9cf25a9f3
work_keys_str_mv	AT vladimirsukhoy formulasandalgorithmsforthelengthofafareysequence AT alexanderstoytchev formulasandalgorithmsforthelengthofafareysequence
_version_	1718419048107081728

Formulas and algorithms for the length of a Farey sequence

Ejemplares similares