Conference rusure::math

     Yes.  See note 804.*  You can even fill in the details of the
     proof! :-)
     
     Dan

	Brings up an interesting question.  Between 2 and 4 is only
	one prime, namely 3.

	Between 4 and 8 is TWO primes, 5 and 7.

	Between 8 and 16 are TWO primes again, 11 and 13.

	Between 16 and 32 are FIVE primes, 17,19,23,29,31.

	Can "we" prove that never again will we see two adjacent powers
	of 2 that only have ONE prime between them ?  (or can we
	find a case other than 2,4 in which it's true ?

/Eric

    re. .-1
    
    Eric, the sequence looks like: 

    { 2, 2, 2, 5, 7, 13, 23, 43, 75, 137, 255, 464, 872, 1612, 3030, ... }
      
    where 3030 is the number of primes between 2^15 and 2^16
    
    /Kostas
    
    

     The number of primes grows too fast, with

          pi(x) = the number of primes <= x

     satisfying
                               x
          lim     pi(x)   =  ------
         x -> oo              ln x

     The number of primes strictly between 2^n and 2^(n+1) for n > 1
     is then pi(2^(n+1)) - pi(2^n) and this almost doubles with each
     next n.

     Dan

    Unfortunately the formula
    
                             x
               pi(x)   =  ------
                           ln x

    is only an estimate; I don't know of any error bounds.  Until we can
    get a minumum guaranteed value, we'll never know for sure...it may be
    that somewhere "out there" there are 2^N-1 composite numbers between
    2^N and 2^(N+1).
    
    Does anybody know a nontrivial formula for the minimum number of primes < N?
    
      John

     re .5

>>    Unfortunately the formula
>>    
>>                             x
>>               pi(x)   =  ------
>>                           ln x
>>
>>    is only an estimate; I don't know of any error bounds.  Until we can

     When I read that, I thought to myself, I can't believe I said it was "=".
     Looking again at .4:

>>                                x
>>          lim     pi(x)   =  ------
>>         x -> oo              ln x

     Which is rather meaningless, but at least I didn't say they were equal.
     A proper way to phrase the result would be

                     pi(x)
          lim       --------  = 1
         x -> oo    x / ln x

     Yes, it is not exact, but it means that for epsilon > 0 no matter how
     small there is an A (which depends on epsilon) such that for all x > A,

          |   pi(x)       |
          | --------  - 1 | < epsilon
          |  x / ln x     |

     So one can pick an epsilon and determine a bound above which there will
     always be at least two primes between 2^n and 2^(n+1).  Then one need
     only check the finitely many cases below the bound.

     Dan

    Excuse my fast and loose usage of the equal sign in the same sentence
    with the word "estimate".
    
>          |   pi(x)       |
>          | --------  - 1 | < epsilon
>          |  x / ln x     |

    This is of course the proper definition.  But I'm not sure it makes the
    solution any easier.  Dan, I pick epsilon = 5.  What value of A makes
    the above inequality hold for all x > A?
    
      John

     Oops, I see now how you meant it; I had read it as correcting
     extracted text.

     Keep that cookie fresh, I will need to consult some references
     at home.

     Dan

	Excuse me, folks, but no one has presented a simple proof that
	for

		2^n< p(n) < 2^(n+1)

	p(n) is always greater than 1, where "p(n)" means the number of
	primes between the two consecutive powers of 2.

	What we've seen so far are two important points:

1)	Examining the sequence of p(n), they "seem" to go up.

2)	Apparently there's some complicated number theory that says
	that x/ln(x) approaches the number of primes less than x in
	terms of percentage, as x becomes larger.

	So, either we need a proof of this complicated theory, or we
	need a simple proof that p(n) is greater than 1 for all n>1.

	The simple proof is more desirable.

	Anyone know of one ?

/Eric

I believe that the proper relation of p(x) to x/ln(x) is looser than that;
I seem to remember it is just that

		p(x) = O(x/ln(x))

or, in other words, that there are constants c2 > c1 > 0 such that

	c1*x              c2*x
       ------  < p(x) <  -------   for all x (well, all x > 2 anyway...)
	ln(x)             ln(x)

A powerful result, but much looser than the limit in .-n

						Richie

     re .10

     Nope.  I'm sure of the limit.  The looser relation is much easier
     to prove, though.

     Dan

     The book I mention in note 804.0 has proofs for the
     following in its chapter XIV (problem numbers as in the
     book):
     
     10. (Chebyshev 1852) For x >= 2 and suitable positive
     constants A and B,
     
                     x                x
                  A ---- < pi(x) < B ----
                    ln x             ln x
     
     12. (Bertrand) If n >= 2 there is a prime strictly between n
     and 2n
     
     13. (Finsler)  pi(2n) - pi(n) >= 2 if n >= 6.
     
     14. (Chebyshev's theorem again)
     
                 1   x                x
                 -- ---- < pi(x) < 4 ----
                 12 ln x             ln x
     
     re .7
     
>>    This is of course the proper definition.  But I'm not sure it makes the
>>    solution any easier.  Dan, I pick epsilon = 5.  What value of A makes
>>    the above inequality hold for all x > A?
     
     According to 10 and 14, for epsilon = 5 you may use A = 2.
     
     re Eric's question, the result in problem 13 covers it.
     
     So there are proofs for these things, each proof is probably
     roughly the length of the one in notes 804.*.  How much
     demand is there for typing them in?
     
     Dan

Let n be a positive integer >= 2, p be a positive integer prime,
and x a positive real number >= 2.  The number of primes <= x is
usually written with the pi symbol, so let pi(x) be the number of
primes <= x.  Let C(n,m) = n!/(m!(n-m)!) be that binomial coefficient.
Let [y] be the least integer <= y for any real number y.  Let
t(x,p) be the largest integral power of p <= x, so that
t(x,p) = [ln x / ln p] and also p^t(x,p) <= x < p^(1+t(x,p)).

A) 2^n < C(2n,n) < 2^2n

     Proof:

     C(2n,n) = (2n)!/(n!)^2
             = (2n * ... * 2)(2n-1 * ... * 1)/(n!)^2
             = (2n * ... * 2)/n! * (2n-1 * ... * 1)/(n * ... * 1)
             = 2^n * (2n-1)/n * ... * 1/1

     This shows C(2n,n) is 2^n times a product of n >= 2 terms
     all of which, except for the last, are > 1 and the last is = 1.
     Therefore C(2n,n) > 2^n.

     It also shows C(2n,n) is 2^n times a product of n >= 2 terms
     all of which are < 2.  Therefore C(2n,n) < 2^n * 2^n = 2^2n.

B) [2y] - 2[y] is 0 or 1 for all reals y

C) The number of times the prime p divides n! is given by the
   sum of one for each of the [n/p] multiples of p <= n, plus
   one more for each of the [n/p^2] of those which are actually
   multiples of p^2, plus one more for each of the [n/p^3] of
   *those* which are actually multiple of p^3, plus ....  This
   infinite sum is really a finite sum because the terms for
   exponents greater than t(n,p) are all zero.  This sum is
   sum(m=1,...,oo) [n/p^m] = sum(m=1,...,t(n,p)) [n/p^m].

D) The number of times the prime p divides C(2n,n) [adding for
   the numerator and subtracting for the denominator] is therefore
   sum(m=1,...,oo) ([2n/p^m] - 2[n/p^m]) = 
   sum(m=1,...,t(2n,p)) ([2n/p^m] - 2[n/p^m]) by part (C).  By
   part (B) this is a sum of t(2n,p) terms each of which is 0 or 1
   and so 0 <= the number of times the prime p divides C(2n,n) <= t(2n,p).
   [digression:  therefore C(2n,n) is an integer]

E) The least common multiple of the numbers 1,...,n is the
   product over all primes p of p^t(n,p).  This infinite product
   is really a finite product as all of the terms for p > n are
   equal to 1.

F) By parts (D) and (E), C(2n,n) divides evenly into lcm({1,...,2n})
   and so C(2n,n) <= lcm({1,...,2n}) = prod(p <= 2n) p^t(2n,p).

G) By parts (A) and (F) 2^n < C(2n,n) <= prod(p <= 2n) p^t(2n,p).
   The product on the right has pi(2n) terms, each of which is <= 2n.
   Therefore 2^n < (2n)^pi(2n) and so n ln 2 < pi(2n) ln 2n and
   pi(2n) > (n ln 2) / ln 2n or pi(2n) > ((1/2)ln 2) 2n/ln 2n

H) By part (G) there exists a positive real number A such that
   pi(x) > A x/ln x for all x >= 2.

     Proof:

     To go from (G) to (H) seems easy enough, ((1/2)ln 2) almost
     works for A, except for the small difference between x/ln x
     and 2n/ln 2n.  The following just grinds through to show
     you only have to divide by 2 at most.

     Note that x/ln x decreases as x grows from 2 to e, reaches
     its minimum for x >= 2 at x = e, then increases as x
     increases for x > e, not reaching as high as it does for x=2
     until x >= 4.  For x >= e (i.e., in the increasing range)
     (x+1)/ln (x+1) < (x+1)/ln x = x/ln x + 1/ln x and so
     increasing x by 1 increases x/ln x by less than 1/ln x <= 1.

     Let x >= 4,  and let the positive integer n be such that
     2n <= x < 2(n+1), i.e., n <= [x/2].  x >= 4 so x/2 >= 2
     so [x/2] >= 2 so n >= 2 and therefore (G) applies.

     Thus pi(x) >= pi(2n) > ((1/2)ln 2) 2n/ln 2n.  But
     x/ln x <= x/ln 2n = 2n/ln 2n + (x-2n)/ln 2n < 2n/ln 2n + 2/ln 2n.
     <=  2n/ln 2n + 2/ln 4.

     So 2n/ln 2n > x/ln x - 2/ln 4 and therefore
     pi(x) > ((1/2)ln 2) (x/ln x - 2/ln 4).  For x >= 4, x/ln x
     always is >= 4/ln 4 and so -4/ln 4 >= - x/ln x, or
     -2/ln 4 >= - (1/2) x/ln x, so x/ln x - 2/ln 4 >= (1/2) x/ln x.
     Thus pi(x) > ((1/2)ln 2) (1/2) x/ln x = ((1/4)ln 2) x/ln x.

     If 2 <= x <= 4, then pi(x) is 1 or 2 and x/ln x <= 2/ln 2
     so there is an A1 such that pi(x) > A1 x/ln x; just let
     A1 < (1/2)ln 2 and then A1 x / ln x < 1 < pi(x).

     Now let A be the minimum of (1/4)ln 2 and A1.  A = (1/4)ln 2
     works, and for all x >= 2, pi(x) > A x/ln x.

I) prod(n < p <= 2n) p divides C(2n,n), because each such prime p
   occurs once in the numerator and not at all in the denominator.

J) By (A) and (I), prod(n < p <= 2n) p <= C(2n,n) < 2^2n and so
   sum(n < p <= 2n) ln p < 2n ln 2.  Therefore
   sum(p <= 2n) ln p <= 2n ln 2 + sum(p <= n) ln p.

K) sum(p <= x) ln p >= sum(sqrt(x) < p <= x) ln p
                    >= sum(sqrt(x) < p <= x) ln sqrt(x)
                    = sum(sqrt(x) < p <= x) (1/2)ln x
                    >= (1/2) (pi(x) - sqrt(x)) ln x

   where the last inequality holds because of the pi(x) primes p <= x,
   certainly at most sqrt(x) of them are <= sqrt(x).

L) By part (K), pi(x) <= sqrt(x) + (2 / ln x) sum(p <= x) ln p

M) sum(p <= 2^k) ln p < 2^(k+1) for all positive integers k

     Proof by induction:  For k = 1 this is ln 2 < 4 and is true.
     Assume the statement is true for k = 1,...,m and try to
     prove it true for k = m+1.

     By (J) sum(p <= 2n) ln p <= 2n ln 2 + sum(p <= n) ln p.
     So sum(p <= 2^(m+1)) ln p = sum(p <= 2 * 2^m) ln p
                               <= 2^(m+1) ln 2 + sum(p <= 2^m) ln p
     By the inductive hypothesis sum(p <= 2^m) ln p < 2^(m+1)
     Therefore, sum(p <= 2^(m+1)) < 2^(m+1) ln 2 + 2^(m+1)
                                  = 2^(m+1) * (1 + ln 2)
                                  < 2^(m+1) * 2 = 2^((m+1)+1)
     and so (M) is true for all positive integers k by induction

N) Let x be any real >= 2.  Let k = t(x,2) = [ln x / ln 2] so that
   2^k <= x < 2^(k+1).  Then sum(p <= x) ln p <= sum(p <= 2^(k+1)) ln p
   which by (M) is less than 2^(k+2) so sum(p <= x) ln p < 2^(k+2).
   But 2^k <= x so 2^(k+2) <= 4x therefore sum(p <= x) < 4x.

O) By (L) pi(x) <= sqrt(x) + (2 / ln x) sum(p <= x) ln p and so
   by (N)  pi(x) < sqrt(x) + (2 / ln x) 4x.  Therefore there
   exists a positive real number B such that pi(x) < B x/ln x for
   all x >= 2.

     Proof:

     We have pi(x) < sqrt(x) + 8 x/ln x for x >= 2.
     Let C be such that sqrt(x) < C x/ln x for all x >= 2.
     Then pi(x) < B x/ln x for B = 8 + C.  I think C = 1
     already works which gives 9 for B.  This is not a particularly
     tight bound.

P) (Chebyshev, 1852)  There exists positive real constants A and B
   such that for all real x >= 2

                  x                x
               A ---- < pi(x) < B ----
                 ln x             ln x

     Errors, if any, are mine, not Chebyshev's.

     He also proved that if the limit as x -> oo of pi(x) / (x/ln x)
     exists, then that limit must be 1.  That proof isn't much more
     involved than this one.  The hard part is to show that the limit
     does exist.

     Dan