An Efficient Algorithm for Estimating Prime Counts

Artur Samojluk; Artur Siemaszko

REVIEW 3 major objections 2 minor 7 references

A partition from generalized triangular numbers produces an incremental O(√x) estimator for the prime counting function π(x) with a fitted correction term.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · grok-4.3

2026-07-01 03:38 UTC pith:SNC6FWOU

load-bearing objection Incremental estimator via triangular-number partitions plus a fitted correction that matches pi(x) to 10^19, but the correction has no derivation or stability argument. the 3 major comments →

arxiv 2606.31761 v1 pith:SNC6FWOU submitted 2026-06-30 math.NT

An Efficient Algorithm for Estimating Prime Counts

Artur Samojluk , Artur Siemaszko This is my paper

classification math.NT

keywords prime counting functionpi(x) approximationgeneralized triangular numbersincremental estimatorO(sqrt x) complexitynumerical correction termnumber theoretic computation

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper constructs an estimator for π(x) by partitioning the integers up to x according to a non-uniform scheme based on generalized triangular numbers. This partition permits each new integer to be incorporated through strictly local adjustments, so that the total work to reach x scales as O(√x) while each individual update costs amortized constant time. Extensive numerical trials supply a single correction term that reduces the discrepancy between the estimator and the true π(x) to levels comparable with classical analytic formulas, at least for all tested arguments up to 10^19. The resulting procedure therefore supplies repeated estimates of prime counts at lower per-query cost than full analytic machinery while retaining the same order of accuracy on the examined range.

Core claim

The paper presents an algorithm that approximates π(x) via a structured non-uniform partition derived from generalized triangular numbers; the resulting incremental estimator requires only local computations for each update, yielding amortized O(1) update complexity and overall O(√x) time, and a correction term obtained by numerical fitting improves the approximation so that computational tests up to 10^19 agree with known values of π(x) at accuracy comparable to classical analytic approximations.

What carries the argument

Structured non-uniform partition derived from generalized triangular numbers, which supports local incremental updates to the estimator.

Load-bearing premise

The correction term fitted to data up to 10^19 will continue to improve accuracy for all larger x without further adjustment.

What would settle it

Compute the exact value of π(x) for some x larger than 10^19 and measure whether the absolute error of the corrected estimator remains comparable to the error of the uncorrected estimator or to classical analytic approximations.

Watch this falsifier — get emailed when new claim-graph text bears on it.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

Incremental estimator via triangular-number partitions plus a fitted correction that matches pi(x) to 10^19, but the correction has no derivation or stability argument.

read the letter

The paper's main concrete piece is a non-uniform partition of the integers up to x built from generalized triangular numbers. This lets the estimator update locally when x grows, giving amortized O(1) per step and total O(sqrt(x)) work. They also report a correction term tuned on data up to 10^19 that brings the error down to roughly the level of classical analytic approximations.

The partition choice itself is a specific, reproducible construction, and the incremental property is a practical plus for repeated queries. The reported agreement with known pi(x) values through 10^19 is straightforward evidence that the scheme functions in that range.

The correction term is the weak point. It is described as the result of numerical experimentation rather than any derivation or asymptotic analysis, so its continued usefulness past 10^19 rests on an untested assumption. Without an error bound or stability argument, the accuracy claim is essentially an extrapolation. The abstract also gives no derivation of the stated complexity and no side-by-side comparison with existing O(x^{1/2+eps}) or better methods.

The work is aimed at computational number theorists who need fast, repeatable estimates rather than theoretical improvements. A reader who wants to implement or benchmark an incremental counter could extract the partition rule and test it directly.

I would send it to referees so the full algorithm, the exact form of the correction, and any supporting analysis can be checked. The empirical results are clear enough to justify that step, but the lack of justification for the correction needs to be addressed.

Referee Report

3 major / 2 minor

Summary. The paper proposes an algorithm for approximating π(x) via a structured non-uniform partition based on generalized triangular numbers. It claims an incremental estimator with amortized O(1) per-update cost yielding overall O(√x) complexity, augmented by a correction term obtained via numerical fitting that improves accuracy, with tests up to 10^19 reported to match known π(x) values at a level comparable to classical analytic approximations.

Significance. If the claimed complexity were rigorously derived and the correction term shown to be stable or asymptotically justified beyond the fitting range, the approach could supply a lightweight incremental method for repeated π(x) estimates. The current manuscript, however, supplies neither a derivation of the complexity bound nor an analysis of the correction term, so the practical utility rests on an unverified empirical extrapolation.

major comments (3)

[Abstract] Abstract: the total complexity is asserted to be O(√x) with amortized O(1) updates, yet no derivation, recurrence, or operation-count analysis supporting this bound appears anywhere in the manuscript.
[Abstract] Abstract (correction term paragraph): the accuracy improvement is attributed to a correction term 'obtained through extensive numerical experimentation' up to 10^19, but the manuscript provides neither the explicit functional form, an error bound, nor any argument that the term remains effective for x ≫ 10^19 without refitting.
[Computational tests] Computational tests section: agreement with known π(x) values is reported up to 10^19, but no a-priori error analysis or comparison against the size of the fitted correction term is supplied, leaving the claimed comparability to analytic approximations dependent on post-hoc fitting.

minor comments (2)

[Abstract] The abstract refers to 'generalized triangular numbers' without an immediate definition or reference; a brief definition or citation in the introduction would improve readability.
[Method description] Notation for the partition and the incremental estimator is introduced without an explicit equation or pseudocode block; adding one would clarify the local-update claim.

Simulated Author's Rebuttal

3 responses · 1 unresolved

We thank the referee for the constructive comments. We address each major point below and will revise the manuscript to supply the requested derivations, explicit forms, and analyses where feasible.

read point-by-point responses

Referee: [Abstract] Abstract: the total complexity is asserted to be O(√x) with amortized O(1) updates, yet no derivation, recurrence, or operation-count analysis supporting this bound appears anywhere in the manuscript.

Authors: The O(√x) bound follows from the partition into O(√x) generalized triangular numbers with amortized O(1) local updates per step. We acknowledge the absence of a formal derivation in the current text and will add a subsection deriving the recurrence for partition sizes together with an explicit operation count establishing the claimed complexity. revision: yes
Referee: [Abstract] Abstract (correction term paragraph): the accuracy improvement is attributed to a correction term 'obtained through extensive numerical experimentation' up to 10^19, but the manuscript provides neither the explicit functional form, an error bound, nor any argument that the term remains effective for x ≫ 10^19 without refitting.

Authors: The revised manuscript will state the explicit functional form of the correction term and describe the fitting procedure. We will also supply an empirical error bound based on residuals up to 10^19. No theoretical argument is available that guarantees effectiveness for x ≫ 10^19 without refitting; we will explicitly note the empirical character of any extrapolation. revision: partial
Referee: [Computational tests] Computational tests section: agreement with known π(x) values is reported up to 10^19, but no a-priori error analysis or comparison against the size of the fitted correction term is supplied, leaving the claimed comparability to analytic approximations dependent on post-hoc fitting.

Authors: We will expand the computational tests section to include a comparison of the approximation error against the magnitude of the fitted correction term and to present the observed residuals as an empirical error indicator. This will clarify the basis for the reported comparability within the tested range. revision: yes

standing simulated objections not resolved

A rigorous (non-empirical) argument that the correction term remains effective for x ≫ 10^19 without refitting

Circularity Check

1 steps flagged

Fitted correction term makes reported accuracy improvement reduce to empirical fit on tested range

specific steps

fitted input called prediction [abstract]
"A correction term obtained through extensive numerical experimentation significantly improves the approximation accuracy. Computational tests for values up to 10^19 show strong agreement with known values of π(x), with accuracy comparable to classical analytic approximations"

The correction term is calibrated directly on the same numerical data (up to 10^19) against which agreement is then reported. The accuracy improvement and 'strong agreement' are therefore measured on the fitted set, making the performance gain equivalent to the input fit by construction rather than an independent prediction or derivation.

full rationale

The paper's algorithmic core (structured partition from generalized triangular numbers yielding amortized O(1) updates and O(√x) total cost) is presented as independently derived. However, the load-bearing accuracy claim rests on a correction term obtained solely by numerical fitting to π(x) data up to 10^19; the reported 'strong agreement' with known values up to the same limit is therefore on the fitted data. This matches the fitted-input-called-prediction pattern: the improvement is statistically forced within the calibration range rather than independently verified. No derivation or stability argument for the term is supplied, so the practical-utility assertion reduces partially to the fit. The complexity claim itself does not reduce by construction, yielding a moderate circularity score.

Axiom & Free-Parameter Ledger

1 free parameters · 0 axioms · 0 invented entities

The central performance claim rests on an experimentally fitted correction term whose explicit form and justification are not supplied in the abstract.

free parameters (1)

correction term
Obtained through extensive numerical experimentation to improve accuracy

pith-pipeline@v0.9.1-grok · 5632 in / 1107 out tokens · 59552 ms · 2026-07-01T03:38:47.298678+00:00 · methodology

0 comments

read the original abstract

We propose an efficient algorithm for approximating the prime counting function $\pi(x)$ using a structured non-uniform partition derived from generalized triangular numbers. The method yields an incremental estimator whose updates require only local computations, resulting in amortized $O(1)$ update complexity and total complexity $O(\sqrt x)$. A correction term obtained through extensive numerical experimentation significantly improves the approximation accuracy. Computational tests for values up to $10^{19}$ show strong agreement with known values of $\pi(x)$, with accuracy comparable to classical analytic approximations, while maintaining a substantially simpler incremental evaluation scheme. The proposed framework may be useful in large-scale computational number theory applications requiring fast repeated estimates of $\pi(x)$.

discussion (0)

Reference graph

Works this paper leans on

7 extracted references · 7 canonical work pages · 1 internal anchor

[1]

R. C. Baker, G. Harman, and J. Pintz. The difference between consecutive primes. II. Proc. London Math. Soc. (3), 83(3). 532- 562, 2001

work page 2001
[2]

J. Büthe. An analytic method for boundingψ(x), arXiv:1511.02032, Bib- code:2015arXiv151102032B

work page internal anchor Pith review Pith/arXiv arXiv
[3]

Heath-Brown, The number of primes in a short interval

D.R. Heath-Brown, The number of primes in a short interval. Journal für die reine und angewandte Mathematik (1988) Volume: 389, page 22-63 8

work page 1988
[4]

Hoheisel, Primzahlprobleme in der Analysis

G. Hoheisel, Primzahlprobleme in der Analysis. Sitz. Preuss. Akad. Wiss. Phys.- Math. Kl. (1930), 580-588

work page 1930
[5]

Huxley, On the difference between consecutive primes

M.N. Huxley, On the difference between consecutive primes. Inventiones math. 15, 164-170 (1972)

work page 1972
[6]

Oliver, Robert, Soundararajan, Kannan. (2016). Unexpected biases in the distri- bution of consecutive primes. Proceedings of the National Academy of Sciences

work page 2016
[7]

10.1073/pnas.1605366113. 9

work page doi:10.1073/pnas.1605366113

[1] [1]

R. C. Baker, G. Harman, and J. Pintz. The difference between consecutive primes. II. Proc. London Math. Soc. (3), 83(3). 532- 562, 2001

work page 2001

[2] [2]

J. Büthe. An analytic method for boundingψ(x), arXiv:1511.02032, Bib- code:2015arXiv151102032B

work page internal anchor Pith review Pith/arXiv arXiv

[3] [3]

Heath-Brown, The number of primes in a short interval

D.R. Heath-Brown, The number of primes in a short interval. Journal für die reine und angewandte Mathematik (1988) Volume: 389, page 22-63 8

work page 1988

[4] [4]

Hoheisel, Primzahlprobleme in der Analysis

G. Hoheisel, Primzahlprobleme in der Analysis. Sitz. Preuss. Akad. Wiss. Phys.- Math. Kl. (1930), 580-588

work page 1930

[5] [5]

Huxley, On the difference between consecutive primes

M.N. Huxley, On the difference between consecutive primes. Inventiones math. 15, 164-170 (1972)

work page 1972

[6] [6]

Oliver, Robert, Soundararajan, Kannan. (2016). Unexpected biases in the distri- bution of consecutive primes. Proceedings of the National Academy of Sciences

work page 2016

[7] [7]

10.1073/pnas.1605366113. 9

work page doi:10.1073/pnas.1605366113