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

69
votes
4answers
25k views

Philosophy behind Yitang Zhang's work on the Twin Primes Conjecture

Yitang Zhang recently published a new attack on the Twin Primes Conjecture. Quoting Andre Granville : “The big experts in the field had already tried to make this approach work,” Granville ...
61
votes
6answers
6k views

Does Zhang's theorem generalize to $3$ or more primes in an interval of fixed length?

Let $p_n$ be the $n$-th prime number, as usual: $p_1 = 2$, $p_2 = 3$, $p_3 = 5$, $p_4 = 7$, etc. For $k=1,2,3,\ldots$, define $$ g_k = \liminf_{n \rightarrow \infty} (p_{n+k} - p_n). $$ Thus the twin ...
57
votes
5answers
3k views

Gaussian prime spirals

Imagine a particle in the complex plane, starting at $c_0$, a Gaussian integer, moving initially $\pm$ in the horizontal or vertical directions. When it hits a Gaussian prime, it turns left ...
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 ...
40
votes
3answers
5k views

Is a “non-analytic” proof of Dirichlet's theorem on primes known or possible?

It is well-known that one can prove certain special cases of Dirichlet's theorem by exhibiting an integer polynomial $p(x)$ with the properties that the prime divisors of $\{ p(n) | n \in \mathbb{Z} ...
39
votes
1answer
1k views

Exploding primes

Suppose every prime $n$ could "explode" once. An explosion results in $\lfloor \alpha \ln n \rfloor$ particles being uniformly distributed over the integers in a range $n \pm \lfloor \beta \ln n ...
39
votes
4answers
2k views

Strange (or stupid) arithmetic derivation

Let us consider the following operation on positive integers: $$n=\prod_{i=1}^{k}p_i^{\alpha_i} \qquad f(n):= \prod_{i=1}^{k}\alpha_ip_i^{\alpha_i-1}$$ (Is it true that if we apply this operation to ...
34
votes
1answer
7k views

Is the Green-Tao theorem true for primes within a given arithmetic progression?

Ben Green and Terrence Tao proved that there are arbitrary length arithmetic progressions among the primes. Now, consider an arithmetic progression with starting term $a$ and common difference $d$. ...
33
votes
5answers
2k views

Happy New Prime Year!

It happens that next year 2011 is prime, while outgoing 2010 is highly composite in the sense that the number of its distinct prime factors is 4, maximal possible for a year $< 2310$. Let me ...
32
votes
4answers
7k views

How hard is it to compute the number of prime factors of a given integer?

I asked a related question on this mathoverflow thread. That question was promptly answered. This is a natural followup question to that one, which I decided to repost since that question is answered. ...
31
votes
4answers
2k views

Are There Primes of Every Hamming Weight?

That is, for every integer $n \in \mathbb{Z}_{>0}$ does there exist a prime which is the sum of $n$ distinct powers of $2$? In this case, the Hamming weight of a number is the number of $1$s in ...
30
votes
2answers
1k views

A question on maps from $\mathbb{Z}/p\mathbb{Z}$ to itself

Let $p\geq 3$ be a prime number, and let $u:\mathbb{Z}/p\mathbb{Z}\to \mathbb{Z}/p\mathbb{Z}$ be a map such that, for all $l\in \mathbb{Z}/p\mathbb{Z}$,$l\neq 0$, the map $k\mapsto u(k+l)-u(k)$ is a ...
30
votes
1answer
3k views

Integers not represented by $ 2 x^2 + x y + 3 y^2 + z^3 - z $

EDIT, 9 March 2014: when I asked this in 2010, I did not have the courage of my convictions, and so did not ask for an if and only if proof, as Kevin Buzzard quite properly pointed out. Such problems ...
29
votes
2answers
2k views

Generalization of Tamarkin's ARO 1993, final round, problem 10/8: still a conjecture?

This is from the category "problems I cannot believe that are still open". But then again, I don't know whether it is still open; it seems to have escaped the attention of most number theorists and ...
28
votes
3answers
2k views

Why Mertens could not prove the prime number theorem?

We know that $$ \sum_{n \le x}\frac{1}{n\ln n} = \ln\ln x + c_1 + O(1/x) $$ where $c_1$ is a constant. Again Mertens' theorem says that the primes $p$ satisfy $$ \sum_{p \le x}\frac{1}{p} = \ln\ln ...
28
votes
3answers
2k views

What is the current status of Agrawal's conjecture?

In their famous 'Primes is in P' paper Agrawal, Kayal and Saxena stated the following conjecture: If for coprime integers $n$ and $r$ the equality $(X-1)^n = X^n - 1$ holds in ...
27
votes
1answer
858 views

Prime Number Races in 2 Dimensions

Is the mapping $$f: \ \mathbb{N} \rightarrow \mathbb{Z}[i], \ \ \ n \ \mapsto \sum_{2 < p \leq n \ {\rm prime}} e^{\frac{p-1}{4} \pi i}$$ surjective? In 1999, when I was an undergraduate student, ...
26
votes
1answer
2k views

Are the primes normally distributed? Or is this the Riemann hypothesis?

Forgive my very naive question. I know next to nothing about number theory, but I'm curious about the state of the art on the distribution of primes. Let $\mathrm{Li}(x)$ be the offset logarithmic ...
25
votes
2answers
2k views

Is Li(x) the best possible approximation to the prime-counting function?

The Prime Number Theorem says that $\lim_{n \to \infty} \frac{\pi(n)}{\mathrm{Li}(n)} = 1$, where $\mathrm{Li}(x)$ is the Logarithm integral function $\mathrm{Li}(x) = \int_2^x \frac{1}{\log(x)}dx$. ...
24
votes
4answers
3k views

What is exceptional about the prime numbers 2 and 3?

Admittedly this question is vague. But I hope to convey my point. Feel free to downvote this. Permit me to define prime number the following way: A number $n>1$ is a prime if all integers $d$ ...
23
votes
3answers
3k views

Bringing Number and Graph Theory Together: A Conjecture on Prime Numbers

Some MOers have been skeptic whether something like natural number graphs can be defined coherently such that every finite graph is isomorphic to such a graph. (See my previous questions [1], [2], ...
23
votes
3answers
1k views

What does the numerically verified part of the Riemann Hypothesis tell about prime numbers?

I'm curious about the following question: As of 2005(?) the Riemann hypothesis is verified for the first 10 trillion zeroes, they are all on the critical line. Does this verification gives us any ...
22
votes
3answers
1k views

Composite pairs of the form n!-1 and n!+1

It's well known that the numbers of the form $n!\pm1$ are not always prime. Indeed, Wilson's Theorem guarantees that $(p-2)!-1$ and $(p-1)!+1$ are composite for every prime number $p > 5$. Is ...
21
votes
2answers
2k views

Why do primes dislike dividing the sum of all the preceding primes?

I was investigating primes with the property that the sum of the first $n$ primes is divisible by $p_n$. It turns out that these primes are extremely extremely rare. For primes less than $10^9$, I ...
21
votes
4answers
2k views

Why so difficult to prove infinitely many restricted primes?

I wondered whether there were an infinite number of palindromic primes written in binary (11, 101, 111, 10001, 11111, 1001001, 1101011, ...) and quickly discovered that it is unknown (OEIS A117697). ...
21
votes
2answers
1k views

What is the crucial difference the Maynard/Tao approach and Goldston-Pintz-Yildirim that extends to prime k-tuples with $k>2$

Suppose $m$ is a positive integer. A quantity of interest is $$ H_m = \liminf_{n\to\infty} \left(p_{n+m} - p_n \right) $$ The twin prime conjecture, is, of course $H_1 = 2$, the the prime k-tuples ...
19
votes
8answers
8k views

What are the connections between pi and prime numbers?

I watched a video that said the probability for Gaussian integers to be relatively prime is an expression in $\pi$, and I also know about $\zeta(2) = \pi^2/6$ but I am wondering what are more ...
19
votes
4answers
4k views

How does Yitang Zhang use Cauchy's inequality and Theorem 2 to obtain the error term coming from the $S_2$ sum

I have been reading Yitang Zhang's paper now for one and a half weeks and also volunteered to give a popular talk on the paper next week at Stockholm University. Today I found a detail in the proof ...
19
votes
6answers
3k views

explicit formula for Riemann zeros counting function

I've often seen it stated (in vague terms) that there's a Fourier duality between the set of prime numbers and the set of nontrivial Riemann zeta zeros. Because there are various explicit formulae ...
19
votes
1answer
1k views

Nontrivial circular arguments?

There is a famous circular argument for the Prime Number Theorem (PNT). It turns out that there exists an infinite sequence of elementary-to-prove Chebyshev-type estimates that taken together imply ...
19
votes
1answer
493 views

Avoiding multiples of $p$

Let $p$ be a prime number and $P=\{1,2,...,p-1\}$ In how many ways we can sum all the elements of $P$ in such a way that we will reach a multiple of $p$ only when we sum the last summand? For ...
18
votes
6answers
2k views

Philosophical Question related to Largest Known Primes

The other day while discussing math, and primes specifically, the following question came to mind, and I figured I'd ask it here to see what people's opinions on it might be. Main Question: ...
18
votes
2answers
687 views

Why are this operator's primes the Sophie Germain primes?

I was seeking a binary operator on natural numbers that is intermediate between the sum and the product, and explored this natural candidate: $$x \star y = \lceil (x y + x + y)/2 \rceil \;.$$ Then ...
18
votes
4answers
1k views

Generalizing Euclid's proof of the infinity of primes

Is the following problem still open? Let $S$ be a non-empty set of prime numbers such that whenever $p,q\in S$, all the prime factors of $pq+1$ are also elements of $S$. Is $S$ infinite?
18
votes
3answers
851 views

Finite sums of prime numbers $\geq x$

Let $S_x$ be the set of finite sums of prime numbers $\geq x$. In other words, let $S_x$ be the submonoid of $(\mathbf{Z}_{\geq 0},+)$ generated by the set $\mathcal{P}_{\geq x}$ of prime numbers ...
18
votes
3answers
765 views

Can Gauss sums derandomize any heuristic arguments?

I've always been fascinated by the fact that the classical Gauss sum has absolute value $\sqrt p$, which is exactly what we would expect if we were to interpret the Gauss sum as a random walk. In ...
18
votes
3answers
2k views

Constructing prime numbers

The classical proof of the infiniteness of prime numbers is to take the $k$ first prime numbers $p_1,\ldots,p_k$, then to form $$n_k:=1+p_1\cdots p_k.$$ Then $n_k$ has a prime factor, which is none of ...
18
votes
1answer
1k views

The Quaternion Moat Problem

"One cannot walk to infinity on the real line if one uses steps of bounded length and steps on the prime numbers. This is simply a restatement of the classic result that there are arbitrarily large ...
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 ...
17
votes
7answers
2k views

Asymptotic density of k-almost primes

Let $\pi_k(x)=|\{n\le x:n=p_1p_2\cdots p_k\}|$ be the counting function for the k-almost primes, generalizing $\pi(x)=\pi_1(x)$. A result of Landau is $$\pi_k(x)\sim\frac{x(\log\log ...
17
votes
3answers
1k views

A binomial sum is divisible by p^2

This is a question I have since longer time, but I have absolutely no idea how to proceed on it. Let $p>3$ be a prime. Prove that ...
17
votes
3answers
668 views

Are sets with similar asymptotic behavior as the primes necessarily finite additive bases?

The set of primes $\mathbb{P}$ has many interesting properties in additive number theory and some of the most famous open problems about $\mathbb{P}$ are the well-known Goldbach's strong and weak ...
17
votes
2answers
703 views

Floors of rationals to powers: Infinite number of primes?

Let $r=a/b$ be a rational number in lowest terms, larger than $1$, and not an integer (so $b > 1$). Q. Does the sequence $$ \lfloor r \rfloor, \lfloor r^2 \rfloor, \lfloor r^3 \rfloor, ...
17
votes
3answers
1k views

Primes of the form $x^2+ny^2+mz^2$ and congruences.

This is a sequel of this question where I asked for which positive integer $n$ the set of primes of the former $x^2+ny^2$ was defined by congruences (a set of primes $P$ is defined by congruences if ...
17
votes
2answers
1k views

Chen's Theorem with congruence conditions.

I would like to revisit a closed question of asterios in a more MO kind of way, because it cuts quite close to a related question about sieving that might be of general interest. The original ...
16
votes
3answers
773 views

For consecutive primes $a\lt b\lt c$, prove that $a+b\ge c$.

For consecutive primes $a\lt b\lt c$, prove that $a+b\ge c$. I cannot find a counter-example to this. Do we know if this inequality is true? Alternatively, is this some documented problem (solved or ...
16
votes
6answers
2k views

Question on consecutive integers with similar prime factorizations

Suppose that $n=\prod_{i=1}^{k} p_i^{e_i}$ and $m=\prod_{i=1}^{l} q_i^{f_i}$ are prime factorizations of two positive integers $n$ and $m$, with the primes permuted so that $e_1 \le e_2 \cdots \le ...
16
votes
6answers
6k views

Examples of prime numbers in nature [closed]

Finding primes in signals is seen as a sign of some kind of intelligence - see e.g. the role of primes in the search for extraterrestrial life (see e.g. here). This is because there are relatively few ...
16
votes
1answer
1k views

Are all primes in a PAP-3?

Van der Corput [1] proved that there are infinitely many arithmetic progressions of primes of length 3 (PAP-3). (Green & Tao [2] famously extended this theorem to length $k$.) But taking this in ...
16
votes
1answer
4k views

Tightening Zhang's bound

Inspired by a blogpost by Scott Morrison and ongoing discussion there I decided to create this community wiki to track progress on the original bound of Yitan Zhang. The original bound was ...