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
3answers
566 views

Bound the error in estimating a relative totient function

Let $n=p_1^{e_1}\cdots p_k^{e_k}$ be an integer with $k$ prime factors. We know that the number of integers less than $n$ and coprime to it is $$\Phi(n)=n-\sum_i\frac n{p_i}\+\sum_{i \lt j}\frac ...
0
votes
1answer
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$. ...
8
votes
0answers
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, ...
62
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 ...
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). ...
13
votes
4answers
1k views

Arithmetic progressions without small primes

The following question came up in the discussion at How small can a group with an n-dimensional irreducible complex representation be? : Is it known that there are infinitely many primes p for which ...
6
votes
2answers
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
0answers
596 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, ...
3
votes
2answers
355 views

Are all counterexamples of OEIS A226181 both Poulet numbers and Proth numbers?

OEIS A226181: 3, 5, 7, 11, 13, 17, 19, 23, 29, 37, 41, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 113, 131, 137, 139, 149, 163, ... Primes $p$ ...
3
votes
3answers
452 views

Estimate for products of integers that are relatively prime with $N$

Let $N$ be a positive integer. Are there known estimates for the product of all numbers that are smaller than $N$ and relatively prime with $N$? One can assume that $N$ is free of squares, if this ...
80
votes
5answers
4k 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 ...
48
votes
4answers
3k 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 ...
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 ...
33
votes
1answer
3k 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 ...
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 ...
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 ...
15
votes
1answer
722 views

Sums of primes that are themselves prime

I'm not a math expert so this may be a trivial question; if $p_i$ is the $i$-th prime, let: $$S(n) = \sum_{i=1}^n p_i$$ be the sum of the first $n$ primes and $$P(n) = | \{1 \leq i \leq n \mid ...
24
votes
3answers
2k 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 ...
6
votes
6answers
800 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. ...
12
votes
1answer
552 views

Analytic lower bounds on the first sign change of pi(x) - li(x)?

There have been many results on the first sign change of $\pi(x)-{\mathrm{li}}(x)$: among others, Lehman, te Riele, Bays & Hudson, Demichael, Chao & Plymen, and most recently Saouter & ...
10
votes
1answer
2k views

The Green-Tao theorem and positive binary quadratic forms

Some time ago I asked a question on consecutive numbers represented integrally by an integral positive binary quadratic form. It has occurred to me that, instead, the Green-Tao theorem may include a ...
8
votes
6answers
1k views

Are there any interesting or lesser known proofs related to Bertrand's Postulate

There are 3 standard proofs of Bertrand's Postulate: (1) Chebyshev's original proof (2) Ramanujan's simplification of Chebyshev's proof (3) Erdos's proof I recently learned about the very ...
7
votes
2answers
419 views

A non-standard ergodic limit

Suppose $T$ is an ergodic measure-preserving transformation on a measure space $(X,\Sigma,\mu)$, and $f\in L^1(\mu)$. Does the limit $\lim_{X\to\infty} \pi(X)^{-1}\sum_{p\leq X} f(T^{p}x)$ exist ...
21
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 ...
9
votes
2answers
1k views

Abel summation of the alternating series of primes?

Consider the ordinary generating function of the sequence of primes ($2+3x+5x^2+7x^3 + ...$); by the ratio test and the prime number theorem, its radius of convergence is $1$. Thus, we might well ask ...
7
votes
2answers
577 views

What is the lower bound for highly composite numbers?

if $x=d(n)$ is the number of divisors of $n$, what is the tightest lower-bound for $n$ only given $x$? http://en.wikipedia.org/wiki/Highly_composite_number
6
votes
3answers
879 views

Values where infinite products of primes and composites are equal

Highly grateful for your help/steers on the following question (at the end): Take the infinite product: $$\displaystyle T(s) = \prod _{n=2}^{\infty } \left( \dfrac{{n}^{s}} {{n}^{s}-1}\right)$$ for ...
6
votes
2answers
1k views

Can a number be factored quickly, given the sum of its prime factors?

This is perhaps most naturally phrased as a promise problem. Given numbers $n$ and $s$, where $s$ is the sum of the prime factors of $n$ (distinct or with multiplicity; I imagine both variants will ...
5
votes
3answers
631 views

a question for the prime counting function

A famous inequality that has been proved by J.B. Rosser and L. Schoenfeld says that $\frac{n}{\ln n-1/2}$ < $\pi(n)$<$\frac{n}{\ln n-3/2} , n\ge 67$. Using this inequality we can prove ...
12
votes
3answers
2k views

The multiplicative order of 2 modulo primes

Artin's Conjecture says that any positive integer, which is not a square, is a primitive root modulo infinitely many primes. Christopher Hooley gave in Hooley, Christopher (1967). "On Artin's ...
10
votes
1answer
352 views

Primes dividing $2^a+2^b-1$

From Fermat's little theorem we know that every odd prime $p$ divides $2^a-1$ with $a=p-1$. Is it possible to prove that there are infinitely many primes not dividing $2^a+2^b-1$? (With ...
9
votes
1answer
308 views

Squarefree numbers $n$ such that $432n+1$ is also squarefree

This is a second attempt (see Primes $p$ such that $432 p +1$ is prime) Is the set of squarefree numbers $n$ such that $n(432 n+1)$ is also squarefree known to be infinite? Fact: the number of such ...
7
votes
1answer
570 views

Least prime primitive root

For $p$ a prime number, let $G(p)$ be the least prime $q$ such that $q$ is a primitive root mod $p$, that is $q$ generates the multiplicative group $(\mathbb Z/p\mathbb Z$)* . Is it known that ...
7
votes
3answers
1k views

Can the twin prime problem be solved with a single use of a halting oracle?

It occurred to me that if it were possible to determine whether a given program halts, that could be used to answer the twin primes conjecture A) Write a program which takes input n and then counts ...
5
votes
2answers
575 views

The shortest interval for which the prime number theorem holds [closed]

It is well known that the prime number theorem on the form \begin{align*} \pi(x+y) - \pi(x) \sim \frac{y}{\log (x+y)} \end{align*} breaks down for short enough intervals, e.g. taking $y=(\log ...
4
votes
1answer
192 views

Uniformity of the distribution of the prime numbers on the prime residue classes (mod $m$)

Given positive integers $m$, $r$ and $n$, let $\pi(m,r,n)$ denote the number of prime numbers $p \leq n$ in the residue class $r$ (mod $m$). Further let $1 = r_1 < r_2 < \dots < ...
4
votes
1answer
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 ...
4
votes
5answers
1k views

residue classes of primes, covering intervals and bounds on the different ways

Take the first $n$ primes $p_1,...,p_n$ and the primorial $P_n$ .Denote by $p_i$ every prime bigger than $p_n$ and smaller than $P_n$. 1) Is that true that there always be a number in any interval of ...
1
vote
1answer
116 views

Are there any theorems about a prime $p > k$ in a sequence stronger than Sylvester-Schur?

Sylvester-Schur says: "if $n \ge 2k$, then there is a number in the list $n − k + 1, n − k + 2,$ ... $, n$ divisible by a prime $p > k$." Shouldn't it also be true that if $n \ge k$, then there is ...
9
votes
2answers
497 views

Odd-bit primes ratio

Say that a number is an odd-bit number if the count of 1-bits in its binary representation is odd. Define an even-bit number analogously. Thus $541 = 1000011101_2$ is an odd-bit number, and $523 = ...
7
votes
1answer
450 views

The Bombieri Vinogradov Theorem restricted to moduli divisible by $k$

The Bombieri-Vinogradov Theorem states that given $A>0$, there exists $B>0$ such that for $Q=\sqrt{x}\left(\log x\right)^{-B},$ we have $$\sum_{q\leq Q}\max_{y\leq x}\max_{\begin{array}{c} ...
4
votes
1answer
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). ...
3
votes
1answer
463 views

Work down on the Upper bound of the Twin Primes [duplicate]

It can be shown using the Selberg Sieve method, that the maximum number of Twin primes less than $N$ is $$\frac{CN}{\ln^2(N)}$$ does anyone know if there has been any work done on finding an upper ...
1
vote
3answers
221 views

Powers of $2$ and the products of initial odd primes

NOTATION: $O_x$ -- the product of all odd primes $\le x$. E.g. $O_7=3\cdot 5\cdot 7 = 105$. QUESTION: Are the three ordered pairs $\ (d\ p)=(1\ 3)\ \ (2\ 3)\ \ (4\ 5)\ $ the only solutions of the ...
-1
votes
1answer
296 views

Primes $p$ such that $432 p +1$ is prime [closed]

Is the set of prime numbers $p$ such that $432 p + 1$ is also prime infinite? It doesn't follow from Dirichlet's theorem as far as I can tell.