Analysis of Algorithms for Moser's Problems on Sums of Consecutive Primes
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915470784856064 |
|---|---|
| author | Sorenson, Jonathan P. Waiss, Eleanor |
| author_facet | Sorenson, Jonathan P. Waiss, Eleanor |
| contents | In his 1963 paper on the sum of consecutive primes, Moser posed four open questions related to $f(n)$, the number of ways an integer $n$ can be written as a sum of consecutive primes. (See also problem C2 from Richard K.~Guy's \textit{Unsolved Problems in Number Theory}.) In this paper, we present and analyze two algorithms that, when given a bound $x$, construct a histogram of values of $f(n)$ for all $n\le x$. These two algorithms were described, but not analyzed, by Jean Charles Meyrignac (2000) and Michael S. Branicky (2022). We show the first algorithm takes $O(x\log x)$ time using $x^{2/3}$ space, and the second has two versions, one of which takes $O(x\log x)$ time but only $x^{3/5}$ space, and the other which takes $O(x(\log x)^2)$ time but only $O( \sqrt{x\log x})$ space. However, Meyrinac's algorithm is easier to parallelize. We then present data generated by these algorithms that address all four open questions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_00236 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Analysis of Algorithms for Moser's Problems on Sums of Consecutive Primes Sorenson, Jonathan P. Waiss, Eleanor Number Theory Data Structures and Algorithms 11Y16, 11Y11, 68Q25 F.2.1 In his 1963 paper on the sum of consecutive primes, Moser posed four open questions related to $f(n)$, the number of ways an integer $n$ can be written as a sum of consecutive primes. (See also problem C2 from Richard K.~Guy's \textit{Unsolved Problems in Number Theory}.) In this paper, we present and analyze two algorithms that, when given a bound $x$, construct a histogram of values of $f(n)$ for all $n\le x$. These two algorithms were described, but not analyzed, by Jean Charles Meyrignac (2000) and Michael S. Branicky (2022). We show the first algorithm takes $O(x\log x)$ time using $x^{2/3}$ space, and the second has two versions, one of which takes $O(x\log x)$ time but only $x^{3/5}$ space, and the other which takes $O(x(\log x)^2)$ time but only $O( \sqrt{x\log x})$ space. However, Meyrinac's algorithm is easier to parallelize. We then present data generated by these algorithms that address all four open questions. |
| title | Analysis of Algorithms for Moser's Problems on Sums of Consecutive Primes |
| topic | Number Theory Data Structures and Algorithms 11Y16, 11Y11, 68Q25 F.2.1 |
| url | https://arxiv.org/abs/2509.00236 |