An Algorithm to Find Sums of Powers of Consecutive Primes
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909059760783360 |
|---|---|
| author | O'Sullivan, Cathal Sorenson, Jonathan P. Stahl, Aryn |
| author_facet | O'Sullivan, Cathal Sorenson, Jonathan P. Stahl, Aryn |
| contents | We present and analyze an algorithm to enumerate all integers $n\le x$ that can be written as the sum of consecutive $k$th powers of primes, for $k>1$. We show that the number of such integers $n$ is asymptotically bounded by a constant times $$ c_k \frac{ x^{2/(k+1)} }{ (\log x)^{2k/(k+1)} }, $$ where $c_k$ is a constant depending solely on $k$, roughly $k^2$ in magnitude. This also bounds the asymptotic running time of our algorithm. We also give a lower bound of the same order of magnitude, and a very fast algorithm that counts such $n$. Our work extends the previous work by Tongsomporn, Wananiyakul, and Steuding (2022) who examined sums of squares of consecutive primes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2204_10930 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | An Algorithm to Find Sums of Powers of Consecutive Primes O'Sullivan, Cathal Sorenson, Jonathan P. Stahl, Aryn Number Theory Data Structures and Algorithms 11A41, 68Q25 We present and analyze an algorithm to enumerate all integers $n\le x$ that can be written as the sum of consecutive $k$th powers of primes, for $k>1$. We show that the number of such integers $n$ is asymptotically bounded by a constant times $$ c_k \frac{ x^{2/(k+1)} }{ (\log x)^{2k/(k+1)} }, $$ where $c_k$ is a constant depending solely on $k$, roughly $k^2$ in magnitude. This also bounds the asymptotic running time of our algorithm. We also give a lower bound of the same order of magnitude, and a very fast algorithm that counts such $n$. Our work extends the previous work by Tongsomporn, Wananiyakul, and Steuding (2022) who examined sums of squares of consecutive primes. |
| title | An Algorithm to Find Sums of Powers of Consecutive Primes |
| topic | Number Theory Data Structures and Algorithms 11A41, 68Q25 |
| url | https://arxiv.org/abs/2204.10930 |