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

4
votes
0answers
114 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
342 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
281 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
544 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
209 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
488 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
292 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
607 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
487 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
68 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 ...
23
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
340 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
911 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
454 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 ...
3
votes
2answers
299 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
312 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
148 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 ...
-1
votes
1answer
188 views

Number of different factors of given size in primorial

Let $b_n$ be number of bits in product of all primes from $1$ to $n$ which is approximtely $b_n\approx n$. What is the approximate number of distinct factors with number of bits ...
7
votes
0answers
180 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
399 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
308 views

Negative coefficient in an almost cyclotomic polynomial

Let $a,b,c,d$ be four prime numbers. We set the polynomial : ...
4
votes
0answers
285 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
653 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
394 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
291 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
360 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 ...
5
votes
1answer
420 views

Unexpectedly prime rich cubic polynomial

We got a cubic polynomial which is unexpectedly prime rich. Let $f(x)=29160 x^3 + 30132 x^2 + 8046 x + 643$ and $\pi_f(n)$ the number of primes values of $f(x)$ for $x \in [1,n]$. Let ...
0
votes
0answers
117 views

Polynomial identities for congruent numbers and Bunyakovsky's conjecture

Bunyakovsky's conjecture states that polynomial with integer coefficients takes infinitely many prime values unless there are obvious reasons not to. It appears to imply something about polynomial ...
10
votes
0answers
373 views

Between Fermat's primes and the twin primes

Let me start with a curiosity. The integers $11,13,17,19$ are prime numbers, and $101,103,107,109$ are prime as well. One might wonder whether there is another occurrence where $10^m+1,10^m+3,10^m+7$ ...
13
votes
0answers
427 views

Intersection between the sums of the first positive integers, primes and non primes

Is the following conjecture true ? $$\left\{\sum\limits_{\begin{array}{c}k=1\\k\in\mathbb{Z}\end{array}}^nk \ |\ n\in\Bbb Z\right\} \cap \left\lbrace ...
1
vote
0answers
97 views

Can someone explain some of the steps in this paper clearly?

I'm having trouble understanding the steps this paper makes to come to the conclusion $p_{f}(d) \sim e^d\sqrt{d}$ Marek Wolf, First occurrence of a given gap between consecutive primes, preprint, ...
7
votes
1answer
512 views

Are there effective small intervals in which primes are dense?

As mentioned in Terry Tao's comment to this question, it is constructively known that there are primes between sufficiently large cubes. $\:$ According to wikipedia, "there exists a constant $\: ...
1
vote
1answer
221 views

reference on Dirichlet theorem on primes in arithmetic progression

I appreciate if you could help me to find a reference (and a proof). Combining Dirichlet theorem on primes in arithmetic progression with Chebotarev densitiy theorem, we know that given two positive ...
0
votes
1answer
255 views

Are there infinitely many $k$ for which $\frac{\sigma(k)}{k}=n^p$ and $p$ is an odd prime? [closed]

I would like to know if there are infinitely many $k$ for which $$\sigma(k)/k=n^p$$ such that $m=k{n}^{p-1}$ with $m,n>0$ and $p$ is an odd prime? Note: $\sigma(\frac{m}{{n}^{p-1}})$ is the sum of ...
0
votes
0answers
151 views

arithmetic progressions with few primes

Is this true ? Let $\beta_0$ be a positive number. One may find $\beta>\beta_0$, $0<\lambda<1$, and infinitely many $q>1$ so that there exists an arithmetic progression of step $q$, $a_1, ...
2
votes
1answer
211 views

Counting function for prime pair with bounded gaps between them [duplicate]

I'll start by noting that I am not at all an expert on number theory. However I do use it in a proof and would like your assistance if possible. Yitang Zhang breakthrough result established that ...
13
votes
1answer
641 views

Elementary Proof of Infinitely many primes $\mathfrak{p} \in \mathbb{Z}[i]$ in the sector $\theta < \arg \mathfrak{p} <\phi $

A quick look at the primes in $\mathbb{Z}[i]$ suggests they might be evenly distributed by angle if we zoom out on a coarse enough scale. I would like ask about the much weaker statement forgetting ...
1
vote
0answers
184 views

Does the proof of Conjectures B and D of Hardy and Littlewood have any implication on the generalized Riemann hypothesis they used?

Does the proof of Conjectures B and D of Hardy and Littlewood have any implication on the generalized Riemannn hypothesis they used? In their paper, Some problems of 'Partitio numerorum'; III - On ...
7
votes
0answers
570 views

“Forthcoming paper” of Goldston-Graham-Pintz-Yıldırım

The above-named authors of [1] and its (significantly different) published version [2] write: In a forthcoming paper, we will show how the methods here can be extended to prove corresponding ...
7
votes
1answer
422 views

Approximating a real by a ratio of primes

Let $x$ and $y$ be positive reals in $(0,1)$ with $x < y$ and $y-x =\epsilon$. I seek smallest primes $p$ and $q$ such that $$x \le \frac{p}{q} \le (x+\epsilon) = y \;.$$ Q. What upper bound ...
3
votes
1answer
217 views

Least prime for which a square-free integer is a non-residue

Suppose $a$ is a square-free integer and $\left(\frac{a}{p}\right)=1$ for the primes $p\leq k$. I'll call $a$ a quasi-square of order $k$. What I am interested in is the maximum value of $k$ in terms ...
5
votes
0answers
118 views

Visibility in a prime orchard

This suggests a variant on Polya's orchard problem. That problem asks1 for which radius $\epsilon$ of trees at each lattice point within a distance $R$ of the origin block all lines of sight to the ...
2
votes
2answers
247 views

binomial/factorial identity mod p

In trying to determine the spectrum of a well-known ergodic transformation, I came up with the following useful (for me) result. Let $p$ be a prime and $a$ a positive integer. Then for $M$ a positive ...