All Questions
84 questions
6
votes
1
answer
2k
views
Difficulty with "A new elementary proof of the Prime Number Theorem" by Richter
I'm studying Richter's "A new elementary proof of the Prime Number Theorem" paper, and I'm finding some problems understanding some parts of it. For example, I don't see how to get, in Lemma ...
- 2,060
3
votes
0
answers
192
views
What smoothing to use for PNT-like results?
Consider a Dirichlet series $\sum_n a_n n^{-s}$ with desirable analytic properties (e.g., analytic extension to $\Re s>0$); one example would be $a_n=\mu(n)$. Say we want to estimate $\sum_{n\leq x}...
- 20.2k
-3
votes
1
answer
201
views
Formula for gaps between primes [closed]
The twin prime conjecture refers to:
$$
\liminf_{n\to \infty}\; p_{n+1} - p_{n} = 2.
$$
By reasoning I arrive at the following simple formula for gaps between primes:
\begin{align}
p_{...
- 26.9k
0
votes
0
answers
122
views
Explicit upper bounds on the number of primes up to the square of the $n^\text{th}$ prime number $p_n$
I'm looking for explicit upper bounds on the number of primes up to the square $m=p_n^2$ of the $n^\text{th}$ prime number.
Such estimates can rely on the knowledge of the exact number of primes up to ...
- 727
8
votes
1
answer
245
views
Asymptotic density of sums of consecutive primes
Call a positive integer respectable if it is a sum of consecutive prime numbers. For example, every prime numbers is respectable. So are $3+5=8$, $2+3+5=10$, $5+7=12$, $3+5+7=15$, $2+3+5+7=17$, $7+11=...
CommunityBot
- 1
5
votes
1
answer
737
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 $\...
- 105k
2
votes
2
answers
424
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, ...
- 1,126
2
votes
1
answer
1k
views
Given an even integer N, what is the minimum set of primes such that any even number x <= N can be expressed as the sum of two primes from the set?
Given an even integer N, what is the minimum set of primes such that any even number $x \leq N$ can be expressed as the sum of two primes in the set?
Goldbach's conjecture said Every even integer ...
- 1,944
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 -...
- 14.6k
21
votes
3
answers
6k
views
Why is the Chebyshev function relevant to the Prime Number Theorem
Why is the Chebyshev function
$\theta(x) = \sum_{p\le x}\log p$
useful in the proof of the prime number theorem. Does anyone have a conceptual argument to motivate why looking at $\sum_{p\le x} \log ...
CommunityBot
- 1
13
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 ...
- 50.6k
4
votes
1
answer
601
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 ...
- 118k
4
votes
1
answer
251
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 ...
- 4,713
30
votes
3
answers
4k
views
Heuristic argument for the prime number theorem?
Here is a bad heuristic argument for the prime number theorem. Let $n$ be a positive integer and assume that PNT holds up to $n$. Then $n$ itself is prime if and only if for each prime $p<n$ the ...
- 4,713
2
votes
1
answer
283
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 ...
- 105k
10
votes
0
answers
416
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 $\...
6
votes
4
answers
2k
views
Probability that randomly chosen integers from a restricted set of natural numbers are coprime
We know that the probability $P(k)$ of $k$ randomly chosen integers $(k \ge 2)$ from the set of natural number are coprime is
$$
P(k) = \frac{1}{\zeta(k)}.
$$
I am looking at a special case of ...
0
votes
0
answers
136
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 $\...
- 63.9k
0
votes
2
answers
302
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)=...
0
votes
1
answer
196
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) $$...
- 4,786
0
votes
0
answers
144
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 ...
- 869
1
vote
1
answer
317
views
An explicit value for a bound proof
I saw a proof that $|p_n - li^{-1}(n)| \leq n e^{-c \sqrt{\ln(n)}} $,
without saying anything about $c$ !
My questions is, what the explicit value of $c$ ??
It just says for some number $c$ without ...
- 105k
8
votes
1
answer
834
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 ...
- 114k
2
votes
1
answer
461
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/...
- 50.6k
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 ...
- 3,871
1
vote
1
answer
186
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 ...
- 1,097
2
votes
0
answers
313
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}$ ...
- 129
4
votes
1
answer
395
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{\...
- 41
7
votes
2
answers
636
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 ...
- 129
-2
votes
1
answer
181
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 ...
- 54.2k
9
votes
1
answer
699
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 ...
- 41.9k
6
votes
1
answer
499
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 ...
- 233
5
votes
2
answers
435
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 ...
- 7,013
5
votes
0
answers
137
views
Is finding positive integer solutions of $\zeta(a/b) = c$ equivalent to deciding the rationality of $\gamma$?
This question requires little bit of explanation of the background hence it is a bit lengthy. Note: The question was initially posted in MSE but did not get answers hence posting in MO.
For every ...
- 5,470
1
vote
1
answer
867
views
$n$th prime: a better approximation
Let $p_n$ be the $n$-th prime, then from Wikipedia I got that
$p_n \approx n \left(\ln n + \ln \ln n -1 + \frac{\ln \ln n-2}{\ln n}+\frac{6\ln \ln n-( \ln \ln n)^2-11}{\ln^2 n} \right)$.
What is a ...
- 345
8
votes
4
answers
2k
views
Asymptotic bounds on $\pi^{-1}(x)$ (inverse prime counting function)
What are the current best asymptotic bounds on $\pi^{-1}(x)$, where $\pi(x)$ denotes the prime counting function (number of primes at most $x$)?
In other words, I am curious about the state of the ...
CommunityBot
- 1
0
votes
1
answer
474
views
An upper bound for $\sqrt{p_{n+1}}$
Let $C$ be a positive constant. Is it true that for all sufficiently large integers $n$ the inequality $$\prod_{i=1}^n (1+\frac{1}{\sqrt{p_i}})>C\sqrt{p_{n+1}}$$ holds? (Here with $p_k$ is denoted ...
CommunityBot
- 1
29
votes
2
answers
3k
views
Is there a Kolmogorov complexity proof of the prime number theorem?
Lance Fortnow uses Kolmorogov complexity to prove an Almost Prime Number Theorem (https://lance.fortnow.com/papers/files/kaikoura.pdf, after theorem $2.1$): the $i$th prime is at most $i(\log i)^2$. ...
- 13.9k
13
votes
1
answer
2k
views
Why shouldn't this prove the Prime Number Theorem?
Denote by $\mu$ the Mobius function. It is known that for every integer $k>1$, the number $\sum_{n=1}^{\infty} \frac{\mu(n)}{n^k}$ can be interpreted as the probability that a randomly chosen ...
- 32.5k
0
votes
1
answer
256
views
Lower bound for $\prod_{p\equiv 3 \pmod 4} p^{v_p(n!)}$
What is the best lower bound known for $$\prod_{p\equiv 3 \pmod 4} p^{v_p(n!)},$$ where the product is taken over all the primes(congruent to $3$ modulo $4$) less than or equal to $n$.
- 12.8k
3
votes
2
answers
386
views
Prime divisors of $\prod_{i=1}^n (i^2+1)$
Is it true that for every positive integer $n$ there is a prime $p>n,$ which divides $\prod_{i=1}^n (i^2+1)$ ?
- 23k
5
votes
0
answers
193
views
Asymptotic expansion for the average of $\omega(n)^2$
Let $\omega(n)$ be the prime factors counting function. I computed that for any $k\geq 0$, there exist certain constants $c_{-1},c_0,c_1,c_2,...c_k$ such that
$$\sum_{n\leq x}\omega(n)^2=x(\log\log x)...
7
votes
1
answer
1k
views
A curious prime counting approximation or just data overfitting?
I am not sure, if this is a research problem. If not I will move this question to ME:
Let $\Omega(n) = \sum_{p|n} v_p(n)$, which we might view as a random variable.
Let $E_n = \frac{1}{n} \sum_{k=1}^n\...
- 105k
36
votes
2
answers
7k
views
Why do primes dislike dividing the sum of all the preceding primes?
I was investigating primes with the property that the sum of the first $n$ primes is divisible by $p_n$. It turns out that these primes are extremely extremely rare. For primes less than $10^9$, I ...
CommunityBot
- 1
20
votes
4
answers
2k
views
Can anything deep be said uniformly about conjectures like Goldbach's?
This is a soft question sparked by my curiosity about the intrinsic depth of Goldbach-like conjectures as perceived by current experts in number theory. The incompleteness theorem implies that, if our ...
- 20.2k
2
votes
2
answers
1k
views
What is the natural density of hyper prime numbers?
What do we mean by hyper prime numbers? Well, roughly speaking they are natural numbers which are prime with respect to hyperoperators in arithmetic such as exponentiation, tetration, pentation, et ...
CommunityBot
- 1
6
votes
2
answers
411
views
A simultaneous generalization of the Grunwald-Wang and Dirichlet Theorems on primes
By Grunwald-Wang Theorem, if for some odd number $n$ the equation $x^n=a$ has no solutions in $\mathbb Z$, then the equation $x^n=a\mod p$ has no solutions for some prime number $p$. I am interested ...
- 20.8k
3
votes
0
answers
206
views
Cancellation in this exponential sum?
I would like to know whether it is possible to obtain cancellation in the sum
$$\sum_{p \leq X} e^{{2\pi iX}/{p}}$$
where $X$ is a real number that goes to $\infty$, and $p$ denotes a prime number.
- 12.8k
3
votes
2
answers
2k
views
Prime counting. Meissel, Lehmer: is there a general formula?
I am looking for a general forumla to count prime numbers on which the Meissel and Lehmer formula are based:
$$\pi(x)=\phi(x,a)+a-1-\sum\limits_{k=2}^{\lfloor log_{p_{(a+1)}}(x) \rfloor}{P_k(x,a)}$$
...
- 91
13
votes
2
answers
2k
views
Asymptotics of the n-th prime using the gamma function
In the paper http://rgmia.org/papers/v8n2/eepnt.pdf, the author proves that proves an explicit inequality on prime numbers using the gamma function and as a corollary, he showed that.
$$
p_n = n \...
- 655