Bertrand's postulate states that there is a prime $p$ between $n$ and $2n-2$ for $n>3$. According to Dirichlet's theorem we have that a sequaence $$a\cdot n+b$$ has infinite primes iff $a$ and $b$ are relatively prime. So in some sense, Bertrand's postulate gives a maximum of time for encountering a prime in the sequence $$2\cdot n+1$$ So, the question is: there is a generalization of Bertrand's Postulate for sequences $a\cdot n+b$ that accomplish the Dirichlet's theorem?

EDIT: (For a more concise explanation of the particular generalization.) We know that given $$a_n=2\cdot n+1$$ we have that for all $m$ there is a prime in the sequence greater than $a_m$ and less than $a_{2m}$. So, the thing is that if there is some generalization of Bertrand's Postulate using the sequence form, for an arbitrary sequence $$c_n=a\cdot n+b$$ with $a$ and $b$ coprime. Something as, for every relatively prime $a$ and $b$, there is a $k\leq a\cdot b$, such that for all $m$ there is a prime in the sequence between $c_m$ and $c_{k\cdot m}$.

Such kind of thing is what I am looking for.

  • $\begingroup$ I believe you want e.g. "There always exists a prime in the arithmetic progression $a\pmod{q}$ between $n$ and $f_{a,q}(n)$ for $n\ge k_{a,q}$." There's Linnik's theorem to bound the first prime from above. Cramér's model should suggest the number of primes in the progression less than or equal to $x$ is $$\frac{\pi(x)}{\phi(q)}+O((x/q)^{1/2}\log(qx))$$ but Maier's theorem throws a wrench at this; see here. $\endgroup$ – anon Sep 6 '11 at 21:42
  • $\begingroup$ Your type of generalization will also be interesting -although I would be more comfortable if $f_{a,q}$ and $k_{a,q}$ would be concrete easily computable things, but for that normally is requiered first the othe. I will look the material you cite, because it seems interesting and due that I am only some kind of beginner in number theory. $\endgroup$ – Josué Tonelli-Cueto Sep 7 '11 at 8:24
  • $\begingroup$ The facts I cited are only related commentary on the distribution of primes in arithmetic progressions. It seemed to me the statement about primes being between $n$ and $f(n)$ would be a natural generalization, but such an $f$ might not be linear as it is in the basic $1\pmod2$ case. $\endgroup$ – anon Sep 7 '11 at 8:41

One generalization of Bertrand's postulate I know is a theorem of Sylvester and Schur. See for example http://www.math.uiuc.edu/~pppollac/sschur.pdf

The theorem says that for any positive integer $k$ the product of $k$ consecutive integers greater than $k$ contains a prime factor greater than $k$.

I hope this helps you somehow.

  • $\begingroup$ Thanks, although I am interested in generalizations for sequences of Dirichet's theorem more beacuse I want to know if one can guarantee computationally if there is a maximum time to find a prime in the next prime from a given term. Nevertheles, it is an interesting generalization. $\endgroup$ – Josué Tonelli-Cueto Sep 6 '11 at 21:04

The answer is that there is such a generalization of Bertrand Postulate. For fizing constants, in the rest of the answer $a$ and $b$ will be coprime numbers, and $c_n$ will be given the sequence by


We consider the prime number theorem for arithmetic progressions, this say that

$$\pi_{a,b}(x)\sim \frac{1}{\varphi(b)}\frac{x}{\log x}\text{,}$$


$$\pi_{a,b}(x)=\text{Card}\{p\leq x\,|\,p\text{ is prime and }p\equiv a\text{ (mod }b\text{)}\}\text{,}$$

$\phi$ is the Euler's totient function and $\sim$ denote that the limit of the quotient of the two functions tends to $1$ as $x$ tends to infinity. Let now $\rho_{a,b}$ be given by

$$\rho_{a,b}(n)=\text{Card}\{k\leq n\,|c_n\text{ is prime}\}\text{,}$$

we can show by straighforward calculation that


From this, we have by the previous theorem that

$$\rho_{a,b}(n)\sim \frac{1}{\varphi(b)}\frac{a+bn}{\log (a+bn)}\text{,}$$

and so, by standard methods of analysis,

$$\rho_{a,b}(n)\sim \frac{b}{\varphi(b)}\frac{n}{\log n}\text{.}$$

Here, we can show, that for all $\varepsilon>0$,

$$\lim_{n\to \infty}\rho_{a,b}((1+\varepsilon)n)-\rho_{a,b}(n)=\infty$$

and thus define $N_\varepsilon$ as the first $n$ for which the previous difference is positive for all natural numbers greater or equal than it, i.e. $\rho_{a,b}((1+\varepsilon)n)-\rho_{a,b}(n)$ is positive for all $n\geq N_\varepsilon$ and negative for $n=N_\varepsilon-1$.

Therefore, we conclude that given $\varepsilon>0$, for all $n\geq N_\varepsilon$ there is a $k$ between $n$ and $(1+\varepsilon)n$ such that $c_k$ is prime. Furthermore, we can make $\varepsilon$ big enough such that $N_\epsilon$ is zero, since

$$\varepsilon\mapsto N_\varepsilon$$

is monotonous decreasing function. In this way, we obtain Bertrand's postulate for arithmetic progressions.


Here is another generalization

Let $n$ and $k$ be positive integers such that $n > 1.1\log(2.5k)$ then there are at least $k-1$ primes between $n$ and $kn$.

Ref: https://arxiv.org/pdf/1710.09891.pdf


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.