**3**

votes

**1**answer

256 views

### Primes in short intervals with a preassigned frobenius

Edited after mistake in the first version.
It is known since Selberg that under the Riemann Hypothesis, given an $\epsilon>0$, there is a prime between $x$ and $x+O(x^\epsilon)$ for all $x$ in a ...

**8**

votes

**0**answers

664 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, ...

**2**

votes

**1**answer

882 views

### The Jones-Sato-Wada-Wiens polynomial for prime numbers and differential calculus?

After works of Davis, Matijasevic, Putman and Robinson between 1960 and 1970, we know that every recursively enumerable set of numbers can be represented by a polynomial.
In particular, it's the case ...

**3**

votes

**1**answer

363 views

### Heuristic for Montgomery's conjecture

This is my third question on this site regarding Montgomery's conjecture -- and I apologize
if this is too much -- but I am still not understanding well why this conjecture is believed to be true.
...

**62**

votes

**6**answers

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 ...

**16**

votes

**1**answer

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 ...

**4**

votes

**1**answer

571 views

### Goldbach's conjecture and Euler's idoneal numbers

Recently, I stumbled upon an interesting statement regarding Quadratic Forms. It is quite well-known and, as I will describe briefly, equivalent to Goldbach's conjecture.
Let $p,q$ be odd primes and ...

**19**

votes

**4**answers

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 ...

**12**

votes

**2**answers

1k views

### Distinctive property of the primes 17 and 19?

Consider the question whether it is true that a prime number $p$ divides
$1^1+2^2+3^3+....+(p-1)^{p-1}$ if and only if $p \in \{17,19\}$.
For the obvious heuristic reasons, for large $n$ one would ...

**8**

votes

**3**answers

509 views

### Asymptotic bounds on $\pi^{-1}(x)$ (inverse prime counting function)

What are the current best asymptotic bounds on $\pi^{-1}(x)$, where $\pi(x)$ denotes the prime counting function (number of primes at most $x$)?
In other words, I am curious about the state of the ...

**2**

votes

**1**answer

221 views

### Given an even integer N, what is the minimum set of primes such that any even number x <= N can be expressed as the sum of two primes from the set?

Given an even integer N, what is the minimum set of primes such that any even number $x \leq N$ can be expressed as the sum of two primes in the set?
Goldbach's conjecture said Every even integer ...

**4**

votes

**1**answer

229 views

### Estimate on the prime-counting function $\psi(x)$.

There is an elementary statement that I believe I have read somewhere, but I can't remember where. I'd like to know if the statement is correct (in which case it is surely standard) and if so, where I ...

**4**

votes

**2**answers

287 views

### Are sums of the inverses of prime siblings finite?

PART I (Initial version)
Let $P$ be the set of all primes $2\ 3\ \ldots$. Let
$$P_d\ \ :=\ \ \{\ p\in P\ :\ \exists_{q\in P}\ \ 0 < |p-q|\le d\ \}$$
and
$$S_d\ :=\ ...

**21**

votes

**0**answers

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 ...

**70**

votes

**4**answers

26k 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 ...

**6**

votes

**6**answers

801 views

### Sequences equidistributed modulo 1

Let $\alpha$ be any positive irrational and $\beta$ be any positive real. We have the following results.
H. Weyl (1909): The fractional part of the sequence $\alpha n$ is equidistributed modulo 1.
...

**4**

votes

**1**answer

456 views

### p such that p+1 has a large prime factor, effectively

I was reading the Boneh-Franklin IBE paper, and it seemed rather conspicuous to me that they
didn't address the question of how to find primes $p$ and $q$ satisfying what they need (on page 19).
...

**0**

votes

**1**answer

411 views

### A possible consequence of Dirichlet's theorem about primes in arithmetic progression

EDIT : I copy-paste the beginning of a previous question since Gerry Myerson suggested this question should be self-contained.
"let's consider a composite natural number $n$ greater or equal to $4$. ...

**7**

votes

**1**answer

173 views

### Composing two-term sums from the same primes

The following is an old result of Erdős and Turán (American Mathematical Monthly, 1934):
Given a set of $2^n + 1$ distinct positive integers, all of its two-term sums cannot be composed of the same ...

**0**

votes

**4**answers

318 views

### The prime number $2$ [duplicate]

Possible Duplicate:
Why is 2 so odd?
I have read few books and articles, almost all of them refer that any prime $p>2$. Just wondering why it has to be $>2$?

**2**

votes

**1**answer

459 views

### To express $e^{\sum \limits_{k=0}^\infty q^{2^k}}$ as product terms of $(1-q^k)^{c(k)}$

$|q|\lt1$
$A(q)=\sum \limits_{k=0}^\infty q^{2^k}$
Easily We can see that
$$A(q)=q+A(q^2)\tag 1$$
Let's assume we redefine $A(q)$ as below
$A(q)=-\sum \limits_{k=1}^\infty c_k \ln{(1-q^k)}$
I ...

**2**

votes

**3**answers

407 views

### Is it true that $p^2+1$ is square free if $p>7$ is a Mersenne prime

For a problem in group Theory I need some information about the Mersenne primes:
Let $p=2^a-1>7$ be a Mersenne prime and so $a$ is an odd prime. Is it true that $p^2+1$ is square free. i.e.
if ...

**5**

votes

**2**answers

276 views

### Does group of 4 equidistant successive prime exists ?

For example
Group of 2 equidistant successive primes
3,5,7 distance 2
151,157,163 distance 6
Group of 3 equidistant successive primes
...

**0**

votes

**1**answer

261 views

### Factorization of $p^2+1$ where $p$ is a Mersenne prime

Let $p=2^a-1$ be a Mersenne prime and so $a$ is an odd prime if $p>7$. We know that if $p=7$, then $(p^2+1)/2$ is equal to $5^2$.
Can we prove that if $p>7$ , then $(p^2+1)/2$ is not equal to ...

**3**

votes

**1**answer

272 views

### Least non primitive root

There is an abundant literature, and even here on MO no shortage of questions, on the question of the smallest prime primitivee root modulo $q$ (where $q$ is a prime, or more generally
an odd prime ...

**4**

votes

**3**answers

268 views

### A divergent series related to the number of divisors of of p-1

Let $d(n)$ denote the number of divisors of $n$. Is it known that the series
$$\sum_{p \text{ prime}} \frac{1}{d(p-1)}$$
diverges?
This would follow immediately from the Sophie Germain Conjecture. ...

**1**

vote

**1**answer

184 views

### What are the best known lower and upper bounds for the second Chebyshev function $\psi(x)$

I was reading through Jitsuro Nagura's proof that there is always a prime between $x$ and $\frac{6x}{5}$ when $x \ge 25$.
In the paper, he uses the following bounds for the second Chebyshev function ...

**5**

votes

**2**answers

316 views

### special primes with p'=4p+1

How can I most quickly find a big prime, p, for which 4p+1 is also prime? For example, p=37 works. I wonder if these special primes have been researched and some characteristics are known. Are ...

**4**

votes

**1**answer

288 views

### A “bit” of primes

Is there anything known/proved/conjectured about the distribution of:
$$B(n) = \frac{(p_n-1)}{2} \bmod 2, \qquad p_n \mbox{ is the } n\mbox{-th prime}$$
i.e. the bit 1 of the binary representation ...

**2**

votes

**0**answers

119 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 ...

**6**

votes

**2**answers

596 views

### At what point would an elementary generalization of Bertrand's Postulate be interesting?

I know that in 1952 Jitsuro Nagura was able to show that there is always a prime between $k$ and $\frac{6k}{5}$ for $k > 24$.
At what point would an improvement on Nagura's result be interesting? ...

**6**

votes

**2**answers

726 views

### Approximate number of primes below a given integer?

The problem of the complexity of the exact counting problem for primes is interesting. The best result we have about primes is that it is hard for TC0. But counting the number of witnesses to a TC0 ...

**7**

votes

**0**answers

272 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 ...

**2**

votes

**1**answer

320 views

### At what point does Miller-Rabin become faster than trial division?

I've read in various places (and know) that Miller-Rabin is a much faster primality test than trial division for large $N$, but is much slower than trial division for small $N$.
My question is: how ...

**2**

votes

**0**answers

86 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 ...

**1**

vote

**2**answers

333 views

### product 1+1/p in terms of Chebyshev's theta or psi function

I would like to know if there is any formula for
$
\prod_{x<p\leq y}\left(1+\frac1p\right)
$
in terms of $\theta$ or $\psi$ functions
$
\theta(x)=\sum_{p\leq x}\log p
$
and
$
...

**2**

votes

**2**answers

393 views

### Random “pseudoprime” number generator ??

Hi
How can I generate pseudoprime numbers in a given interval without... ?
- going sequentially from the smallers to the largest ones (as with a Erathostenes Sieve)
- nor using slow probabilistic ...

**8**

votes

**2**answers

869 views

### Does this sequence exhausts the prime numbers?

We define recursively
$p_1=2,p_2=3$
and
$$p_{n}= \min_{(A,B)\in F_{n-1}}|A-B| $$
Where
$$
\begin{split}
F_n=\{(A,B) |&\gcd (A,B)=1,\quad |A-B| \not =1,
\\\
&\text{both $A$ and $B$ are ...

**2**

votes

**2**answers

229 views

### Catalan-type equations for prime powers

Do there exist nonzero integers $a,b,c$ for which the equation $$aX + bY = cZ$$ has infinitely many solutions with $X,Y,Z$ distinct prime powers?
For example, if there are infinitely many Sophie ...

**1**

vote

**1**answer

258 views

### primes of the form of 2^n+y^2

Dear All,
I wonder what the numbers(primes) of the form of 2^n + x^2 (where n is even) are called? What are their properties? Any references to look at?
Thank you.

**5**

votes

**2**answers

294 views

### Equivalence of two well-known forms of (RH): reference-request.

This is a reference-request about a very simple statement.
The Riemann hypothesis is well-known to be equivalent to
$$(1)\ \ \ \pi(x) = \mathrm{Li}(x)+O(x^{1/2} \log x)$$
and to
$$(2)\ \ ...

**0**

votes

**2**answers

469 views

### On reducible polynomials with positive coefficients, $1$ as constant coefficient and certain bounds on coefficients

Given $a \in \mathbb{Z}$ with $a > 1$. Let $g(x) \in \mathbb{Z}[x]$ be a polynomial with $g(a)=\pm 1$. Let $h(x) \in \mathbb{Z}[x]$ be a polynomial with $h(a)= p$, a prime. Let $g(x)$ and $h(x)$ ...

**2**

votes

**1**answer

539 views

### A formula combining Euler $\phi$ and $\gcd$

Let us fix a natural number $N>1$ and $a_1, \ldots, a_n$ natural numbers satisfying $0 \leq a_i < N$, with the property that $1+ \sum a_i$ is divisible by $N$. Let $\phi$ be the Euler totient ...

**4**

votes

**0**answers

318 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

**3**answers

598 views

### Mathematical techniques to reduce the amount of storage memory

Apologies for the length question. Those acquainted with the analytics industry will know that the next big thing in the information technology world will be the Big Data revolution where huge volumes ...

**27**

votes

**1**answer

907 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, ...

**22**

votes

**2**answers

3k 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 ...

**6**

votes

**2**answers

907 views

### Probability that randomly chosen integers from a restricted set of natural numbers are coprime

We know that the probability $P(k)$ of $k$ randomly chosen integers $(k \ge 2)$ from the set of natural number are coprime is
$$
P(k) = \frac{1}{\zeta(k)}.
$$
I am looking at a special case of ...

**0**

votes

**0**answers

199 views

### Prime numbers characterization

When, in one endeavour, I investigated prime numbers, I came up with a formula that characterizes primes, and the job was done in essentially this way:
First i defined a function $sr$ (sum of ...

**0**

votes

**0**answers

186 views

### Confirm/refute $f(x)$ where $f(x) = $x-th Mersenne prime ($M_p$) where $x$ is [1,2,3,4,5,6,7…]

While tinkering with numbers, I found $n=f(x)$ where $n = \sigma(\sigma(n)-n)$ and $x \neq p$ where $p$ is a Mersenne prime exponent, but I need help input in regard to improving accuracy.
First off, ...