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.