{"id":"b27773c4-5e5f-44b5-a45b-c708d9995974","arxiv_id":"2509.00236","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Two existing algorithms that count representations as sums of consecutive primes are analyzed, giving O(x log x) time with sublinear memory, and run to 10^14, producing the first integer with 14 representations and heuristic yes-answers to Moser's four questions.","lead":"This paper analyzes two known algorithms that count how many ways each number can be written as a sum of consecutive primes, and runs them to find all such counts up to about 10^14. The value is practical: it gives the first formal time and memory analysis of these methods and extends the known record, offering evidence for four open questions posed by Moser in 1963.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Time bounds rest on unproven average-case prime-gap heuristics: Lemma 2.3 underlies Theorems 2.6, 3.2, and 3.3, so if slide costs do not cancel as claimed, the O(x log x) / O(x log^2 x) guarantees are not established.","rationale":"The reader's weakest_assumption identifies exactly the same load-bearing concern: the average-case prime-gap model in Lemma 2.3 underlies the time bounds of the main theorems. My reading of the manuscript confirms that Corollary 2.4 and the work sums in Sections 2.3.3/2.3.4 and Theorem 3.2 all inherit this assumption. The paper's own justification (Section 2.3) explicitly states a cancellation heuristic rather than a proof. I found no other issue that is more load-bearing: the Lemma 3.1 setup-bound typo (x1^(1/3) vs x1^(2/3)) is minor since the corrected bound still leaves setup negligible; the abstract's off-by-145,300 range is disclosed in a footnote; and the Poisson-model discrepancy in the k=0 bin does not affect the algorithmic complexity claims. Thus the appropriate verdict remains CONDITIONAL: the computational results and data are credible, but the central complexity theorems should be presented as conditional on an unproved prime-gap equidistribution assumption, or supported by a rigorous bound. The reader already reached this conclusion, so no verdict change is needed.","tokens_in":13383,"tokens_out":4358,"duration_ms":53166,"concrete_test":"Instrument the authors' published code to record, for each length m and each segment, the actual number of slide operations and the actual sum of slide increments, for x = 10^10, 10^11, and 10^12. Compare the per-(m, segment) chain counts against Delta/(m log(x/m)) from Corollary 2.4, and compare cumulative work against C x log x. If the maximum relative deviation over all segments and lengths does not shrink with x, or if the cumulative work exceeds the predicted bound by a growing factor, the cancellation assumption underlying Lemma 2.3 is empirically false in the tested range. For a definitive analytical resolution, replace Lemma 2.3 with a rigorous discrepancy bound (e.g., via the Brun-Titchmarsh theorem or large-sieve estimates) and re-derive Theorems 2.6 and 3.2; if the resulting time bound is no longer O(x log x) without unproved assumptions, the theorems must be restated as condi","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central algorithmic claims—Theorem 2.6 (puzzle algorithm: O(x log x) time, O(x^(2/3)) space) and Theorems 3.2/3.3 (priority queue: O(x log x) time with O(x^(3/5)) space, or O(x (log x)^2) with O(sqrt(x log x)) space)—are all proved through Corollary 2.4 and Lemma 2.3. Lemma 2.3 asserts that n(slide(c)) - n(c) has average value Theta(m log(n/m)). The proof is heuristic: it invokes the prime number theorem to say consecutive primes near p are, on average, log p apart, so a slide changes the sum by roughly (p + log p) - (p - m log p) = (m+1) log p. This is a statement about the mean gap, but the algorithm's actual work is the sum of slide costs over all chains, and the per-segment, per-length chain counts depend on the distribution of prime gaps in intervals of length roughly Delta/m. The paper's justification (Section 2.3) is that 'significant variations from the average must cancel out, as the algorithm examines all primes and all chains up to x.' This cancellation is a non-trivial equidistribution claim about prime gaps; it is not proved. If, for some range of lengths m or segments, slide costs are systematically larger than the PNT average (e.g., due to prime clusters or large gaps), the work sums in Sections 2.3.3-2.3.4 and Theorem 3.2 could be superlinear. The theorems are therefore stated as unconditional when the proofs are conditional on an unproved prime-gap heuristic. This is the single most load-bearing concern: everything else (space counts, setup costs, lemma 3.1 typo, range off-by-145300) is minor and fixable, but a failure of Lemma 2.3 would invalidate the main complexity conclusions.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":13751,"tokens_out":16857,"duration_ms":192198,"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":[{"comment":"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.","section":"§2.3, Lemma 2.3 and Corollary 2.4"},{"comment":"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.","section":"§2.3.4, Lemma 2.5"},{"comment":"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.","section":"§3, Theorems 3.2 and 3.3"}],"minor_comments":[{"comment":"Typo: 'Meyrinac' should be 'Meyrignac'. Also 'Priorty' in §3.1's header should be 'Priority'.","section":"Abstract and §1"},{"comment":"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.","section":"Algorithm 2, line 8"},{"comment":"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.","section":"Tables 1 and 3"},{"comment":"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.","section":"Table 5"},{"comment":"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.","section":"§4.1"}],"recommendation":"major_revision","confidential_remarks":"The manuscript's computational contribution is solid and the new record is a useful OEIS update. The main issue is that the stated complexity theorems are not proven as unconditional statements; they depend on an unproved average-case model of prime gaps. If the authors can either supply rigorous proofs for the relevant averaged quantities (perhaps using telescoping sums over all chains) or explicitly recast the theorems as conditional on a standard heuristic, the paper would be acceptable. As it stands, the gap between theorem statements and proofs is too large for a journal to certify the central claim."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nMinor 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.\n\nWho'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.","headline":"Real algorithmic analysis with an honest record, but the headline time bounds lean on an unproved prime-gap cancellation; revise or label conditional.","tokens_in":14451,"tokens_out":2680,"would_cite":true,"duration_ms":25651,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["11N05","11Y16","11Y55"],"pacs":[],"model":"deepseek-v4-flash","headline":"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","keywords":["sums of consecutive primes","representation counting function","histogram computation","sliding window algorithm","priority queue algorithm","average-case analysis","prime gaps","computational number theory"],"falsifier":"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)))","tokens_in":13125,"feed_emoji":"🔢","tokens_out":14340,"duration_ms":151915,"temperature":0.7,"pith_summary":"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.","feed_headline":"First known integer with 14 prime-sum representations found","feed_subtitle":"Near-linear, low-memory algorithms compute the histogram to 10^14 and suggest yes on all four open questions.","key_machinery":"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","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the counting function f(n), proves its average value is log 2, and poses the four open questions the paper addresses.","marker":"[7]"},{"why":"Describes the sliding-window approach the paper names the puzzle algorithm and then fills in and analyzes.","marker":"[10]"},{"why":"Supplies the Python priority-queue implementation for a histogram over sums of consecutive primes, which the paper restates and analyzes, and the record sequence extended to k=14.","marker":"[1]"},{"why":"Supplies the asymptotic for sums of the first primes used to bound M(x) and p(m,x) in Lemmas 2.1 and 2.2.","marker":"[3]"},{"why":"Provides the Atkin-Bernstein prime sieve underlying the interval sieve used in the low-space variants.","marker":"[2]"},{"why":"Shows how to sieve an interval of primes in O(b-a+b^(1/3)) time and O(b^(1/3)) space, critical for small-m processing and the low-space priority-queue version.","marker":"[4]"},{"why":"Supplies the pseudosquares prime-test method that yields the O((log x)^2) per-slide cost in the low-space variant.","marker":"[11]"}],"fun_headline_variants":["Near-linear algorithms for sums of consecutive primes","Prime-sum histogram: O(x log x) time, tiny memory","Moser's prime-sum questions answered by new data","Fast, low-memory count of consecutive prime sums","Cracking Moser's prime-sum problems with two algorithms"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Near-linear algorithms for sums of consecutive primes","Prime-sum histogram: O(x log x) time, tiny memory","Moser's prime-sum questions answered by new data","Fast, low-memory count of consecutive prime sums","Cracking Moser's prime-sum problems with two algorithms"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000313,"raw_usage":{"total_tokens":1639,"prompt_tokens":793,"completion_tokens":846,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":537,"completion_tokens_details":{"reasoning_tokens":768}},"tokens_in":537,"tokens_out":846,"duration_ms":9897,"temperature":1.0,"reasoning_tokens":768,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T13:52:41.129078+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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)))","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the counting function f(n), proves its average value is log 2, and poses the four open questions the paper addresses."},{"cited_title":"Puzzle 46.- primes expressible as sum of consecutive primes in k ways","cited_arxiv_id":null,"evidence_quote":"Describes the sliding-window approach the paper names the puzzle algorithm and then fills in and analyzes."},{"cited_title":"https://oeis.org","cited_arxiv_id":null,"evidence_quote":"Supplies the Python priority-queue implementation for a histogram over sums of consecutive primes, which the paper restates and analyzes, and the record sequence extended to k=14."},{"cited_title":"Algorithmic number theory","cited_arxiv_id":null,"evidence_quote":"Supplies the asymptotic for sums of the first primes used to bound M(x) and p(m,x) in Lemmas 2.1 and 2.2."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Atkin-Bernstein prime sieve underlying the interval sieve used in the low-space variants."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows how to sieve an interval of primes in O(b-a+b^(1/3)) time and O(b^(1/3)) space, critical for small-m processing and the low-space priority-queue version."},{"cited_title":"Sorenson","cited_arxiv_id":null,"evidence_quote":"Supplies the pseudosquares prime-test method that yields the O((log x)^2) per-slide cost in the low-space variant."}],"review_version":1}