Skip to main content

All Questions

Filter by
Sorted by
Tagged with
4 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 ...
rr_math's user avatar
  • 43
3 votes
0 answers
191 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}...
H A Helfgott's user avatar
  • 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_{...
Wayne's user avatar
  • 13
1 vote
0 answers
156 views

Nontrivial nonrandom properties of prime numbers

What are some nontrivial nonrandom properties of prime numbers. Consider the simple model where each number is prime with probability 1/log(n) by Montgomery and extensions of it. Once you add some ...
ericf's user avatar
  • 680
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 ...
Nautilus's user avatar
  • 727
1 vote
0 answers
68 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
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 $\...
user avatar
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, ...
John McManus's user avatar
2 votes
1 answer
152 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
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
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 ...
Roland Bacher's user avatar
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 ...
Daniel Loughran's user avatar
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 ...
Riemann's user avatar
  • 654
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 ...
Bruno's user avatar
  • 456
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 $\...
Tobias Schnieders's user avatar
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 $\...
Pierluigi's user avatar
  • 109
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)=...
ishandutta2007's user avatar
0 votes
0 answers
91 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
195 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,776
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 ...
Johnny Cage's user avatar
  • 1,561
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 ...
Nilotpal Kanti Sinha's user avatar
2 votes
1 answer
460 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
  • 781
1 vote
0 answers
186 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
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,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 ...
Isaac Brenig's user avatar
2 votes
0 answers
311 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
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{\...
user627482's user avatar
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 ...
Juu's user avatar
  • 129
3 votes
1 answer
333 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
  • 4,074
2 votes
1 answer
299 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
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 ...
VS.'s user avatar
  • 1,826
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 ...
Taras Banakh's user avatar
  • 41.8k
-3 votes
1 answer
237 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
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 ...
math is fun's user avatar
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 ...
math is fun's user avatar
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=...
David Corwin's user avatar
  • 15.4k
-1 votes
1 answer
144 views

Sufficient conditions on $ a_i,b_i$ for $a_1\phi(n)+b_1, \cdots, a_k\phi(n)+b_k$ to be simultaneously prime infinitely often?

I am really interested in sufficient conditions on $a_i, b_i$ guaranteeing that the linear forms $a_1\phi(n)+b_1,\dots, a_k\phi(n)+b_k$ become simultaneously prime for infinitely many positive ...
zeraoulia rafik's user avatar
0 votes
1 answer
248 views

What can this $\int_{0}^{t} (\pi(x)-Li(x)) dx$ tell us about primes distribution?

Many papers I have read which are related to primes distribution only it discussed sign and refinement Bounds of $\pi(x)-Li (x)$ with $\pi(x)$ is a prime counting function and $Li (x)$ is the ...
zeraoulia rafik's user avatar
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 ...
Nilotpal Kanti Sinha's user avatar
0 votes
1 answer
228 views

Is this theorem on the abundance of prime patterns/k-tuples known?

I am looking for references regarding the following statement. For any two natural numbers x and y there must be a prime k-tuple (a, b, ...) corresponding to x consecutive primes (n+a, n+b, ...) for ...
Thomas Traill's user avatar
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$. ...
Turbo's user avatar
  • 13.9k
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 ...
Kristiyan Vasilev's user avatar
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$.
Kristiyan Vasilev's user avatar
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)$ ?
Kristiyan Vasilev's user avatar
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)...
The Number Theorist's user avatar
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\...
user avatar
0 votes
0 answers
114 views

The best error term for the second moment

Let $r_2(n)$ be the number of representations of a positive integer $n$ as a sum of two prime squares, i.e. $n=p^2+q^2$. Consider $S_1(x)= \sum_{n \le x} r_2(n)$ and $S_2(x) = \sum_{n \le x}r_2^2(n)$. ...
RunForrest's user avatar
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 ...
Q_p's user avatar
  • 1,019
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 ...
user21820's user avatar
  • 2,912
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 ...
Taras Banakh's user avatar
  • 41.8k