Questions tagged [prime-number-theorem]

The Prime Number Theorem is a theorem that describes the distribution of the primes. It says that the number of primes less than or equal to a real number $x$ is asymptotic to $\frac{x}{\ln x}$.

Filter by
Sorted by
Tagged with
1 vote
0 answers
52 views

Primality testing by reversible computation using the prime number theorem

Suppose we want to build a primality testing algorithm for the numbers limited to the set $A =\{1, ..., 2^n\}$ and $n$ is reasonably large. The prime-number theorem tells us that there are ...
user1747134's user avatar
0 votes
0 answers
61 views

Using Ehrhart polynomials to count primes?

As indicated below, one could use the Ehrhart polynomials of the simplex in number theory. Here are the questions without context first: Questions: The sum $$\sum_{k=0}^t (-1)^k ( \operatorname{...
mathoverflowUser's user avatar
5 votes
1 answer
503 views

Smallest prime factor of numbers

The literature refers to smooth integers as \begin{equation}\Psi(x,y):=\#\{n\le x:P_1(n)\le y\},\end{equation} where $P_1(n)$ is the largest prime factor of $n$. There are lots of results studying $\...
alidixon222's user avatar
2 votes
2 answers
403 views

"Squeezing" the primes?

The logical idea here is to map a curve that encodes the primes into the region $(0,1)^2$ and analyze the distribution there more easily and achieve tight bounds. To assess the distribution of primes, ...
53Demonslayer's user avatar
3 votes
1 answer
447 views

Prime number theorem via the explicit formula

Can the prime number theorem be obtained from the explicit formula, $\psi(x)=x-\sum_{\zeta(\rho)=0}\frac{x^\rho}{\rho}+O(1)$? Here, $\psi(x)=\sum_{k=1}^\infty\sum_{p^k<x}\log p$
Mustafa Said's user avatar
  • 3,679
0 votes
0 answers
81 views

Generalizations for the PNT to a subset of Dedekind domains?

The classical prime number theorem states that the prime counting function $$\pi(X) := \# \{ p \leq X \ | \ \text{$p$ prime} \}$$ is asymptotically equal to $X/\log(X)$. It is also known (and much ...
Simon Pohmann's user avatar
0 votes
0 answers
88 views

Mathematical simplification of Willans' formula for the prime counting function

Willans' formula for the prime counting function $\pi (n)$ becomes computationally intractable for large values of $n$. Has there been any work specifically on reducing this computational complexity, ...
David G. Stork's user avatar
2 votes
1 answer
135 views

Estimating the minimum number of distinct least prime factors found in range of $c$ consecutive integers

When I look at the count of distinct least prime factors for a range of consecutive integers, I am seeing the same minimum number appear again and again. I am wondering if this number represents the ...
Larry Freeman's user avatar
10 votes
1 answer
320 views

Vinogradov-Korobov prime number theorem for number fields

Without assuming the Riemann hypothesis, the traditional error bound of the prime-counting function $\pi(x)$ is $O(x\exp(-c(\log(x))^{1/2}))$. As shown by the Wikipedia page for the Landau prime ...
George Bentley's user avatar
21 votes
4 answers
3k views

What is the difference between elementary and non-elementary proofs of the Prime Number Theorem?

There is an easy proof of the PNT, just in a few lines, in the book by Julian Havil, "Gamma", pages 201-202. Specifically, Von Mangoldt's formula, which is very easy to derive: $$ \psi(x) = ...
Peter S.'s user avatar
  • 221
11 votes
2 answers
1k views

Mertens-like theorem

Mertens' first theorem states that $$ \sum_{p \leq n} \frac{\log p}{p} = \log n + O(1). $$ I read in this paper that the following variant is "classical": $$ \sum_{p \leq n} \frac{\log p}{p -...
Charles Bouillaguet's user avatar
1 vote
1 answer
121 views

Best possible unconditional partial sum estimate of $\sum_{p\leq x}\frac{\ln(p)}{({p})^{n/2}}$:

Consider the following partial sum: $$S(x,n)=\sum_{p\leq x}\frac{\ln(p)}{({p})^{n/2}}$$ Here p runs through primes and $n$ is constant What is the best possible unconditional( using best known version ...
Zaza's user avatar
  • 149
4 votes
1 answer
587 views

Reference for a proof of Euclid's Theorem for the infinitude of primes

I would be curious to have a reference for the following proof of Euclid's Theorem on the infinitude of primes: Using Legendre's formula (also called de Polignac's formula) for $p$-adic valuations of ...
Roland Bacher's user avatar
12 votes
4 answers
2k views

Proving Mertens' theorem using the prime number theorem

Mertens' Theorem states that $$\sum_{p \leq x}\frac{1}{p} = \log \log x + M + O(1/\log x).$$ This is weaker than the prime number theorem; in fact according to the Wikipedia page, the prime number ...
Daniel Loughran's user avatar
3 votes
1 answer
186 views

Density of semiprimes in arithmetic progression

Let $n,a,b$ be integers such that $n$ and $a$ are coprime, and $n$ and $b$ are also coprime. According to the Prime number theorem for arithmetic progressions, the primes which are $a\mod n$ have the ...
Riemann's user avatar
  • 537
2 votes
1 answer
270 views

Explicit bounds on number of primes of given size

How many prime numbers of $b$ bits are there? Beyond the prime number theorem, one can give explicit bounds on the number of primes below some integer $n$, or in a given interval. For instance, Rosser ...
Bruno's user avatar
  • 456
10 votes
0 answers
407 views

Are prime numbers among sums of prime numbers distributed as $\frac n{2\ln(n)}$?

Let $(s_n)_{n\in\mathbb N}$ be defined as follows: For $n\in\mathbb N$, $s_n:=2+3+5+\cdots+p_n$ is the sum of the first $n$ prime numbers (e.g.: $s_1=2$, $s_2=5$, $s_3=10$, $s_4=17$, $\ldots$). Let $\...
Tobias Schnieders's user avatar
2 votes
0 answers
189 views

An approach to the prime number theorem with Rademacher variables and a recursive formula for the prime pi function?

Consider the bipartite graphs defined here: Why is this bipartite graph a partial cube, if it is? We do random walks on them with equal propability and since the graphs are finite and connected the ...
mathoverflowUser's user avatar
0 votes
0 answers
126 views

Bounded sums involving primes

I'm trying to generalize the Theorem 2.7.1 in [1] where they prove: $$\sum_{p \leq x} f(p) = \int_{2}^{x} \frac{f(t)}{\log{t}} dt + \epsilon(x)f(x) - \int_{2}^{x} \epsilon(t) f^{'}(t) dt $$ where $\...
Pierluigi's user avatar
  • 109
0 votes
2 answers
263 views

How can I convert Meissel's/Lehmer's formula for prime counting to get sum of primes

Legendre's formula can be very easily be generalised as mentioned here (visible after login) which is like this ${\pi}(v,p)={\pi}(v,p-1)-1.[{\pi}(v/p,p-1)-{\pi}(p-1,p-1)]$ ${ \big\downarrow}$ $S(v,p)=...
ishandutta2007's user avatar
0 votes
0 answers
90 views

How to use prime number theorem In such cases?

Let, $$A(x)=\sum_{p\leq x}f(p)$$ Where $p$ is a prime number. Under the Prime Number theorem we have that, $$\pi(x)=Li(x)+O\left(\frac{x}{e^{a\sqrt{\ln(x)}}}\right) $$ as $x$ approach infinity. Now, $$...
RAHUL 's user avatar
  • 111
0 votes
1 answer
189 views

Geometric prime distribution

Let integers $\ a>1\ $ and $\ b\in\mathbb Z\ $ be relatively prime (hence $\ b\ne 0).\ $ The Dirichlet's prime distribution theorems apply to the arithmetic sequence $$ (_aG_b(x) : x\in\mathbb Z) $$...
Wlod AA's user avatar
  • 4,686
0 votes
0 answers
142 views

better estimates than the prime number Theorem in Euclidean domains

For a unique factorization domain we know that we have some the analogues of fundamental theorem of arithmetic, and can build elements by using 'building blocks'. For me the easiest examples are ...
Johnny Cage's user avatar
  • 1,543
2 votes
1 answer
264 views

Averages of Möbius function in arithmetic progressions

It is mentioned in multiple occasions here that the bound $$ \mathop{\sum_{n=1}^{N}}_{n\equiv a\mod l} \mu(n) = o(N) $$ is equivalent to the prime number theorem in arithmetic progressions. But I am ...
Krishnarjun's user avatar
2 votes
1 answer
126 views

Is $\lim_{s \rightarrow 1} E(f(X_s)) = \lim_{N \rightarrow \infty} \frac{1}{N} \sum_{k=1}^N f(k)$?

Let $s>1$ be a real number. We look at the zeta probability function / Zipf probability function defined as: $$P(X = n) = \frac{1}{n^s \zeta(s)}$$ Suppose $f: \mathbb{N} \rightarrow \mathbb{R}$ is ...
mathoverflowUser's user avatar
0 votes
0 answers
97 views

Primes in residue classes [duplicate]

For which sets of residue classes are there easy elementary proofs that there are infinitely many primes in them, which don’t require the machinery of proofs of Dirichlet’s theorem? Example: it’s ...
Joe Shipman's user avatar
8 votes
1 answer
805 views

Are there highly composite prime gaps?

Definition: Highly composite prime gap The three composite numbers between the consecutive primes $643$ and $647$ each have at least three distinct prime factors. This is the first occurrence of prime ...
Nilotpal Kanti Sinha's user avatar
1 vote
1 answer
256 views

Asymptotic lower bound for the number of square free with at least two prime factors

In one of Soundararajan's papers, he claims without proof that it is a standard exercise to show that the number $N(X)$ of positive square-free integers $d \equiv 1 \; \bmod \; 8$ less than $X$, with ...
Melanka's user avatar
  • 577
7 votes
2 answers
445 views

Asymptotics of $\operatorname{lcm} ((2-1), (3-1), (5-1), (7-1), (11-1), \dotsc, p_n-1 )$

$\DeclareMathOperator\lcm{lcm}$Let $p_k$ be the $k$th prime number. Set $$L(n) = \lcm(p_1-1, p_2-1, \dotsc, p_n-1). $$ What can we say about the growth of $L(n)$? Trivially, one has that $L(n) < ...
JoshuaZ's user avatar
  • 6,090
2 votes
1 answer
414 views

How essential is the vanishing of the Dirichlet $L$-functions to Dirichlet's theorem on primes in arithmetic progressions?

I seem to recall that the prime number theorem (PNT) is equivalent to the fact that the Riemann zeta function $\zeta(s)$ is non-zero on all of $\text{Re}(s) = 1$ (see https://math.stackexchange.com/...
D.R.'s user avatar
  • 681
4 votes
1 answer
227 views

Short proof of the error bound in PNT assuming a zero-free strip?

I am looking for a short proof of the fact that $\zeta(z)\neq 0$ for $\Re z>a$ implies the prime number theorem with an error bound $O(x^{a+\varepsilon})$ for any $\varepsilon>0$, which would be ...
Kostya_I's user avatar
  • 8,632
5 votes
2 answers
345 views

A lower-bound for the square-mean of Fourier coefficients of cusp forms at primes argument

There is a basis question which puzzles me for a while. The question is the following: Let $X\ge 2,$ and $\lambda(n)$ be the $n$-th Fourier coefficient of a $GL(2)$ newform of prime level $N>1$, ...
hofnumber's user avatar
  • 553
1 vote
0 answers
181 views

Do $k$ specific prime factors uniquely determine the continuous composite sequence of length $k$?

猜想:不存在两个长度为k且一共含有k个不同素因子的连续合数序列的素因子集合相等。例如 24 25 26 27 (2 3 5 13) 其余长度为4的连续合数序列要么素因子个数大于4 要么素因子集合不等于{2 3 5 13} 这个连续合数猜想的重大特定情况下的猜想。难度可与哥德巴赫猜想匹敌,非天才误入。再比如2 3 5 唯一决定了8 9 10 除此之外再无其他。总之经过计算机验证没有找到反例。 ...
光子精灵S's user avatar
9 votes
3 answers
569 views

Deriving an asymptotic for $\pi(x)$ directly from $\log \zeta(s)$?

Denote by $\pi(x)$ the number of primes $p\leq x$. We generally give approximations for $\pi(x)$ by first approximating $\psi(x) = \sum_{n\leq x} \Lambda(n)$. Part of the reason is presumably that, if ...
H A Helfgott's user avatar
  • 19.3k
20 votes
2 answers
4k views

information-theoretic derivation of the prime number theorem

Motivation: While going through a couple interesting papers on the Physics of the Riemann Hypothesis [1] and the Minimum Description Length Principle [2], a derivation(not a proof) of the Prime Number ...
Aidan Rocke's user avatar
  • 3,807
3 votes
0 answers
1k views

On new (purely analytic) perspective towards theory of prime numbers

[I'm going to ask this question very carefully as a question similar to this received a critical response on this platform. I myself am very skeptical about this but I want to know, from the experts' ...
bambi's user avatar
  • 375
1 vote
1 answer
184 views

Comparing densities of different gapped primes (twin, cousin, sexy...) [closed]

In this experiment, I have checked how many times different gapped primes occur out of the first 10000, 100000, 1000000 first primes. Please view the following as ($X$:$Y$) where $X$ represents the ...
Isaac Brenig's user avatar
2 votes
0 answers
289 views

Proving that the Riemann zeta function is zero free on Re=1 using the prime number theorem

Is $\frac{-\zeta'(s)}{\zeta(s)}+\frac{-s}{s-1}$ an analytic continuation, holomorphic for $Re\ s > 0,\ s\neq 1$, of $f(s)=s\int_{1}^{\infty}\frac{\psi(x)-x}{x^{s+1}}\mathrm{d}x$? If so: Let $s_{0}$ ...
Juu's user avatar
  • 129
4 votes
1 answer
375 views

Mertens formulas aren't enough for prime number theorem

For the primes it's true that $$ \sum_{p \le x}\frac{1}{p} = \ln\ln x + M + O(1/\ln x) $$ where, $M$ is suitable constant, and, moreover, the prime number theorem gives that $$ \lim_{x\to\infty}\frac{\...
user627482's user avatar
7 votes
2 answers
605 views

How to use the Prime Number Theorem in order to prove Selberg's Formula?

I`m reading Melvin B. Nathanson's "Elementary Methods in Number Theory" and I can't think of a way of deducing Selberg's formula (9.3) from the prime number theorem. This is one of the tasks ...
Juu's user avatar
  • 129
0 votes
0 answers
71 views

Repetitions of residua following a prime

NOTATION $\ p(0)\!=\!2\quad p(1)\!=\!3\quad\ldots\ $ -- the strictly increasing sequence $\ \mathbb P\ $ of all primes. Conjecture $$\forall_{k\in\mathbb Z_{>4}}\,\exists_{m\,n\in\mathbb P}\quad (\...
Wlod AA's user avatar
  • 4,686
3 votes
1 answer
331 views

$\pi(x+200)-\pi(x)\leq 50$?

Is it true, that $\forall x \in \mathbb N, \pi(x+200)-\pi(x) \leq 50 $ ? $$\pi(x)=\text{card}(\{n \in [0,x] \cap \mathbb N, n\text{ is prime}\})$$
Dattier's user avatar
  • 3,737
1 vote
1 answer
162 views

Density of gaussian primes inside consecutive disks centered along the real axis of complex plane

Let's define the family of consecutive subsets of $\mathbb{N}$: $$S_n =\{x \in \mathbb{N}\,:\,|x-n^2|\le n\}$$ With the previous definition we have that $$U_n=\bigcup_{k=1}^n S_k=\{x \in \mathbb{N}\,:\...
Augusto Santi's user avatar
2 votes
1 answer
248 views

Fermat's little theorem, Poulet numbers, Carmichael numbers, and primes

To begin with, i would like to apologize if my question is not up to the level of this forum. I have tried asking a variant of the following question on math.stackexchange.com and my question ...
Ilan Alon's user avatar
2 votes
0 answers
174 views

A question on $a_i(n) = a_i(\pi(n)) + a_i(n-\pi(n))$ with $a_i(n) = 1$ for $n \le i$

Let $a_i(n) = a_i(\pi(n)) + a_i(n-\pi(n))$ with $a_i(n) = 1$ for $n \le i$ where $\pi(n)$ is the prime-counting function. By definition, it is obvious that $a_1(n) = n$ and $a_2(n)$ is https://oeis....
Alkan's user avatar
  • 681
-2 votes
1 answer
174 views

Polynomials of minimum degree that interpolate primes in intervals

Given an interval $[a,b]$ what is the minimum degree of univariate polynomials in $\mathbb Q[x]$ that passes through all primes between $a$ and $b$ (denoted by $\mathbb P[a,b]$ with total number of ...
VS.'s user avatar
  • 1,816
8 votes
1 answer
639 views

Strange and non-strange prime numbers, are there infinitely many of them?

Definition. A prime number $p$ is called strange if there exists $k>1$ such that each prime divisior of $p^k-1$ divides $p-1$. Example 3. The prime number $p=3$ is strange as $3^2-1=8$ has the same ...
Taras Banakh's user avatar
  • 40.7k
-3 votes
1 answer
225 views

L. Gegenbauer's proof of Infinitude of Primes [closed]

I was going through the paper 'Euclid’S theorem on the infinitude of primes: A historical survey of its proofs' by Romeo Mestrovic where he mentioned that L. Gegenbauer proved Infinitude of Primes by ...
math is fun's user avatar
6 votes
1 answer
477 views

Understanding Sylvester' s $1871$ paper of primes in arithmetic progression of the forms $4n+3$ and $6n+5$

The following is the proof of infinitude of primes in arithmetic progression of the form $4n+3$ and $ 6n+5$ done by Sylvester in $1871$ in his paper "On the theorem that an arithmetical progression ...
math is fun's user avatar
5 votes
2 answers
413 views

Proving certain inequality related to Primes

I was reading the following paper. But I can't understand why the last line concerning $\frac{2}{\pi}$ is true. The proof is a work of Sylvester. I would be happy if someone helps me in understanding ...
math is fun's user avatar