Questions where prime numbers play a key-role, such as: questions on the distribution of prime numbers (twin primes, gaps between primes, Hardy–Littlewood conjectures, etc); questions on prime numbers with special properties (Wieferich prime, Wolstenholme prime, etc.). This tag is often used as a ...

learn more… | top users | synonyms

53
votes
0answers
3k views

The topology of Arithmetic Progressions of primes

The primary motivation for this question is the following: I would like to extract some topological statistics which capture how arithmetic progressions of prime numbers "fit together" in a manner ...
16
votes
0answers
468 views

Does $\binom{2n}{n} \equiv 2 \pmod p$ ever hold?

Well, the title does not tell the whole story; the complete question is: Are there any primes of the form $p=2n(n-1)+1$, with integer $n\ge 1$, such that $$ \binom{2n}{n} \equiv 2\pmod p ? $$ ...
13
votes
0answers
871 views

Small primes attract large primes

I posted a version of this to stackexchange and got 12 up-votes and no answers in somewhat more than a day. Someone in a comment construed it as asking for a lot of novel research including figuring ...
12
votes
0answers
314 views

Word complexity of primes mod 4

For an infinite binary word $w$, the word complexity $f_w(n)$ is defined as the number of different subwords of length $n$. The asymptotic behavior of this function is an important parameter of the ...
11
votes
0answers
428 views

Why are solutions to $\sqrt[k]{x_1^k+x_2^k+x_3^k+x_4^k}$ for $k=2,3$ curiously smooth?

Given an integer solution $s_m$ to the system, $$x_1^2+x_2^2+\dots+x_n^2 = y^2$$ $$x_1^3+x_2^3+\dots+x_n^3 = z^3$$ and define the function, $$F(s_m) = x_1+x_2+\dots+x_n$$ For $n\geq3$, using an ...
11
votes
0answers
223 views

Why $\gcd \{ {\rm ord}_p(q)\colon q\mid p-1 \}$ likes to be large?

For a prime $p$, let $F_p$ denote the greatest common divisor of the orders modulo $p$ of all prime divisors of $p-1$: $$ F_p = \gcd \{ {\rm ord}_p(q)\colon q\mid p-1 \}; $$ thus, for instance, ...
11
votes
0answers
655 views

Are the twin primes the only positive double zeros of this real function?

Agno's answer was extremely helpful. For $x \in \mathbb{R}, x \ge 1$ define $$ f(x) = \sin\frac{\pi(\Gamma(x)+1)}{\lfloor x \rfloor}$$ By Wilson's theorem the positive integer zeros of $f(x)$ are ...
9
votes
0answers
119 views

The multiplicative group generated by shifted primes

I am asking for references about the following problem. In particular, it is still open? If not, what is the state of the art result? Problem 1. Let $\Gamma$ be the multiplicative subgroup of ...
9
votes
0answers
391 views

Sieve bound for prime $k$-tuples

Let $d_1<d_2<\dots<d_k$ be integers. Then the number of integers $n\leq x$, such that $n+d_1, n+d_2, \ldots, n+d_k$ are simultaneously prime, is bounded above by $$ \mathfrak{S}(d_1, \ldots, ...
8
votes
0answers
129 views

Does the given operation on pairs of primes always repeat?

Let $p$ and $q$ be two distinct primes. The set $$A(p,q) =\{m+n : mp+nq=1 \textrm{ and } m,n \in \mathbb{Z}\}$$ is an arithmetic progression. Its step size $p-q$ is coprime to a fixed $m+n$ because ...
8
votes
0answers
737 views

Would the following conjectures imply $\lim\inf_{n\to\infty}p_{n+k}-p_{n}=O(k\log k)$?

Assume Goldbach's conjecture. Then for every $n\ge 2$ there exists at least one non-negative integer $r\le n-2$ such that both $n+r$ and $n-r$ are primes. Let's write $r_{0}(n):=\inf\{r\le n-2, ...
8
votes
0answers
551 views

Two different ways to count Mersenne Primes

Hi there, the motivation for this question is to better understand the heuristics of Mersenne primes, and I was motivated by the recent questions (Mersenne quasi-primes) and (Primes in generalized ...
7
votes
0answers
234 views

On the ratio of Gilbreath sequences

Definitions: let $n \in \mathbb{N}_{>0} \cup \{ \infty \}$ and let $E_n$ be the set of sequences $(d_i)_{i=1}^n$ such that $d_1=1$, $d_i$ is an even integer (for $i > 1$) and $0<d_i \le i$. ...
7
votes
0answers
201 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 ...
7
votes
0answers
317 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 ...
7
votes
0answers
637 views

“probabilistic” density of primes?

A certain set $\cal P$ of primes is defined by two assumedly independent conditions: The first condition on a prime $p$ can be characterized in terms of the type of splitting of $p$ in certain Galois ...
6
votes
0answers
65 views

Prime divisors of the norm of the first coefficient of an elliptic newform at width-1 cusps.

Let $E/\mathbb{Q}$ be an elliptic curve of conductor $N$ and let $f$ be its newform. Suppose $p \geq 5$ is a prime such that $p^2 \mid N$. We assume $f$ is $p$-minimal, which is equivalent to that the ...
6
votes
0answers
249 views

Can integers be distorted to make primes more regular?

Given a set $P$ of real numbers $\ge 1$, define the gap among different products in $P$ as $$g(P) = \inf \big\{\prod_{i=1}^n p_i^{a_i} - \prod_{i=1}^n p_i^{b_i} \mid p_i\in P;\,\, p_i\ne p_j \,\text{ ...
6
votes
0answers
164 views

Is ${\rm lcm}\{{\rm ord}_p(q)\colon q\mid p-1,\ q>2\}>\sqrt p\ \,$?

The following question is "ideologically related" to the one I recently asked here. For a prime $p$, let $M_p$ denotes the least common multiple of the orders modulo $p$ of all odd prime divisors of ...
6
votes
0answers
214 views

A conjecture of Erdos on consecutive differences of primes

Let $d_k = p_{k + 1} - p_k$ be the difference between consecutive primes and define \begin{equation} e_k = \left\{\begin{array}{c l} 1 &, d_{k + 1} > d_k \\ 0 &, \text{otherwise} ...
6
votes
0answers
265 views

On the sum of consecutive primes and product of first and last

Lets consider the sequence of consecutive prime numbers $p_1=2 , p_2=3 ,p_4=5 , \cdots$ . $(p_n,p_{j})$ is to be called good prime pair if $$\sum_{i =n }^{j}p_i= p_n p_{j}$$ Meaning the sum of set of ...
6
votes
0answers
320 views

Twin Primes that are Sophie Germain Primes

Suppose $p$ is a prime such that $p + 2$ is also prime, and nothing else is known about $p$. Is there any reason to think that this affects the probability that $p$ is also a Sophie Germain prime? ...
6
votes
0answers
239 views

Generalizing prime numbers to product-indecomposable objects in toposes

Any object $A$ in any topos decomposes as $A\times1$ and $1\times A$, and in $FinSet$ objects with no other product decompositions are "prime numbers". Is there any extension of the theory of ...
6
votes
0answers
630 views

Would the following conjectures imply Cramer's conjecture?

Assume Goldbach's conjecture. Then for every $n\ge 2$ there exists at least one non-negative integer $r\le n-2$ such that both $n+r$ and $n-r$ are primes. Let's write $r_{0}(n):=\inf\{r\le n-2, ...
6
votes
0answers
480 views

Any published references for this $O(n)$ time, $O(n^\epsilon)$ space identity for the count of primes?

I would like to know if this identity (or trivial equivalents) for $\pi(n)$, the count of primes, is currently published anywhere. $D_{0,a}(n) = 1$ $D_{1,a}(n) = \lfloor n\rfloor-a-1 \ \ \ \ \ \ \ \ ...
6
votes
0answers
355 views

Primes of the form $x^2+ny^2$ such that when you swap x and y you get another prime

Hello, Im looking at primes of the form $x^2+ny^2$ for $n>1$ where we can swap $x$ and $y$ and get another prime, I have found many such pairs for many values of n, and i wanted to know if there ...
5
votes
0answers
269 views

$x^2+1$ attaining almost prime values

Iwaniec, using the linear sieve, proved that $n^2+1$ can be a product of at most two primes infinitely often and furthermore a lower bound of the correct order of magnitude for the number of such ...
5
votes
0answers
252 views

Primes for which 2 is a primitive root

I am writing a paper in which I keep referring to primes p for which 2 is a primitive root mod p and so I want to give a name for these primes. Is there a name for these primes in the literature ...
5
votes
0answers
263 views

Should I expect to see numbers this smooth?

I have a sequence $N_k$ of numbers whose growth I wish to determine, or at least approximate nicely. When I look at the ratios of consecutive members, I find some interesting simplifications ...
5
votes
0answers
253 views

$n\varphi(n)\equiv 2\pmod{\sigma(n)}$ as a primality test

It is known from Subbarao, "On two congruences for primality" that $n>22$ is a prime iff $$n\sigma(n)\equiv 2\pmod{\varphi(n)},$$ where $\varphi(n)$ is Euler's function and $\sigma(n)$ is sum of ...
5
votes
0answers
311 views

How many ways can a number be Fortunate?

An integer $m$ is Fortunate if it can be written as $q-P$, where $P$ is a primorial and $q$ is the smallest prime greater than $P+1$. It is conjectured that Fortunate numbers are always prime. It ...
5
votes
0answers
246 views

Picking out an odd subset

I want to know whether the following property holds: There exists a constant C such that for any big positive integer N and any nonempty subset M of {1,...,N} there exists a positive integer ...
5
votes
0answers
524 views

Are there an infinite number of prime Euclid numbers?

A number defined as the product of first $n$ prime numbers $+1$ is called $n$th Euclid number. Are there any survey on the progress for answering the following question: are there an infinite number ...
4
votes
0answers
78 views

Visibility in a prime orchard

This suggests a variant on Polya's orchard problem. That problem asks1 for which radius $\epsilon$ of trees at each lattice point within a distance $R$ of the origin block all lines of sight to the ...
4
votes
0answers
134 views

Are there infinitely many zeros of $\chi(s)+ \dfrac{2^{s}- 2^{2s-1}}{2^{s}-1}$ on the critical line?

Take $\chi(s)= 2^s\,\pi^{s-1}\,\sin\left(\frac{\pi\,s}{2}\right)\,\Gamma(1-s)$, so that $\zeta(s)=\chi(s)\,\zeta(1-s)$. The zeros of $\chi(s)=-1$ and the non-trivial zeros $\rho$ of $\zeta(s)$, seem ...
4
votes
0answers
256 views

Are there always at least *five* divisions?

@JosephO'Rourke asked a question about a Collatz like function related to primes: $f(n) = \begin{cases} n^2 & \text{if} \;n \;\text{is prime} \\ \lfloor n/2 \rfloor & \text{if} \;n ...
4
votes
0answers
220 views

Analog of Euler's factoring technique

Is there an analog of Euler's Two Squares factoring theorem over polynomial rings $\Bbb Z[x]$ by considering a version for non-negative polynomials? Euler's two squares factoring states that numbers ...
4
votes
0answers
315 views

Is there a hidden symmetry in the prime numbers distribution?

Under Goldbach's conjecture, let's consider once again the map $r_0\colon n\mapsto r_{0}(n)$ such that $r_{0}(n)$ is the smallest non negative integer $r$ such that both $n-r$ and $n+r$ are prime. ...
4
votes
0answers
137 views

The divisors of $p-1$ and high-degree residues modulo $p$

Here is a somewhat more explicit version of a question that I asked a while ago. Suppose that $p$ is a prime of the form $p=2n(n+1)+1$, with a positive integer $n$. Can every odd prime divisor of ...
4
votes
0answers
170 views

Can the following quantitative version of Chen's theorem be obtained?

The theorem of the Chinese mathematician Chen Jingrun is currently one of the best results with respect to the binary Goldbach problem. It asserts that every even integer $n$ is in the sumset $P + ...
4
votes
0answers
319 views

About sign changes of Li(x)-π(x)

Given a constant $C$, which are the best known upper bounds for the number of sign changes of the function $$ f: \mathbb{N} \rightarrow \mathbb{R}, \ \ x \mapsto {\rm Li}(x)-\pi(x) $$ in the range ...
4
votes
0answers
93 views

On a weighted sum in a lemma for sieve methods

I'm reading James Maynard's paper "Small gaps between primes". Lemma 6.1 (p.14) in this paper confused me. This lemma was taken from Goldston-Graham-Pintz-Yildirim's paper "Small gaps between ...
4
votes
0answers
422 views

AKS Algorithm Pseudoprimes

The AKS algorithm is based on the following fully deterministic primality check: Let input $n>1$ and $a \in \mathbb{N}$ such that $(a,n)=1$. Then $n$ is prime if and only if $$\tag{1}(x+a)^n ...
4
votes
0answers
324 views

Estimate on radical of $2^n \pm 1$

Not sure if this belongs to MO or not. Are there any lower bound on radical of $2^n \pm 1$ (Recall that radical of integer $rad(k)$ is a product of primes which divide integer $k$)? As an example If ...
4
votes
0answers
149 views

smallest k such that highest prime factor of m(m+1)…(m+k-1) is > n if m > n.

I am fascinated by this entry OEIS A213253 which lists the smallest $k$ such that highest prime factor of $m(m+1)\dots(m+k-1)$ is $> n$ if $m > n$. The article has references to the algorithm ...
4
votes
0answers
288 views

Generalization of Tamarkin’s ARO 1993, final round, problem 10/8: part II

Let us use the notations of my previous question about Tamarkin's problem. Let $\ell\in\left\lbrace 0,1,...,p\right\rbrace$. An element $f\in \mathbb Z^{\mathbb Z}$ is said to be ...
4
votes
0answers
364 views

Number of $k$-partitions of $n$ into odd prime parts

Browsing through OESIS I have found that if $p_p(n)$ denotes the number of partitions of $n$ into prime parts then $p_p(n) = O(e^{\frac{2 \Pi}{\sqrt{3}}\sqrt{n/\log n}})$. I am interested in the ...
3
votes
0answers
116 views

Farey Fractions Estimate Equivalent to the Prime Number Theorem?

Wikipedia's article on Farey Fractions points to an article of Jerome Franel that some averages are equivalent to the Riemann hypothesis. Let $F_n$ be the $n$-th Farey sequence, then the number of ...
3
votes
0answers
435 views

Two (strictly related) proofs by induction of inequalities

This is a question I originally asked on MSE, receiving no answer, even with a bounty (which expired) on it. Therefore I am crosslinking in order to prevent duplication of effort: see here for the ...
3
votes
0answers
177 views

Effective version of the Bombieri-Vinogradov theorem

Is there an effective version of the Bombieri-Vinogradov Theorem, in that have bounds on the implied constant been found?