Skip to content
Preprint

An Efficient Algorithm for Estimating Prime Counts

Jun 2026 · 0 citations · 14 references
Mathematics

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.

View source

Similar papers

Preprint Aug 2026

Sharp extremal asymptotics for Cusick's sum-of-digits bias at fixed Hamming weight

Let $s_2(n)$ be the binary sum-of-digits function and let $c_t$ be the natural density of the integers $n\ge0$ for which $s_2(n+t)\ge s_2(n)$. Earlier work of the author proved the universal exponential bound $$c_t-\frac12\ge 2^{-2s_2(t)-1},$$ thereby resolving Cusick's conjecture for every $t$. This estimate, however,...

Kai-Min Cheng · 0 citations
Preprint Aug 2026

A Sharper Explicit Result for the Sum of Two Almost Primes

We prove that for every integer $N\geq2$, there exist positive integers $a$ and $b$ such that $N=a+b$ and $\Omega(ab)\leq33$, where $\Omega(n)$ denotes the number of prime factors of $n$, counted with multiplicity. This improves the previous bound of $40$ obtained by Dudek and Dunn. The proof applies the explicit Fried...

Peter J. Campbell · 0 citations
Preprint Jul 2026

An improvement on the largest prime factors of consecutive integers

Let $P^+(n)$ denote the largest prime factor of $n$. One of Erd\H{o}s and Tur\'an's conjectures asserts that the asymptotic density of integers $n$ satisfying $P^+(n)<P^+(n+1)$ is 1/2. In this paper, we prove that this density is larger than 0.280, which improves the previous result 0.2017 by L\"u and Wang (2025). We a...

Z. Yang · 1 citation
Preprint Aug 2026

Ap\'ery-type approximations and irrationality measures for certain $q$-series

We construct a three-parameter family of rational approximations to values of $q$-hypergeometric series. Using these approximations, we prove that, for every integer $x$ with $|x|\geq2$, the values at $r=x^{-1}$ of Ramanujan's theta function $\psi(r)=\sum_{n\geq0}r^{n(n+1)/2}$, the generating function $\Delta(r)=\sum_{...

Junnosuke Koizumi, Anju Yokoi · 0 citations
Preprint Aug 2026

A Neighbouring-Denominator Case of the Erd\H{o}s--Mahler Conjecture

In 1939, Erd\H{o}s and Mahler conjectured that an irrational real number $\xi$ must be a Liouville number whenever $P(p_nq_n)$ is bounded for infinitely many convergents $p_n/q_n$, where $P(N)$ denotes the largest prime factor of a nonzero integer $N$. In this note, we prove a neighbouring-denominator case of their con...

Diego Marques · 0 citations
Preprint Jul 2026

Small Counterexamples to the Gaussian Moments Conjecture

We give explicit complex polynomials $P,Q$ in three independent standard real Gaussian variables such that \[ {\mathbb E}(P^m)=0,\qquad {\mathbb E}(QP^m)=m!\neq0 \] for every $m\geq1$. In natural complex linear coordinates, $P$ has five terms and total degree $4$. Hence the Gaussian Moments Conjecture is false in every...

Christopher D. Long · 2 citations · ⚡1

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.