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

49
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 ...
14
votes
0answers
374 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 ? $$ ...
14
votes
0answers
849 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 ...
11
votes
0answers
199 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
619 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 ...
8
votes
0answers
124 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
357 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
685 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
526 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
213 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
176 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
287 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 ...
6
votes
0answers
233 views

Does the Maynard-Tao Theorem apply to general tuples of linear forms?

In the paper http://arxiv.org/pdf/1311.5319v1.pdf the author states the following theorem, which he attributes to Maynard and Tao. For any integer $m > 2$, there exists an integer $k = k(m)$ such ...
6
votes
0answers
291 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
230 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
605 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
472 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
343 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 ...
6
votes
0answers
596 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 ...
5
votes
0answers
144 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 ...
5
votes
0answers
171 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} ...
5
votes
0answers
233 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 ...
5
votes
0answers
238 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
243 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
248 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
300 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
243 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 ...
4
votes
0answers
223 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 ...
4
votes
0answers
157 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
311 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
83 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
216 views

Relative Densities

Throughout the question, we only consider primes of the form $3k+1$. A reference for cubic reciprocity is Ireland & Rosen's A Classical Introduction to Modern Number Theory. How can I count ...
4
votes
0answers
330 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
313 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
146 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
283 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
359 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 ...
4
votes
0answers
508 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 ...
3
votes
0answers
521 views

Second Hardy-Littlewood Conjecture theme

If Second Hardy-Littlewood Conjecture is true then we can claim that $\pi(x)-\pi(y)\leq \pi(x-y)$. Thus the conjecture gives an upper bound for the number of primes between $x$ and $y$. I have found ...
3
votes
0answers
311 views

Metric on the set of subsets of the rational primes

Note: this is a revision of an earlier post. It was kindly pointed out that my initial proposed metric was in fact not a metric, so this is a revised version. I was thinking how to say that two sets ...
3
votes
0answers
90 views

Numbers expressible as sums of prime powers larger than n

Given a fixed $n \in \mathbb{N}$ larger than $1$, let $G(n)$ denote the largest number that is not expressible as a sum of prime powers larger than $n$ (the 'base' prime of the prime power need not be ...
3
votes
0answers
183 views

Logarithms of ratios of squarefree numbers

Let $M \geq 1$, and $N=2^M$. Let $a_1, \dots, a_N$ be the set of all the numbers that you get when forming all square-free products of the first $M$ primes. For example, for $M=2$ and $N=4$ you get ...
3
votes
0answers
212 views

Generating function for the characteristic function of prime numbers

What do we know about the generating function of $\chi(n)$ (A010051) $$ f(x) = \sum_{n=0}^\infty \chi(n)x^n = \sum_{p\text{ prime}} x^p $$ for $\chi(n)$ the characteristic function of the primes: ...
3
votes
0answers
143 views

Number of Inverse Pairs Modulo Prime $p$

Is there a result which gives a lower bound on the number of inverse pairs $(a, a^{-1})$ modulo prime $p$ lying in the interval $[1,t]$, where $t < p$?
3
votes
0answers
331 views

Linear independence over Q of logarithmic powers of prime numbers

I denote $p_k$ the $k^{th}$ prime number ($p_1=2$, etc...) Clearly, for any $n\in \mathbb{N}^*$, $(\log p_k)_{1\leq k\leq n}$ is linearly independent over $\mathbb{Q}$. My question concerns a ...
3
votes
0answers
496 views

Paul Erdős and Ramanujan Primes

It's easy to find Ramanujan's proof of Ramanujan primes: Ramanujan's Proof Wikipedia mentions that Paul Erdős also had a proof: Wikipedia article on Bertrand's Postulate Does anyone know the ...
3
votes
0answers
553 views

Least Prime Factor in a sequence of 2n consecutive integers

I was thinking about consecutive integers and I wondered if anyone had done work exploring whether a sequence of $2n$ consecutive integers (i.e. 101,102,103,...,100+2n) always contains at least one ...
2
votes
0answers
90 views

Siegel Walfisz Theorem for algebraic number fields

Is there a generalization of the Siegel Walfisz to algebraic number fields? This has been done for the prime number theorem in the prime ideal theorem.
2
votes
0answers
126 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?
2
votes
0answers
183 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 ...