Question

\[1\le \pi(2^n)-\pi(2^{n-1}) \le \dfrac{2^n}{n-1}\]

Answer 1

\(\pi(x)\) is the prime counting function
https://en.wikipedia.org/wiki/Prime-counting_function

Answer 2

So there is at least one prime between \(2^n\) and \(2^{n+1}\) and there can only be \(\dfrac{2^n}{n-1}\) many primes between the two powers of two?

Answer 3

Exactly!

Answer 4

This is horrible...

Answer 5

Use any theorems that you're familiar with...

Answer 6

It would be extremely uncomfortable to have no primes between two consecutive powers of two but I have no idea how to prove it.

Answer 7

I have simply used below postulate for the first inequality :
https://en.wikipedia.org/wiki/Bertrand%27s_postulate

Answer 8

The lower bound trivially follows from the Bertrand's postulate..

I'm still working on the upper bound...

Answer 9

Bertrand's postulate is the first inequality you cheater!

Answer 10

Haha you have a good eye ;)

Answer 11

It follows trivially implies you still have to do trivial work using Bertrand's postulate but this is Bertrend's postulate! Cheater!

Answer 12

I can do some trivial work if you insist

Bertrand's postulate give \(k \lt p \lt 2k\).
Letting \(k=2^{n-1}\) gives the lower bound in the present problem :)

Answer 13

hm

Answer 14

\[p_{n+1}<2P_n\]
this looks

Answer 15

Can't even use PNT to "morally" justify the upper bound. :(
\[
\begin{align*}
\pi(x)&\sim\frac{x}{\ln(x)}\\
\pi(2^n)-\pi(2^{n-1})&\sim\frac{2^n}{n\ln(2)}-\frac{2^{n-1}}{(n-1)\ln(2)}\\
&\sim\frac{(n-1)2^n-n2^{n-1}}{n(n-1)\ln(2)}\\
&\sim\frac{2^{n-1}(2(n-1)-n)}{n(n-1)\ln(2)}\\
&\sim\frac{2^{n-1}(n-2)}{n(n-1)\ln(2)}\\
\end{align*}
\]

Answer 16

i thnk i have a certain way of building up the primes

Answer 17

\(\pi(x)\sim\frac{x}{\ln(x)} \implies \pi(2^n) - \pi(2^{n-1})\sim 0 \)

since \(\sim\) is an asymptotic equivalence right ?

Answer 18

Yes it is asymptotic equivalence.

Answer 19

Oh it cannot be 0 as x/lnx is not constant..

Answer 20

nvm, your work looks sound...

Answer 21

It might be mathematically correct, but I don't see how it even justifies the upper bound.

Answer 22

@dan815 proving \(p_{n+1}\lt 2p_n\) isn't trivial... so im simply using bertrand's postulate for the lower bound

Answer 23

yeah we can't squeeze out an inequality out of asymptotic bound

Answer 24

\[
2^n-2^{n-1}=2^{n-1}
\]
If the upper bound is true, than between two consecutive powers of two the proportion of primes is at most \(\dfrac{2}{n-1}\).

Answer 25

are you saying

(number of integers) / (number of primes) = 2/(n-1)

?

Answer 26

Yes. I am just rephrasing the upper bound.

Answer 27

that looks very interesting...
as \(n\to\infty\), the ratio approaches 0

Answer 28

\[\lim\limits_{n\to\infty} \dfrac{\pi(n)}{n}=0\]

Answer 29

That is really a very useful conclusion to make out of the upper bound !

Answer 30

From Wikipedia,\[\pi(x)<1.25506\frac{x}{\ln(x)}\]
Not sure what can be made out of this.

Answer 31

Perhaps we can use that result at the end of :

\(\pi(2^n) - \pi(2^{n-1}) \le \dfrac{2^n}{n-1}\\~\\ \implies \sum\limits_{n=1}^m \pi(2^n) - \pi(2^{n-1}) \le \sum\limits_{n=1}^m \dfrac{2^n}{n-1}\\~\\

\implies \pi(2^m) \le \sum\limits_{n=1}^m \dfrac{2^n}{n-1} \)

Answer 32

Not really sure.. im feeling all dyslexic today...

Answer 33

The denominator is n-1 so it won't work?

Answer 34

Ahh need to fix that

Answer 35

\(\pi(2^n) - \pi(2^{n-1}) \le \dfrac{2^n}{n-1}\\~\\ \implies \sum\limits_{n=2}^m \pi(2^n) - \pi(2^{n-1}) \le \sum\limits_{n=2}^m \dfrac{2^n}{n-1}\\~\\

\implies \pi(2^m) \le 1+ \sum\limits_{n=2}^m \dfrac{2^n}{n-1} \)

Answer 36

Is \(\dfrac{2^n}{n-1}\) the Taylor series coefficient of some function? I remember it is.

Answer 37

ln(1-x) ?

Answer 38

http://www.wolframalpha.com/input/?i=power+series+-ln(1-x)

Answer 39

No it isn't ln(1-x). \(\dfrac{2^n}{n-1}\) seems to grow too fast for the series to converge.

Answer 40

I was thinking of replacing the right hand side of the inequality with a function that has the same Taylor series expansion. Does \(\displaystyle\sum_{n=2}^\infty\frac{2^n}{n-1}x^n\) converges for \(\displaystyle |x|<\frac{1}{2}\)?

Answer 41

Yeah
http://www.wolframalpha.com/input/?i=%5Csum_%7Bn%3D2%7D%5E%5Cinfty%5Cfrac%7B2%5En%7D%7Bn-1%7Dx%5En

Answer 42

...