{"ID":2876909,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.00236","arxiv_id":"2509.00236","title":"Analysis of Algorithms for Moser's Problems on Sums of Consecutive Primes","abstract":"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.","short_abstract":"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 algor...","url_abs":"https://arxiv.org/abs/2509.00236","url_pdf":"https://arxiv.org/pdf/2509.00236v1","authors":"[\"Jonathan P. Sorenson\",\"Eleanor Waiss\"]","published":"2025-08-29T20:55:35Z","proceeding":"math.NT","tasks":"[\"math.NT\",\"cs.DS\"]","methods":"[]","has_code":false}