2025/08/29 by Jonathan Sorenson, Sorenson, Jonathan P., Eleanor Waiss +1
Computer Science · Mathematics · #11Y11 #11Y16 #68Q25 #Algebraic Geometry and Number Theory #Analytic Number Theory Research #Data Structures and Algorithms (cs.DS) #F.2.1 #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2509.00236
openalex publication_date 2025/08/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 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≤ 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(xlog x) time using x2/3 space, and the second has two versions, one of which takes O(xlog x) time but only x3/5 space, and the other which takes O(x(log x)2) time but only O( √(xlog x)) space. However, Meyrinac's algorithm is easier to parallelize. We then present data generated by these algorithms that address all four open questions.