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

-5
votes
1answer
244 views

How to prove twin prime conjecture or Goldbach conjecture if we assume prime distribution is completely random? [closed]

If we assume that prime number distribution is COMPLETELY random (subject to 1/log(x) restriction), can we prove twin prime conjecture or Goldbach conjecture ? My feeling is that, this will be ...
5
votes
1answer
268 views

The limit of the following product? What is the closed form of the value?

Assume that $P_n$ is the $n$'th prime: Please help me solve the following $$\lim_{k\to\infty} {k}\prod_{n=1}^k \frac{P_{2n-1}}{P_{2n}}$$ I am not really sure quite where to start here as I am ...
4
votes
0answers
317 views

A problem on prime numbers

Given integers $a,b,c,d\in[2^n,2^m]$ with $m>n>1$, how many primes $p$ are there in $[n^\alpha,n^\beta]$ for some $1<\alpha<\beta$ such that $$0<a\bmod p<n^{\alpha/k}$$ $$0<b\bmod ...
4
votes
1answer
184 views

What is known about the largest prime divisor of the product of $k$ consecutive integers?

Take $k$ consecutive composite integers from a prime gap. What is known about the largest prime divisor of their product? It seems to me that except for the triplet $(8,9,10)$ and the pair $(8,9)$ , ...
6
votes
0answers
122 views

Asymptotic density of winning positions in “Prime Nim”?

Consider a single-pile NIM variant, played under standard (not misere) objective, with the rule that you may remove any prime number from the pile. The winning positions of this game are all numbers $...
4
votes
1answer
326 views

Upper bound for the first Hardy-Littlewood conjecture

About the Hardy-Littlewood conjecture by Terence Tao: Conjecture 2 (Prime tuples conjecture, quantitative form) Let ${k_0 \geq 1}$ be a fixed natural number, and let ${{\mathcal H}}$ be a fixed ...
2
votes
0answers
332 views

How big can a set of integers be if all pairs have bounded gcd

In this recent MO question, it was shown that the maximal cardinality of a subset $A(M,N)$ of $[1,N]$ where the pairwise GCD's of all set elements are upper bounded by $M,$ with $M^2\leq N$ has size ...
4
votes
1answer
396 views

About factorization in Zhang's proof of weak Twin Prime conjecture

Why does it need to firstly factorize the number n into two factors q and r( Lemma 4 in the paper,see the following)? What's the motivation. What if it doesn't do this factorization?
0
votes
2answers
326 views

Does theta(n)<n for all n imply the Riemann Hypothesis and/or vice versa?

I know that better and better bounds of the Chebyshev Theta and Psi functions are implied by knowing that the first (insert large number here) zeta zeroes lie on the Critical Line. These bounds, ...
2
votes
0answers
154 views

On sets of coprime numbers

We know that from prime number theorem that the number of primes below $n$ and above $\frac n2$ (denoted by $\pi_{n,\frac n2}$ is approximately $$\pi_{n,\frac n2}\approx\frac{n}{2\ln n}.$$ Denote by $...
2
votes
1answer
168 views

Gap between semiprimes

Is there a conjectured gap between semiprimes? There is a conjectured gap between primes in form of Cramer's conjecture. Using this we have $p_1\leq p_0+c(\log p_0)^2$ for consecutive primes $p_0$ ...
22
votes
1answer
689 views

How big can a set of integers be if all pairs have small gcd?

Suppose $A\subset[1,N]$ is a set of integers. If for any distinct $a,b\in A$ we have $(a,b)\leq M$ then how big can $|A|$ be? If $M=1$ then $|A|$ is at most $\pi(N)$ since the map $a\mapsto P_+(a)$ (...
6
votes
1answer
188 views

$N_p := \text{card}\{(x, y, z, t) \in (\textbf{F}_p)^4 : ax^4 + by^4 + z^2 + t^2 = 0\}?$

Assume that $ab \neq 0$. What is $$N_p := \text{card}\{(x, y, z, t) \in (\textbf{F}_p)^4 : ax^4 + by^4 + z^2 + t^2 = 0\}?$$I need this result, but unfortunately I am not a number theorist. Could ...
8
votes
0answers
170 views

Primes of the form $(2m+1)^2-2^{2s+1}$

The question is the following : Question: Does there exist infinitely many primes of the form $(2m+1)^2-2^{2s+1}$ with $m,s\geq 1$ ? Why this could be true: Bunyakowsky conjecture would ...
2
votes
0answers
203 views

Avoiding Chinese Remainder Theorem

Given $k\in\Bbb N$ with $k<(\log_2N)^{\frac1\alpha}$ where $\alpha>2$ is fixed and $N$ being some integer such that $$N<\prod_{i=1}^k\pi_i^{a_i}$$ where $\pi_1,\pi_2,\dots,\pi_{k-1},\pi_k$ ...
0
votes
0answers
111 views

Bounding $\dfrac{r(x)}{\pi(x+r(x))-\pi(x-r(x))}$ with $1\ll r(x)\ll \log^{4}(x)$

I would like to know whether it is possible to obtain the bounds $\sqrt{r(x)}\ll k(x)\ll r(x)$ where $k(x)={\pi(x+r(x))-\pi(x-r(x))}$ and $1\ll r(x)\ll \log^{4}(x)$ and thus $1\ll\dfrac{r(x)}{\pi(x+r(...
2
votes
2answers
345 views

Primes $p$ for which $2p-1$ is prime

It's a well-known open problem (Sophie-Germain primes) whether there are infinitely many primes $p$, $2p+1$. What about $p$, $2p-1$? Seemingly it's also an open problem (see here and the linked ...
3
votes
1answer
186 views

Is $2^n -1$ finitely many times the product of consecutive primes? [duplicate]

This question was asked at MSE but recieved no attention at all. Here it is: Are there finitely many $(n,k) \in \mathbb{N}^2$ with $2^n-1=p_1p_2\cdots p_k$ ? $p_1=3,p_2=5 , ...,p_k$ are ...
4
votes
0answers
117 views

Behavior of the “mean prime factor” of numbers

This question concerns the behavior of a function $f(\;)$ that maps each number in $\mathbb{N}$ to its mean prime factor. I previously posted premature questions, now deleted, which explains the cites ...
8
votes
1answer
353 views

Distribution of the number of prime factors

Count the number of prime factors of a number $n$ to include multiplicity, so that $$n=24=2^3 \cdot 3 = 2 \cdot 2 \cdot 2 \cdot 3$$ has $4$ prime factors, and $$n = 6500 = 2^2 \cdot 5^3 \cdot 13 = 2 \...
3
votes
1answer
284 views

Did Erdős prove there are two primes $4a+1, 4b+3$ between between $n$ and $2n$?

http://mathworld.wolfram.com/ChoquetTheory.html Is the claim in the link true? Here's the reference given there: https://www.renyi.hu/~p_erdos/1934-01.pdf Erdős proved that there exist at least ...
1
vote
0answers
124 views

A Question on Chinese Remainder Theorem [closed]

Let $p_1,p_2,\ldots,p_n$ be odd primes. Let $y$ be the unique solution of the Chinese Remainder Problem ( $0 \le y < m$, $ m = p_1\cdot p_2 \cdots p_n$) $ y = \frac{p_1-1}{2} \text{ mod } (p_1) $...
7
votes
3answers
556 views

Quantitative and elementary proofs of the Prime Number Theorem

I would like to know two things: one, whether the best quantative bounds in the Prime Number Theorem are still basically those given by the Vinogradov-Korobov zero-free region? and two, whether there ...
6
votes
0answers
216 views

Any ways to Simplify Daboussi's Argument for Prime Number Theorem?

One strategy to prove the Prime number theorem involves removing some factors: $$ \limsup_{x \to \infty} \underbrace{\frac{1}{x}\sum_{n \leq x} \mu(x)}_{\color{red}{A}}\leq \prod_{p \leq y} \left( 1 ...
4
votes
1answer
496 views

Green-Tao theorem for 1-central numbers

This question came to my mind this afternoon while trying to figure out a possible way to tackle de Polignac's conjecture, which states that every even positive integer can be written as the ...
17
votes
2answers
3k views

Does the equation $241+2^{2s+1}=m^2$ have a solution?

Let $p$ be a prime congruent to $1$ mod. 8. If $p= 17$ one has : $p+ 8 = 5 ^2$. If $p= 41$ one has : $p+ 8 = 7 ^2$. If $p= 73$ one has : $p+ 8 = 9 ^2$. If $p= 89$ one has : $p+ 32 = 11 ^2$. If $...
4
votes
2answers
294 views

Relative-totient function (2nd attempt)

Let $\Lambda(x,y)$ be the count of totatives of $x$ that are less than or equal to $y$. I am asking for the following result to be verified, (particularly the final proposal), I have found no ...
-1
votes
1answer
608 views

What is wrong with this counterexample to primality test assuming GRH? [closed]

From SMOOTH NUMBERS: COMPUTATIONAL NUMBER THEORY AND BEYOND Andrew Granville pp.13-14: 2j. Lenstra’s polynomial time test as to whether an integer that is conjecturally prime, is rigorously ...
6
votes
1answer
497 views

An elementary lower bound on the number of primes

Recall the second Chebyshev function: $$\psi(x) = \sum_{p \leq x} \lfloor \log_p x \rfloor \log p$$ where $x$ is a positive integer, and $p$ runs over all primes $\leq x$. In a hunt for an "...
1
vote
1answer
128 views

A deterministic and explicitly described walk which is like random ones

Consider a sequence $(X_i)_{i = 1}^{\infty}$ which every $X_i$ is $-1$, $0$ or $+1$ and lets define $Y_n = X_1+ \cdots + X_n$. We say the sequence $(X_i)_{i = 1}^{\infty}$ a Good Sequence if $Y_n \neq ...
0
votes
0answers
69 views

Is this sufficient condition for primality of numbers of special form of practical interest?

The best variant of deterministic primality is of complexity $ \tilde{O}(\log^{6}(n))$. For large $n$, this is significantly worse than $O(\log{n})$. Appears to me paper p. 16 gives sufficient ...
22
votes
2answers
1k views

Proof for new deterministic primality test

Claim: Let $p$ be a positive prime. Let $n \in \left\{1, 2, 3, ...\right\}$. Then $N = p\cdot 2^n+1$ is prime, if and only if it holds the congruence $3^{(N-1)/2} \equiv \pm1\ ($mod $N)$. If the ...
1
vote
1answer
343 views

Proof that $p_{n+1}-p_n\gg\frac{\log \log \log p_n}{\log \log \log \log p_n} \log {p_n}$ [closed]

I cannot find a proof of this theorem. May anyone assist? $p_{n+1}-p_n\gg\frac{\log \log \log p_n}{\log \log \log \log p_n} \log{p_n}$
10
votes
2answers
912 views

Update for 2015: least prime of form nq+1, with q prime?

I have received a complaint about my 2011 answer least prime in a arithmetic progression which, indeed, gives conflicting reports about this: given a prime $q,$ what can we say about an upper ...
7
votes
2answers
461 views

What is wrong with this deterministic algorithm efficiently generating large primes?

According to PolyMath (Strong) conjecture. There exists deterministic algorithm which, when given an integer k, is guaranteed to find a prime of at least k digits in length of time polynomial in k....
4
votes
2answers
314 views

Asymptotics of the least common multiple of the first natural numbers

What is $$ \limsup_{n \to \infty} \frac{\log(\mathrm{lcm}(1,2, \dots, n))}{n} \ \ ?$$
3
votes
1answer
100 views

Upper bound for OEIS A076689 “Smallest k such that k*p#+1 is prime”?

OEIS A076689 Is defined as smallest integer $a(n)=k$ such that $k n\#+1$ is prime, where $n\#$ is primorial, the product of the first $n$ primes. Lower bound appears $1$, the primorial primes. ...
-3
votes
2answers
327 views

The number of totatives to the nth primorial, in an interval shorter than the nth primorial

(The notation of this question will be improved over the next few days, sorry for the lack of clarity at the moment.) Can, and if so when can, we determine the amount of natural numbers which are ...
1
vote
1answer
150 views

Primes in simultaneous arithmetic progressions

Suppose we're given four positive integers $a$, $b$, $c$, $d$ such that $a$ and $b$ are coprime, and $c$ and $d$ are coprime. Is there a non-negative integer $k$ such that both $ak+b$ and $ck+d$ are ...
7
votes
0answers
183 views

Are there an infinite number of twin semiprimes?

A semiprime is a number that is the product of two (possibly equal) primes. Define twin semiprimes (my terminology) as two consecutive numbers both semiprimes. For example, $(57,58)$ are twin ...
6
votes
0answers
404 views

Prime gap counts in short intervals

Since it is conjectured that the twin prime count at $n\sim2 C_2\ \frac{n}{\log^2n},$ where $C_2 = \prod_{p\ge 3} \frac{p(p-2)}{(p-1)^2} = 0.66016 18158 \dots,$ it follows that the twin prime count ...
2
votes
2answers
198 views

Finiteness of number of consecutive primes with gap $4$

Assuming Riemann Hypothesis Hardy showed primes $3\bmod 4$ are more common than primes $1\bmod 4$ https://en.wikipedia.org/wiki/Riemann_hypothesis#Consequences_of_the_generalized_Riemann_hypothesis. ...
6
votes
1answer
309 views

Negative coefficient in an almost cyclotomic polynomial

Let $a,b,c,d$ be four prime numbers. We set the polynomial : $$P(X)=\frac{(1-X^{abc})(1-X^{abd})(1-X^{acd})(1-X^{bcd})(1-X^a)(1-X^b)(1-X^c)(1-X^d)}{(1-X)^2(1-X^{ab})(1-X^{ac})(1-X^{ad})(1-X^{bc})(1-X^{...
4
votes
0answers
287 views

Conjectured new primality test for Mersenne numbers

How to prove that this conjecture about a new primality test for Mersenne numbers is true ? Definition: Let $M_{q}=2^{q}-1 , S_{0} = 3^{2} + 1/3^{2} , \ and: \ S_{i+1} = S_{i}^{2}-2 \pmod{M_{q}}$ ...
18
votes
3answers
655 views

Are there open problems for primes which are known for probable primes?

Define "probable prime" (PP) to be natural $n>1$ satisfying $2^{n-1} \equiv 1 \pmod{n}$ or $n=2$. Probable primes are the union of the primes and base two pseudoprimes. This definition is much ...
7
votes
1answer
406 views

Bounded gaps between primes in arithmetic progressions

Has Zhang's work on bounded gaps between primes been extended to the following theorem? For any arithmetic progression $an+b,\gcd(a,b)=1$, there is a constant $H$ (depending only on $a$) such that ...
0
votes
0answers
144 views

The maximum lengthed sequence of prime numbers with certain conditions (denizens)

Definition - Denizen A sequence $\lbrace a_k \rbrace$ is a denizen if all of it's members are prime numbers, i.e $a_0, a_1, ... a_n \in \mathbb{P} $; and it satisfies the following condition; ...
1
vote
1answer
36 views

Prime constant graphicial representation [closed]

I have something to check. It is about prime constant (I don't know if it is officially so called), but it is created on following way. We start with binary point number represenation. Zero followed ...
-5
votes
1answer
303 views

Gauss-Wantzel theorem, Fermat primes and solvability of S_n [closed]

Gauss-Wantzel theorem asserts that a polygon with $n$ sides is constructible if and only if $n$ is a product of a power of $2$ and distinct prime Fermat numbers, where the Fermat number of index $k$ ...
4
votes
4answers
367 views

Prime divisors of values of a polynomial on an infinite set

This may be a well known problem: Let $f$ be a polynomial with integer coefficients. Is it possible for the set of prime divisors of values of $f$ on an infinite set of integers, to be finite? I ...