An Efficient Algorithm for Estimating Prime Counts

Artur Samojluk; Artur Siemaszko

An Efficient Algorithm for Estimating Prime Counts

T0 review · 3 major / 2 minor · reviewed 2026-07-01 · grok-4.3

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

Pith's one-line read A partition from generalized triangular numbers produces an incremental O(√x) estimator for the prime counting function π(x) with a fitted correction term.

desk verdict 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 →

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

Artur Samojluk , Artur Siemaszko This is my paper · ORCID

classification math.NT

keywords primecountingfunctionpi(x)approximationgeneralizedtriangularnumbersincrementalestimatorO(sqrtx)complexitynumericalcorrectiontermnumbertheoreticcomputation

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

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.

What carries the argument

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

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

Extended reading notes

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.

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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

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 · score 6.0 of 10

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

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.

Assumptions & free parameters 1 free parameters · 0 assumptions · 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

how reviews work

0 comments

Cite this review

Pith. "Pith review of An Efficient Algorithm for Estimating Prime Counts." pith.science (2026). https://pith.science/paper/SNC6FWOU

@misc{pith2026260631761,
  author       = {Pith},
  title        = {Pith review of: An Efficient Algorithm for Estimating Prime Counts},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SNC6FWOU}},
  note         = {Machine review of arXiv:2606.31761}
}

abstract

We develop the Samojluk--Siemaszko (S--S) estimator for the prime-counting function $\pi(x)$ using a non-uniform partition generated by generalized triangular numbers. A cold-start evaluation uses $\big O(\sqrt{x})$ local terms, whereas consecutive partition nodes can be processed with amortized $\big O(1)$ update cost. Updated computations up to $10^{19}$, performed with the correction coefficient $c_T=0.7071$, show accuracy comparable with the Riemann approximation $R(x)$; the two estimators are also asymptotically equivalent at the level of their main term. The correction is written as a one-parameter family $S_{\ell,c}(x)$. Finite-range experiments indicate that effective coefficients lie near $0.7$. We prove asymptotic formulas for the natural scale $q_\ell(x)$ and the accumulated discretization error $D_\ell(x)$, obtaining an unconditional transfer relation between the normalized S--S error and the classical normalized prime-number-theorem error. Together with the logarithmic-mean theorem under RH, this identifies the exact coefficient $c_{\mathrm{th}}=1/\sqrt2$ as uniquely asymptotically optimal in the logarithmic-mean centering sense. The converse implication is quoted from a companion manuscript in preparation.

Discussion (0). Continue with ORCID to comment.

Pith tools

Reviewed July 1, 2026 · model on record in the stance chip above.