All Questions
130 questions
26
votes
1
answer
1k
views
What is the status on this conjecture on arithmetic progressions of primes?
The Green-Tao theorem states that for every $n$, there is an arithmetic sequence of length $n$ consisting of primes.
For primes, $p$, let $P(p)$ be the maximum length of an arithmetic progression of ...
- 1,835
26
votes
0
answers
567
views
Elliptic analogue of primes of the form $x^2 + 1$
I have a project in mind for an undergraduate to investigate next quarter -- a curiosity really, but I'm surprised I can't find it in the literature. I do not want a detailed analysis here... but ...
- 13.3k
25
votes
2
answers
4k
views
Primes of the form $x^2+ny^2$ and congruences.
The answer of following classical problem is surely known, but I can't find a reference
For which positive integer $n$ is the set $S_n$ of primes of the form $x^2+n y^2$ ($x$, $y$ integers) ...
- 26k
25
votes
1
answer
911
views
Reference request for a proof of the two-square Theorem
One can show (see below for a sketch of a proof) that every odd prime number $p$
can be written in exactly $(p+1)/2$ different ways as
$$p=a\cdot b+c\cdot d$$
with $a,b,c,d\in\mathbb N$ satisfying $\...
- 17.9k
21
votes
3
answers
3k
views
Twin Prime Conjecture Reference
I'm looking for a reference which has the first statement of the twin prime conjecture. According to wikipedia, nova, and several other quasi-reputable resources it is Euclid who first stated it, but ...
- 1,588
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
19
votes
2
answers
2k
views
Who first proved the generalization of Bertrand's postulate to (2n,3n) and (3n,4n)?
In Wikipedia's page for Bertrand's postulate, it is said that its (2n,3n) version was proved by El Bachraoui in 2006. Seems likely that it was first proved way before than that! Can anyone point to ...
- 2,992
18
votes
3
answers
6k
views
The multiplicative order of 2 modulo primes
Artin's Conjecture says that any positive integer, which is not a square, is a primitive root modulo infinitely many primes. Christopher Hooley gave in
Hooley, Christopher (1967). "On Artin's ...
- 25.5k
17
votes
2
answers
2k
views
Is every odd positive integer of the form $P_{n+m}-P_n-P_m$?
I am looking for a comment, reference, remark, or proof of three conjectures as follows:
Conjecture 1: Let $x$ be an odd positive integer. Then there exist two integers $n, m \ge 2$ so that $$x=P_{n+...
- 1,776
17
votes
0
answers
891
views
An elementary proof that, for every fixed $n \in \mathbf N^+$, there are infinitely many primes $\equiv -1 \bmod n$
This morning, I made a comment to a comment to a question of Ayman Moussa, only to point out that, among many others, there is an elementary proof of Dirichlet's theorem on the existence of infinitely ...
- 10.5k
16
votes
1
answer
4k
views
Order of magnitude of $\sum \frac{1}{\log{p}}$
Question: What is the order of magnitude of the following sum?
$$ \sum_{\substack{p<n\\\text{$p$ prime}}} \frac{1}{\log{p}} $$
Additional information: Since
$$ \sum_{\substack{p<n\\\text{...
- 3,004
14
votes
1
answer
424
views
Unpublished result of Rosser in Sieve Methods book
Erdős and Selfridge (1971) state that the following is "implied by an unpublished result of Rosser" which they claim appears in a forthcoming book on sieve methods by Halberstam and Richert.
...
- 24.8k
13
votes
1
answer
333
views
Elementary prime-generating sequences
A student of mine keeps coming again and again and telling "I've found a formula $n\mapsto f(n)$ giving all primes" or sometimes "infinitely many primes", where $f$ is a classical function (I mean ...
- 1,980
12
votes
1
answer
526
views
Equidistribution of $\{\alpha p\}$ for $p$ in an arithmetic progression
Let $\alpha$ be irrational. A famous theorem of Vinogradov says that $\{ \alpha p\}$ is equidistributed in $[0,1]$ as $p$ runs over all primes.
Let $a,q$ be natural numbers with $\gcd(a,q) = 1$. Then ...
- 21.3k
11
votes
2
answers
1k
views
Most dense subset of numbers that avoids arbitrarily long arithmetic progressions
The famous Green-Tao theorem says that there exist arbitrarily long sequences of primes in arithmetic progression.
I am wondering: How dense can a subset $S \subset \mathbb{N}$ be and still avoid
...
- 151k
11
votes
1
answer
408
views
Integers with a large prime divisor in short intervals
For an integer $n$, denote by $P^+(n)$ the largest prime divisor of $n$. Then we have the following:
There exists some $c>0$, such that for all $x$ sufficiently large the number of integers $n\in[...
11
votes
1
answer
1k
views
The Bombieri Vinogradov Theorem restricted to moduli divisible by $k$
The Bombieri-Vinogradov Theorem states that given $A>0$, there exists $B>0$ such that for $Q=\sqrt{x}\left(\log x\right)^{-B},$ we have $$\sum_{q\leq Q}\max_{y\leq x}\max_{\begin{array}{c}
a\...
- 11.4k
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
9
votes
1
answer
388
views
$π(x+y) - π(x) ≤ c·y/\ln(y)$ for some constant $c$?
(I posted this question on Math SE but it has had no answer for a year now so I would like to ask if anyone here can provide one.)
Thinking about the prime number theorem, I wondered whether it is ...
- 2,912
9
votes
2
answers
547
views
Primes between $x$ and $x+x^\theta$
Iwaniec [1] proved that
$$
\pi(x+x^\theta)-\pi(x) < \frac{(2+\varepsilon)x^\theta}{\eta(\theta)\log x},\ x>x_0(\varepsilon,\theta).
$$
with
$$
\eta(\theta)=\frac{15\theta-2}{9}.
$$
(Actually, he ...
- 9,114
9
votes
1
answer
400
views
The difference between consecutive primes in arithmetic progressions
Let $\pi(x)=\sum_{p\leq x}$ denote the prime counting function. A well known result of Baker, Harman, and Pintz on prime gaps states that for $x\geq y\geq x^{0.525}$ we have that
$$\pi(x+y)-\pi(x)\gg \...
- 11.4k
9
votes
0
answers
414
views
In which orders can the numbers of prime factors of consecutive integers be?
Let $\omega(m)$ be the number of distinct prime divisors of a positive integer $m>1$. I am interested in the relative orders in which the numbers $\omega(n+1),...,\omega(n+k)$ can occur.
Given a ...
- 2,719
8
votes
2
answers
354
views
Let $f \in \mathbb{Z}[x]$. Does $\bar{f}$ have as many roots in $\mathbb{F}_p$ as $f$ has in $\mathbb{C}$ for infinitely many primes $p$?
Let $f \in \mathbb{Z}[x]$ be a nonconstant polynomial. Consider $\bar{f} \in \mathbb{F}_p[x].$ Let $\rho_p$ be the number of distinct roots of $\bar{f}$ in $\mathbb{F}_p$, and let $\rho$ be the number ...
8
votes
2
answers
1k
views
Question about functions $f: \mathbb{Z}^+ \to \mathbb{Z}^+$ such that $x$ is prime whenever $f(x)$ is prime
Let $f: \mathbb{\mathbb{Z}^+} \to \mathbb{Z^+}$ be a function and suppose
$(\star)$ For all integers $x \geq 3$, if $f(x)$ is prime, then $x$ is prime.
A trivial example of such a function is the ...
- 707
8
votes
1
answer
811
views
Primes of the form $x^2 + y^2 + 1$
There are infinitely many primes of the form $x^2+y^2+1$, as proved by Bredihin. Motohashi improved the result by showing that there were $\gg x/\log^2 x$ such primes up to $x$. But we expect $\Theta(...
- 9,114
7
votes
1
answer
1k
views
What would be the consequences of $\displaystyle{\lim\inf_{n\to\infty}p_{n+k}-p_{n}\sim k\log k}$?
The question is in the title: what would be the number theoretic consequences if we managed to establish the conjectured asymptotic equality $\displaystyle{\lim\inf_{n\to\infty}p_{n+k}-p_{n}\sim k\log ...
- 6,984
7
votes
2
answers
1k
views
Is there a von Koch-type theorem for the generalized Riemann hypothesis?
Helge von Koch proved in 1901 that the Riemann hypothesis is equivalent to the error term in the prime number theorem having the bound
$$
\mid\pi(x)-\textrm{li}(x)\mid=O(\sqrt{x} \log x).
$$
Q1: ...
- 965
7
votes
4
answers
1k
views
Reference for the expected number of prime factors of n larger than n^alpha is -log alpha
Let $0 < \alpha < 1$ be a constant. The expected number of prime factors of a "random" integer near $n$ which are greater than $n^\alpha$ is $-\log \alpha$.
It's my understanding that (...
- 14k
7
votes
1
answer
660
views
Prove: If $P_n$ is $n$-$th$ prime number then $P_{n+m} \ge P_n+P_m$
Let $n > 1$ and $m > 0$ be two integers and $P_n$ be the $n^{th}$ prime.
Prove: $$P_{n+m} \ge P_n + P_m .$$
Can you give a hint, reference, comment, or proof?
- 1,776
7
votes
1
answer
435
views
Are primes of density 0 in $a\cdot b^n+c$?
Hooley proves in Applications of Sieves to the Theory of Numbers that there are only $o(x)$ numbers $n\le x$ such that $n\cdot2^n+1$ is a (Cullen) prime. The proof generalizes to forms $n\cdot2^{n+a}+...
- 9,114
7
votes
1
answer
382
views
$\log \log p / \log \log n$, where $p|n$, gets equidistributed in [0,1] (for almost all $n$)
According to Hardy-Ramanujan/Erdős-Kac we know that usually there are $\sim\log\log n$ prime numbers in a factorization. But if you pick up a natural number at random, and you factor it, what is the ...
- 1,384
7
votes
1
answer
652
views
Fermat-quotient of "order" 3: I found $68^{112} \equiv 1 \pmod {113^3}$ - are there bigger examples known?
(I've taken this from MSE, it seems to be more appropriate here)
I'm rereading an older text on fermat-quotients (see wikipedia) from which I have now the
Question for
$$ b^{p-1} \equiv 1 \pmod{ ...
- 5,342
7
votes
0
answers
786
views
"Forthcoming paper" of Goldston-Graham-Pintz-Yıldırım
The above-named authors of [1] and its (significantly different) published version [2] write:
In a forthcoming paper, we will show how the methods here can be extended to prove corresponding ...
- 9,114
6
votes
2
answers
1k
views
$\pi((n+1)^2)-\pi(n^2) \le \pi(n)$ for all $n \ge 370$?
There are some conjectures of the form: There always exist at least $X$ prime numbers between $A$ and $B$. Examples:
Bertrand's postulate: for every $n>1$ there is always at least one prime $p$ ...
- 1,776
6
votes
2
answers
804
views
Must Mersenne numbers be divisible by arbitrary large primes with exponent one?
Let $M_n$ denote the Mersenne numbers $M_n=2^n-1$.
As $n$ varies, must $M_n$ be divisible by arbitrary large prime $p$
with exponent one, i.e. $p \mid M_n, p^2 \nmid M_n$?
In other words, must the ...
- 25.4k
6
votes
4
answers
895
views
Mathematical induction vis-à-vis primes
One of the most used proof-techniques is mathematical induction, and one of the oldest subjects is the study of prime numbers. Thanks to Euclid, we can consider the primes as a infinite monotone ...
6
votes
1
answer
367
views
Bounds re Asymptotic Formula for the Sum of Largest Prime Factors
I have a reference request related to the result :
$\sum_{n=2}^{x} P(n)$ ~ $\frac{\pi^2}{12}\frac{x^{2}}{log(x)}$ as $x \rightarrow \infty$
where $P(n)$ is the largest prime factor of the positive ...
- 71
6
votes
2
answers
754
views
ASCII prime plots and prime-rich quadratic polynomials
This is a series of questions inspired by the MathOverflow question
Find the least prime so that p-1 has two factors greater than $m$ and $n$ posted by Aaron Sterling.
I suggested plotting primes by ...
- 13k
6
votes
1
answer
1k
views
Reference request: Dickman, On the frequency of numbers containing prime factors
I've been trying without success to find the paper
Dickman, Karl, "On the frequency of numbers containing prime factors of a certain relative magnitude." Ark Mal., Astronomi och Physik, 22A (10), ...
- 1,077
6
votes
1
answer
360
views
Friable Numbers In Short Intervals: Density Estimates?
I am hoping for explicit numerical estimates like the following sample (with made up numbers, though it might be true): for every $n \gt 10^6$ and every $b$ with $b^2 \lt n \lt b^3$, the number of ...
- 13k
6
votes
0
answers
149
views
Dickson's conjecture for Beatty sequences
A particular case of Dickson's Conjecture states that for $a_1,q_1,a_2,q_2$ with $(a_1,q_1)=(a_2,q_2)=1$, there are infinitely many $n$ for which $q_1 n + a_1$ and $q_2 n+a_2$ are both prime, provided ...
- 1,990
5
votes
2
answers
1k
views
Error term in Mertens' third theorem
Mertens' third theorem states that:
$$\prod_{\substack{
p \leq x \\
\text{p prime}
}} \left( 1 - \dfrac{1}{p} \right) \sim \dfrac{e^{-\gamma}}{\log(x)}$$
Question: what is the best functions (...
- 521
5
votes
1
answer
259
views
Central binomial coefficients deprived of $2$'s: not radicals?
In the paper, P Erdos, R Graham, I Ruzsa, E Straus, On the prime factors of $\binom{2n}n$, Math. Comp., 29:83–92, 1975, it was conjectured that the central binomials are never square-free for $n>4$....
- 43.2k
5
votes
1
answer
340
views
About an asymptotic behavior in number theory
Where can I read about the asymptotic behavior (with $N$ tending to infinity) of the sum of the fractional parts obtained from dividing $N$ by all prime numbers up to $N$ divided by the number of ...
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 $\...
user344548
5
votes
3
answers
809
views
Positive proportion of logarithmic gaps between consecutive primes
For $x, \lambda > 0$, define
$$S_\lambda(x) := \#\{p_{n+1} \leq x : p_{n+1} - p_n \geq \lambda \log x\} ,$$
where $p_n$ is the $n$th prime number. It is known [1] that an uniform version of the ...
- 113
5
votes
4
answers
819
views
Can one show combinatorially how $\operatorname{lcm}(1, \dotsc, n)$ grows?
Let us write $M(n)$ for $\operatorname{lcm}(1,\dotsc,n)$ for $n$ a positive integer. Asymptotically $M(n)$ tends toward $e^n$. This result uses analytic number theory. (Lcm is least common multiple, ...
- 13k
5
votes
1
answer
455
views
Large gaps between P2s
Gaps between consecutive primes are $O(n^{\theta+\varepsilon})$ for $\theta=0.525$ and any $\varepsilon>0.$ I was wondering if a better result is known for gaps between numbers with at most two ...
- 9,114
5
votes
1
answer
472
views
Is the following weak version of second Hardy-Littlewood conjecture already known?
Very recently I was going through my previous MSE posts and I stumbled upon some of them regarding the Second Hardy-Littlewood Conjecture which states that,
For all $x,y\ge 2$ we have, $$\pi(x)+\...
user57432
5
votes
1
answer
414
views
Primality test for $2p+1$
In 1750 Euler stated following theorem :
Let $p \equiv 3 \pmod 4$ be prime then $2p+1$ is prime iff $2p+1 \mid 2^p-1$ .
In 1775 Lagrange gave a proof of the theorem .
Recently I have formulated ...
- 2,661