Analysis of Algorithms for Moser's Problems on Sums of Consecutive Primes

Eleanor Waiss; Jonathan P. Sorenson

REVIEW 3 major objections 5 minor 13 references

Analysis of Algorithms for Moser's Problems on Sums of Consecutive Primes

T0 review · 3 major / 5 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves near-linear time and sublinear space bounds for two algorithms that build exact histograms of the number of ways an integer is a sum of consecutive primes, and uses them to find the first known integer with 14 such represe

desk verdict Real algorithmic analysis with an honest record, but the headline time bounds lean on an unproved prime-gap cancellation; revise or label conditional. read the letter →

arxiv 2509.00236 v1 pith:ISX5MMBI submitted 2025-08-29 math.NT cs.DS

Jonathan P. Sorenson , Eleanor Waiss This is my paper · ORCID

classification math.NTcs.DS MSC 11N0511Y1611Y55

keywords sumsofconsecutiveprimesrepresentationcountingfunctionhistogramcomputationslidingwindowalgorithmpriorityqueueaverage-caseanalysisprimegapscomputationalnumbertheory

topics The Twin Prime Conjecture

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Four open questions from 1963 ask whether integers with exactly k representations as sums of consecutive primes occur infinitely often, whether every k occurs, whether each such set has a density, and whether the number of representations is unbounded. This paper supplies the first rigorous analyses of two algorithms that compute the exact histogram h(k,x), counting how many integers n ≤ x have exactly k such representations. The results are near-linear time and sublinear space: one algorithm runs in O(x log x) arithmetic operations with O(x^(2/3)) space, while a second runs in O(x log x) time with O(x^(3/5)) space, or in O(x(log x)^2) time with O(sqrt(x log x)) space, depending on how primes are generated. Running the algorithms just past x=10^14 produced the first known integer with 14 representations, 84,941,668,414,584, and histogram data consistent with a Poisson distribution of mean log 2, pointing to affirmative answers to all four questions.

What carries the argument

The central objects are chains: consecutive strings of primes stored by their starting and ending prime indices, length m, and sum n. The key operation is a slide: remove the smallest prime and append the next prime after the largest, keeping length fixed and increasing the sum by p-q. The load-bearing estimate is that this increment averages Theta(m log(n/m)), which implies the number of chain sums landing in a window of length Delta is Theta(Delta/(m log(x/m))); this drives the cutoff mcutoff=Theta(x^(1/3)), the window size Delta=x^(2/3), and the space/time tradeoffs in the theorems. The priority-queue variant stores one chain per length in a min-heap keyed by the chain sum; each dequeue-s

What would settle it

Instrument the released implementation to record, by chain length m, the actual total increment from every slide and the actual number of slide operations up to a large bound such as 10^12, and compare with the predicted Theta(x log(x/m)); if the ratio grows without bound along a sequence of bounds, Lemma 2.3 and the O(x log x) theorems fail. A sharper spot-check is a single window of length Delta=x^(2/3) immediately after an unusually large gap between consecutive primes or a stretch with many close primes: if the number of chain sums in that window for each m is not Theta(Delta/(m log(x/m)))

Watch

Extended reading notes

Core claim

Theorem 2.6 of the paper is that the sliding-window 'puzzle' algorithm computes h(k,x) on input x in O(x log x) arithmetic operations and O(x^(2/3)) space. The priority-queue algorithm, which keeps one chain of each length in a min-heap keyed by sum, achieves O(x log x) time and O(x^(3/5)) space when primes are produced by an incremental interval sieve, or O(x(log x)^2) time and O(sqrt(x log x)) space when primes are produced by a pseudosquares prime test. The analysis is average-case over prime gaps: the basic estimate, Lemma 2.3, is that sliding a chain of length m with sum n changes the sum by Theta(m log(n/m)) on average. The implementations ran to x = 10^14 + 145300 (the paper notes tha

Load-bearing premise

The time bounds assume that when a chain of m consecutive primes is slid forward, the increase in its sum is, on average, m times the typical spacing between primes near the sum divided by m, and that deviations from this average cancel out over all chains and windows up to x; if prime gaps cluster or the average increment behaves differently for some chain lengths, the O(x log x) and O(x(log x)^2) claims fail.

Editorial extensions

If this is right

Exact histograms of representation counts up to 10^14 are now available, and the smallest integer with 14 representations, 84,941,668,414,584, extends the known record sequence from 13 to 14.
The histogram data match a Poisson distribution with mean log 2, which predicts densities (log 2)^k/(2 k!) for exactly k representations; if the trend holds, the answers to all four open questions are yes.
The time-space tradeoff gives a practical choice: the sliding-window algorithm parallelizes well and was run on 560 cores, while the priority-queue algorithm uses far less space but resists parallelization; extrapolating, the next interval [10^14, 10^15] would take roughly a year on current hardware and may contain the first integer with 15 representations.
If the average-case analysis is correct, the histograms can be pushed to larger x with more machines, making the next record value k=15 a concrete computational target.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The near-Poisson fit suggests a sharp test: h(0,x)/x should move from about 0.5226 at 10^14 toward the conjectured limit 1/2, and the excess of high-count values should shrink; checking this on the next factor of 10 would discriminate between a genuine limit and finite-size noise.
The same slide-based machinery should carry over to sums of consecutive terms of any sequence with a known average gap law, for example sums of consecutive squares of primes, by replacing only the average-increment lemma.
Because the analysis is average-case, a direct instrumentation of the released code, counting actual slide increments by chain length, would quantify how close reality is to the Theta(m log(n/m)) model; a persistent deviation would indicate that the time bounds are heuristic for the tested range.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Short version: this is a genuine contribution—first analysis of two known algorithms for the Moser histogram, plus a new computational record and data that bear on all four of Moser's questions. The authors credit Meyrignac and Branicky for the algorithms; what's new is the analysis and the run to 10^14. I checked several lemmas against PNT and Bertrand; they're consistent. The priority queue space bounds (x^(3/5) and sqrt(x log x)) look right, and the reported timings are compatible with the claims.

The soft spot is Lemma 2.3. The slide-cost average is asserted via the prime number theorem, but the work sums require cancellation of deviations over all chains and segments. The paper waves at this with 'variations from the average must cancel out,' but that's a claim about equidistribution of prime gaps, not a proof. Theorems 2.6, 3.2, 3.3 are stated unconditional but inherit this average-case assumption. If that cancellation fails for some length range, the time bounds could be superlinear. This is not a fatal flaw—the paper is upfront about average-case analysis—but the theorems should be labeled conditional on that heuristic, or the heuristic needs a real argument.

Minor issues: Lemma 3.1 has an exponent typo (x1^(1/3) where the proof needs x1^(2/3)); the '10^14' in the abstract is off by 145,300 (disclosed in a footnote); the Poisson model fits the histogram well except a visible, persistent gap in the k=0 bin, so the conjectured densities are plausible but shouldn't be sold as precise.

Who's it for: people working on additive problems with primes, and anyone implementing histogram algorithms for such sums. The data and code are real, and the record for k=14 will be cited. I'd bring it to reading group and would cite the record. For peer review: yes, send it out. The analysis is serious and mostly correct, but the referee should push on Lemma 2.3 and the conditional wording.

Referee Report

3 major / 5 minor

Summary. This paper studies two algorithms for computing h(k,x) = #{n ≤ x : f(n) = k}, where f(n) is the number of representations of n as a sum of consecutive primes. The first ("puzzle") algorithm processes [1,x] in sliding windows of size Δ and is claimed to run in O(x log x) time and O(x^{2/3}) space. The second ("priority queue") algorithm generates representations in increasing order of n; two variants are claimed to use O(x log x) time and O(x^{3/5}) space, or O(x(log x)^2) time and O(√(x log x)) space. The paper also reports computations to x ≈ 10^14 + 145300, including a new record integer with f(n) = 14, and uses histogram data to conjecture affirmative answers to Moser's four questions.

Significance. If the complexity theorems are correct, the paper substantially advances the feasible range for exact histogram computation and provides the first known n with 14 representations, a concrete OEIS contribution. The algorithms are clearly described, the code and data are available, and the Poisson heuristic is interesting. However, the main theorems are not proven as stated: the analysis relies on an average-case model of prime gaps (Lemma 2.3) without rigorous justification. The data and conjectures stand on their own, but the algorithmic analysis needs either stronger proofs or explicit conditional statements.

major comments (3)

[§2.3, Lemma 2.3 and Corollary 2.4] The average slide cost Θ(m log(n/m)) is the sole basis for the claimed per-segment chain counts, and hence for the O(x log x) and space bounds in Theorems 2.6, 3.2, and 3.3. The proof of Lemma 2.3 replaces a sum of m consecutive gaps by m times the PNT average and then appeals to cancellation over all segments. This is a heuristic. The theorems are stated unconditionally, but a non-uniform distribution of prime gaps could make the work superlinear. Please either prove a rigorous averaged bound (for example, by summing p_{i+m} - p_i over all chains and lengths) or explicitly restate the theorems as conditional on a stated heuristic model. A concrete diagnostic would be to report, from the runs to 10^14, the maximum and total deviation of per-segment chain counts from the predicted Δ/(m log x) values.
[§2.3.4, Lemma 2.5] The derivation of mcutoff = Θ(x/Δ) uses Corollary 2.4 and Equation (3), i.e. the same average-gap heuristic, to estimate the number s of slide operations needed to reach the first chain in a segment. Lemma 2.5 is then used in Theorem 2.6 to balance mcutoff and Δ, giving mcutoff = x^{1/3} and Δ = x^{2/3}. If the average estimate fails for some range of m, the balancing is invalid and the claimed O(x log x) bound is not established. The proof should either avoid the per-segment average by using global counts of chains, or be explicitly conjectural.
[§3, Theorems 3.2 and 3.3] These results inherit the same heuristic. In addition, the claim that each short chain's incremental sieve performs a slide in O(log x) average time, and the estimate that the number of short chains is Θ(x), are based on the same prime-gap average assumption. The space bound O(x^{3/5}) and the time bounds O(x log x) and O(x(log x)^2) are therefore conditional as written. The proof needs a rigorous amortized analysis of the incremental-sieve slides, or the theorems must be qualified as average-case/heuristic results.

minor comments (5)

[Abstract and §1] Typo: 'Meyrinac' should be 'Meyrignac'. Also 'Priorty' in §3.1's header should be 'Priority'.
[Algorithm 2, line 8] The condition '2 + slide(c).sum > x2' is unclear; the phrase '2 +' likely is a typo. Please clarify the intended construction of the initial chain.
[Tables 1 and 3] The footnote acknowledges that the tables labelled x = 10^14 actually use x = 10^14 + 145300. This should be corrected in the tables, not only in a footnote, since it affects the direct comparison with the Poisson expectation in Table 3.
[Table 5] The alignment of columns in Table 5 is confusing (especially the third column). Please reformat so that pmin and pmax are clearly separate columns, and use comma or thin-space separators consistently.
[§4.1] The phrase 'empty sum of a single prime' should be 'the sum of a single prime', since the paper counts a single prime as a representation.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the analysis is anchored in external facts (prime number theorem, Bertrand's postulate, Moser's average theorem) plus an explicitly labeled average-case assumption; no prediction reduces to a fitted input.

full rationale

The central complexity claims (Theorem 2.6 and Theorems 3.2/3.3) are proved by summing slide costs and prime counts. The load-bearing Lemma 2.3 estimates n(slide(c)) - n(c) as Theta(m log(n/m)) 'on average' using Lemma 2.1 and the prime number theorem; this is an explicit heuristic assumption, not an equation that identifies the conclusion with an input. Corollary 2.4 and Lemma 2.5 propagate that average-case estimate, but none of these steps is fitted to the histograms or to the running times they are supposed to prove. The computational results and Poisson conjecture use lambda = log 2 from Moser's independent average theorem, not fitted from Table 1; Table 3 shows real deviations from Poisson, so the model is predictive rather than a relabeling. The self-citations ([11], [12], and [8]) are implementation-level references (prime sieves and a prior sum-of-powers algorithm) and do not carry the argument's load. The footnote about Tables 1 and 3 using 10^14 + 145300 instead of 10^14 is a typographical inconsistency, not a circular step. No step in the derivation reduces to its own conclusion by definition or by self-citation.

Assumptions & free parameters 3 free parameters · 7 assumptions · 0 invented entities

The complexity bounds depend on standard facts (PNT, Bertrand, Moser's average-value theorem) plus one load-bearing but unproven average-case cancellation heuristic (axiom 4). The conjectured answers to Moser's questions additionally assume a Poisson model (axiom 6) whose fit shows a persistent deviation in the k = 0 bin. The design constants Delta, mcutoff, and B are chosen by the analysis, not fitted to data. No invented entities are introduced.

free parameters (3)

Delta (sliding window size) = x^(2/3) for the standard puzzle algorithm; x^(1/2) in the tradeoff discussion
Chosen by the balancing argument in section 2.3.4 to keep total work O(x log x); not fitted to data. The paper derives O(x^(1+3u) log x) time when Delta = x^(2/3-u).
mcutoff (chain-length cutoff) = Theta(x^(1/3))
The boundary between large-m (sliding) and small-m (sieve-based) processing. Lemma 2.5 derives mcutoff = Theta(x/Delta) on average, yielding x^(1/3) with Delta = x^(2/3).
B (stored prime bound, priority queue version) = x^(3/5)
Chosen in Theorem 3.2 to balance the O(B) prime-table space against the total space of incremental sieves attached to short chains; not fitted to data.

assumptions (7)

standard math Prime number theorem: pi(y) ~ y/log y, sums of the first u primes are ~ (u^2 log u)/2, and consecutive primes near y average log y apart.
Invoked in Lemma 2.1 (upper bound on p(m,x)), Lemma 2.2 (M(x) ~ 2 sqrt(x/log x)), Corollary 2.4, and Theorem 3.2's B = x^(3/5) balance. The final clause (average gap log y) is a heuristic use of PNT.
standard math Bertrand's postulate: for every prime p_j, the next prime p_{j+1} < 2 p_j.
Used in the Lemma 2.1 lower bound x/(m+2) < p(m,x).
domain assumption Moser's theorem: the average of f(n) for n <= x is log 2 + o(1).
Bounds the total number of representations as O(Delta) in the priority queue main loop (section 3.1.2) and fixes the mean lambda = log 2 in the Poisson model (section 4.1). Cited to [7] and not re-derived.
ad hoc to paper Average-case chain slide cost Theta(m log(n/m)) with cancellation of deviations over the whole run.
The load-bearing distributional assumption: Lemma 2.3 states the slide cost 'on average'; section 2.3 asserts variations 'must cancel out'. Theorems 2.6, 3.2, and 3.3 all depend on it; it is plausible but unproven as a worst-case statement.
domain assumption Atkin-Bernstein-Galway sieve finds primes on [a,b] in O(b - a + b^(1/3)) time and O(b^(1/3)) space.
Used in sections 2.3.4 and 3.1.2 / Theorem 3.2 to justify near-linear small-m processing and the per-chain sieve space sum. Cited to [2] and [4], not verified in this review.
domain assumption f(n) behaves like independent Poisson(log 2) random variables across n.
Explicitly conjectural in section 4.1 ('roughly Poisson with mean lambda = log 2'); the basis for the affirmative heuristic answers to Moser's questions and the conjectured densities (log 2)^k/(2 k!). Table 3 shows a systematic deviation (h(0)/x around 0.523 vs 0.5).
domain assumption Deterministic primality testing on 64-bit inputs is correct (fixed-base Miller-Rabin, pseudosquares, BPSW-style tests).
The record claim (Table 4) and histogram completeness depend on primality decisions in sections 2.3.4 and 3.1.2; plausible for 64-bit inputs, not formally verified here.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Analysis of Algorithms for Moser's Problems on Sums of Consecutive Primes." pith.science (2026). https://pith.science/paper/ISX5MMBI

@misc{pith2026250900236,
  author       = {Pith},
  title        = {Pith review of: Analysis of Algorithms for Moser's Problems on Sums of Consecutive Primes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ISX5MMBI}},
  note         = {Machine review of arXiv:2509.00236}
}

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.

Figures

Figures reproduced from arXiv: 2509.00236 by the authors.

**Figure 2.** Average number of representations below n order results include taking 3 days for x = 1011 and 6 hours cumulative for all smaller powers of ten. We also created a version of the priority queue algorithm using a custom min-heap implementation with primality testing, storing chain objects indexed by length in an array. The authors discussed splitting the min-heap into two separate structures, one to store short chain… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

[1]

https://oeis.org

The On-Line Encyclopedia of Integer Sequences. https://oeis.org

work page
[2]

A. O. L. Atkin and D. J. Bernstein. Prime sieves using binary quadratic forms. Math. Comp. , 73(246):1023–1030 (electronic), 2004

work page 2004
[3]

Algorithmic number theory

Eric Bach and Jeffrey Shallit. Algorithmic number theory. Vol. 1. Foun- dations of Computing Series. MIT Press, Cambridge, MA, 1996. Effi- cient algorithms. 23

work page 1996
[4]

William F. Galway. Dissecting a sieve to cut its need for space. In Al- gorithmic number theory (Leiden, 2000) , volume 1838 of Lecture Notes in Comput. Sci. , pages 297–312. Springer, Berlin, 2000

work page 2000
[5]

Richard K. Guy. Unsolved problems in number theory . Problem Books in Mathematics. Springer-Verlag, New York, third edition, 2004

work page 2004
[6]

Gary L. Miller. Riemann’s hypothesis and tests for primality. J. Com- put. System Sci. , 13(3):300–317, 1976

work page 1976
[7]

L. Moser. Notes on number theory. III. On the sum of consecutive primes. Canad. Math. Bull. , 6:159–161, 1963

work page 1963
[8]

Sorenson, and Aryn Stahl

Cathal O’Sullivan, Jonathan P. Sorenson, and Aryn Stahl. Algorithms and bounds on the sums of powers of consecutive primes. Integers, 24:Paper No. A4, 14, 2024

work page 2024

Show all 13 references

[9]

Michael O. Rabin. Probabilistic algorithm for testing primality. J. Number Theory, 12(1):128–138, 1980

1980
[10]

Puzzle 46.- primes expressible as sum of consecutive primes in k ways

Carlos Rivera. Puzzle 46.- primes expressible as sum of consecutive primes in k ways. https://primepuzzles.net/puzzles/puzz_046. htm. Accessed: 2025-06-03

2025
[11]

Sorenson

Jonathan P. Sorenson. The pseudosquares prime sieve. In Florian Hess, Sebastian Pauli, and Michael Pohst, editors, Proceedings of the 7th International Symposium on Algorithmic Number Theory (ANTS- VII), pages 193–207, Berlin, Germany, July 2006. Springer. LNCS 4076, ISBN 3-54...

2006
[12]

Sorenson

Jonathan P. Sorenson. Two compact incremental prime sieves. LMS Journal of Computation and Mathematics , 18(1):675–683, 2015

2015
[13]

Sums of consecutive prime squares

Janyarak Tongsomporn, Saeree Wananiyakul, and J¨ orn Steuding. Sums of consecutive prime squares. Integers, 22, 2022. A9. 24

2022

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.

[1] [1]

https://oeis.org

The On-Line Encyclopedia of Integer Sequences. https://oeis.org

work page

[2] [2]

A. O. L. Atkin and D. J. Bernstein. Prime sieves using binary quadratic forms. Math. Comp. , 73(246):1023–1030 (electronic), 2004

work page 2004

[3] [3]

Algorithmic number theory

Eric Bach and Jeffrey Shallit. Algorithmic number theory. Vol. 1. Foun- dations of Computing Series. MIT Press, Cambridge, MA, 1996. Effi- cient algorithms. 23

work page 1996

[4] [4]

William F. Galway. Dissecting a sieve to cut its need for space. In Al- gorithmic number theory (Leiden, 2000) , volume 1838 of Lecture Notes in Comput. Sci. , pages 297–312. Springer, Berlin, 2000

work page 2000

[5] [5]

Richard K. Guy. Unsolved problems in number theory . Problem Books in Mathematics. Springer-Verlag, New York, third edition, 2004

work page 2004

[6] [6]

Gary L. Miller. Riemann’s hypothesis and tests for primality. J. Com- put. System Sci. , 13(3):300–317, 1976

work page 1976

[7] [7]

L. Moser. Notes on number theory. III. On the sum of consecutive primes. Canad. Math. Bull. , 6:159–161, 1963

work page 1963

[8] [8]

Sorenson, and Aryn Stahl

Cathal O’Sullivan, Jonathan P. Sorenson, and Aryn Stahl. Algorithms and bounds on the sums of powers of consecutive primes. Integers, 24:Paper No. A4, 14, 2024

work page 2024