Re: Pomerance/Crandall "Prime Numbers" book: inequality question

From: Robert Israel (israel_at_math.ubc.ca)
Date: 11/02/05 

Date: 2 Nov 2005 01:40:51 GMT

In article <11mg1esoqc3nb09@corp.supernews.com>,
yer mammy <yer_mammy@yahoo.com> wrote:
>The second edition of Pomerance and Crandall's "Prime Numbers" book is
>out, and before I buy it I figured I should read the first edition,
>which I already own (I bought it a few years ago and only read a few
>sections that were of interest to me at the time).
>
>Sadly, I can't figure out the following inequality, which occurs -- even
>more sadly -- on page 6:
>
>x <= PROD( floor( 1 + (ln x) / (ln p) ) ), where x is a positive integer
>and the product is taken over all primes p <= x.
>
>Why is this inequality true?

Call the right side P(x) = product_p f(x,p).
f(x,p) = floor(1 + ln(x)/ln(p) = n iff p^(n-1) <= x < p^n. Thus f(x,p)
is the number of powers of p that are <= x. Consider selecting
one of those powers of p for each prime p <= x and multiplying them
together. This gives us P(x) distinct positive integers, and each
of the x positive integers <= x can be obtained in this way, so
x <= P(x).
 
Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada

Relevant Pages

  • REPOST: Re: Pomerance/Crandall "Prime Numbers" book: inequality question
    ... >which I already own (I bought it a few years ago and only read a few ... >Why is this inequality true? ... one of those powers of p for each prime p <= x and multiplying them ... This gives us Pdistinct positive integers, ...
    (sci.crypt)
  • Re: ranges of integer polynomials
    ... On the complement of the k-th powers for fixed k>1, a ... powers is the range of a polynomial. ... A Polynomial whose Range is the Positive Integers which are not ... It is convenient to have all variables range over the non-negative ...
    (sci.math)
  • Re: ranges of integer polynomials
    ... Can rangebe the set of all positive integer non-cubes? ... For which positive integers k>2, if any, can the set of all ... positive integer non-k'th powers be realized as range? ...
    (sci.math)
  • Re: ranges of integer polynomials
    ... Can rangebe the set of all positive integer non-cubes? ... For which positive integers k>2, if any, can the set of all ... positive integer non-k'th powers be realized as range? ...
    (sci.math)
  • Re: Whos *not* in the "198"?
    ... Sean MacDOnald wrote: ... > I bought the 198 files book. ... > who still has their powers. ...
    (rec.arts.comics.marvel.xbooks)
Loading