All Questions
84 questions
46
votes
4
answers
8k
views
Why could Mertens not prove the prime number theorem?
We know that
$$
\sum_{n \le x}\frac{1}{n\ln n} = \ln\ln x + c_1 + O(1/x)
$$
where $c_1$ is a constant. Again Mertens' theorem says that the primes $p$ satisfy
$$
\sum_{p \le x}\frac{1}{p} = \ln\ln ...
- 5,460
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 ...
- 5,460
32
votes
3
answers
8k
views
Ideas in the elementary proof of the prime number theorem (Selberg / Erdős)
I'm reading the elementary proof of prime number theorem (Selberg / Erdős, around 1949).
One key step is to prove that, with $\vartheta(x) = \sum_{p\leq x} \log p$,
$$(1) \qquad\qquad \vartheta(x) \...
- 587
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 ...
- 29k
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
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 ...
- 1,533
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
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 ...
- 2,912
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 ...
- 21.1k
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 \...
- 5,460
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 ...
- 1,019
11
votes
2
answers
1k
views
Does the Prime Number Theorem have anything to do with Erdos-Kac law or vice versa?
The prime number theorem says on average we can find $\frac n{\log n}$ primes of magnitude $n$.
Erdos-Kac law state a typical number of magnitude $n$ has $\log\log n$ primes.
Somehow the fact $e^{\...
user94040
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 -...
11
votes
1
answer
700
views
Squarefree numbers $n$ such that $432n+1$ is also squarefree
This is a second attempt (see Primes $p$ such that $432 p +1$ is prime)
Is the set of squarefree numbers $n$ such that $n(432 n+1)$ is also squarefree known to be infinite?
Fact: the number of such ...
- 123
10
votes
3
answers
1k
views
Quantitative and elementary proofs of the Prime Number Theorem
I would like to know two things: one, whether the best quantative bounds in the Prime Number Theorem are still basically those given by the Vinogradov-Korobov zero-free region? and two, whether there ...
- 1,687
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 $\...
10
votes
0
answers
739
views
Implications of divergence of $1/\zeta(s) $ at 1/2
$1/\zeta(s)=\sum_{n>0}\frac{\mu(n)}{n^s}$ where $\mu$ is the Moebius function.
This series is known to converge for $s\ge 1$ and diverge for $s\le 1/2$.
Its convergence is unknown if $1/2< s&...
- 2,106
10
votes
0
answers
512
views
Montgomery's conjecture and lower bound on certain Fourier transform.
Recently I have come across the following question, while meditating about Matt Young's answer to this question of mine, explaining the heuristic (or at least, one possible heuristic) behind ...
- 26k
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.8k
8
votes
2
answers
3k
views
Asymptotics of the least common multiple of the first natural numbers
What is $$ \limsup_{n \to \infty} \frac{\log(\mathrm{lcm}(1,2, \dots, n))}{n} \ \ ?$$
- 11.3k
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 ...
- 1,329
8
votes
3
answers
1k
views
Asymptotics for primality of sum of three consecutive primes
We consider the sequence $R_n=p_n+p_{n+1}+p_{n+2}$, where $\{p_i\}$ is the prime number sequence, with $p_0=2$, $p_1=3$, $p_2=5$, etc..
The first few values of $R_n$ are:
10, 15, 23, 31, 41, 49, 59, ...
- 93
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 ...
- 5,460
8
votes
1
answer
243
views
Main term in the number of sign changes of $\psi(x) - x$
Define $N_\Delta(T)$ to be the number of sign changes of $\psi(x) - x$ in the interval $[1, T]$.
Landau's Theorem says $N_\Delta(T)$ is $\Omega(\log T)$ [1].
But perhaps that estimate is too crude. ...
- 83
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=...
- 15.4k
7
votes
3
answers
1k
views
a question for the prime counting function
A famous inequality that has been proved by J.B. Rosser and L. Schoenfeld says that
$\frac{n}{\ln n-1/2}$ < $\pi(n)$<$\frac{n}{\ln n-3/2} , n\ge 67$.
Using this inequality we can prove ...
- 3,866
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\...
user6671
7
votes
2
answers
2k
views
Legendre's Constant
In a couple of web pages, I see that Legendre's constant is defined to be $\lim_{n \to \infty} (\pi(n) - (n/\log(n)))$ (for example, here and here).
Actually the first uses $\lim_{n \to \infty} (\log(...
- 595
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
7
votes
2
answers
426
views
Divisor sums over values of binary forms of primes
Let $\tau$ be the divisor function, that is
$$
\tau(n)=\sharp\{d \in \mathbb{N}, d|n\}.
$$
I was wondering if anyone has ever proved an asymptotic estimate
for the sum
$$S(x):=\sum_{p,q\leq x}\tau(p^...
- 3,062
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 ...
- 5,460
6
votes
3
answers
2k
views
Logarithmic integral, $π(x)$ and $x/(\ln x)$
The function $\text{Li}$ (logarithmic integral) is defined for $x>0$
by
$$
\text{Li}(x)=\int_2^{x}\frac{dt}{\ln t}.
$$
The prime number theorem, proven by Hadamard and de la Vallée-Poussin in 1896 ...
- 16.2k
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 ...
- 41.8k
6
votes
2
answers
1k
views
The shortest interval for which the prime number theorem holds [closed]
It is well known that the prime number theorem on the form
\begin{align*}
\pi(x+y) - \pi(x) \sim \frac{y}{\log (x+y)}
\end{align*}
breaks down for short enough intervals, e.g. taking $y=(\log x)^\...
- 965
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
1
answer
1k
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 ...
- 53
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 ...
- 233
5
votes
1
answer
736
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 $\...
user344548
5
votes
1
answer
224
views
Log weight removal in general (weaker) prime number theorem
Let $a_n$ be a sequence of non-negative numbers.
Assume that $$\limsup _{X\to \infty}\frac{\sum_{p\leq X} a_p\log p}{X}\leq 1.$$
Can we prove that $$\limsup _{X\to \infty}\frac{\sum_{p\leq X} a_p}{X/\...
- 131
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,460
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)...
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 ...
- 17.9k
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 ...
- 654
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
4
votes
0
answers
672
views
Euclides' sieve
This is probably a well-known problem. Given a set or multiset of natural numbers let us construct its "Euclides" closure: on each step we take all possible products $P_i$ of the elements in the set, ...
- 5,043
4
votes
0
answers
318
views
Prime powers between $x$ and $x+x^\theta$
By the result of Baker, Harman, Pintz (http://www.cs.umd.edu/~gasarch/BLOGPAPERS/BakerHarmanPintz.pdf), for any sufficiently large $x$ the interval $[x-x^{21/40},x]$ contains a prime number. This ...
- 41.8k
4
votes
0
answers
412
views
Effective prime number theorem
The prime number theorem implies that for every $ϵ>0$, there is $n_\epsilon$ such that for all $n≥n_\epsilon$ the number of primes in $[n,cn]$ is at least $\frac{(c−1−\epsilon)n}{\log n}$ and at ...
- 13.9k
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)$ ?
3
votes
1
answer
860
views
Lower bounds on the error term of the prime number theorem
Are there any lower bounds on the error term for the prime number theorem, or in other words, is there a nontrivial $f$ s.t.
$$f(x)\ll |\psi(x) - x|$$
where $\psi$ is the Chebyshev function.
- 1,890
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