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

41
votes
0answers
2k 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 ...
18
votes
0answers
1k views

Permutations of $(Z/pZ)^*$

Let $p$ be a prime integer, and let $(\mathbb Z/p\mathbb Z)^*$ be the set of non-zero elements of $\mathbb Z/p \mathbb Z$. Denote by $S((\mathbb Z/p \mathbb Z)^*)$ the group of permutations of ...
14
votes
0answers
824 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 ...
9
votes
0answers
445 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
112 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
316 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
530 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, ...
7
votes
0answers
243 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
476 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 ...
6
votes
0answers
241 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
225 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
565 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
452 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
334 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
574 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
139 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 ...
5
votes
0answers
207 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
226 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
234 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
292 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
241 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
284 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
72 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
205 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
298 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
303 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
144 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
307 views

Recursivity of the primes

As is well-known, with the finite set of the first $n$ primes $p_1,\dots ,p_n$ one can find all primes exactly (i.e. without false positives) with the Eratosthenes Sieve in the interval ...
4
votes
0answers
282 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
348 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
499 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
135 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 + ...
3
votes
0answers
173 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
164 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
138 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
297 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
465 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
541 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
116 views

Analytic varieties for the primes and the twin primes

I am wondering what real and complex analysis say about the primes and twin primes. According to Wikipedia analytic variety is defined locally as the set of common zeros of finitely many analytic ...
2
votes
0answers
253 views

A question concerning the strange arithmetic derivation

This question is related to Strange (or stupid) arithmetic derivation. The original question whether an unbounded sequence of iterates exists is still unanswered. $$n=\prod_{i=1}^{k}p_i^{\alpha_i} ...
2
votes
0answers
177 views

Efficient ways to count primes satisfying Zhang's theorem

The theorem of Yitang Zhang states that there exist a finite $k \in \mathbb{N}$ such that there exist infinitely pairs of primes $(p,q)$ such that $|p - q| \leq k$. The statement that $k$ can be taken ...
2
votes
0answers
111 views

Steps required to recognise a $z$-smooth number

I am currently reading section 5 of Pomerance's paper The Number Field Sieve and I have a few questions about smooth numbers. A number $x\in\mathbb Z_{\ge1}$ is called $z$-smooth if every prime ...
2
votes
0answers
296 views

On the primitive prime divisors of $q^n-1$

Let $q=p^\alpha$ be a prime power. We call $r$ a primitive prime divisor of $q^n-1$ where $r\mid (q^n-1)$ but $r\nmid (q^i-1)$ for each $1\leq i\leq n-1$. The set of all primitive prime divisors of ...
2
votes
0answers
117 views

Two products over primes

For $k \in \mathbb{N}$ define $$ f(k) = \prod_{\text{p prime}}\left(1+\frac{1}{p^k(p^k+1)}\right)$$ $$ g(k) = \prod_{\text{p prime}}\left(1+\frac{1}{p^k(p^k-1)}\right)$$ By the product for zeta ...
2
votes
0answers
82 views

Symmetric dominance regions surrounding a Gaussian prime

Let $z=a + b i$ be a complex number which is a Gaussian prime, on neither the $x$- nor the $y$-axis. So $a^2+b^2$ is a prime. Construct a region $D(z)$ surrounding $z$ which is the largest ...
2
votes
0answers
212 views

Something Diophantine

Hi there, recently I came across the following divisibility question, and I wondered if much can be said about it. Let $p$ and $q$ be different primes, and suppose $p^n + q^r$ divides $p^{2m} - 1$, ...
2
votes
0answers
288 views

Algorithm for keeping a concrete version of Euclid's argument simple

(A version of this same question was posted to stackexchange.) Suppose we do what Euclid wrote about: starting with a finite set of primes, multiply them, add or subtract 1, factor the result, append ...
2
votes
0answers
323 views

Prime generating algorithm

If I want an algorithm that outputs any $n$ distinct prime numbers, is there anything faster than Atkins' Sieve $O(n/log(log(n))$ ?
2
votes
0answers
304 views

How small can intervals be and still contain a prime times a power of 2?

There was a question on MathOverflow which has since disappeared, that was on sums of at most M B-smooth numbers. It asked several questions related to how many could be found in the interval ...
2
votes
0answers
258 views

Reducing factoring prime products to factoring integer products (in average-case)

My question is about the equivalence of the security of various candidate one-way functions that can be constructed based on the hardness of factoring. (This question has been asked also in the CS ...