20061019, 00:43  #1 
Aug 2004
New Zealand
2×5×23 Posts 
Exercise 1.23 in Crandall & Pomerance
I know this isn't a factoring question, but you're the ones I like
to talking to. Excercise 1.23 in Crandall & Pomerance requires one to show sum_{p <= x} (ln(p) / p) = ln(x) + O(1) and then show that this implies pi(x) = O(x/ln x). I have done the first part, but I can't manage the second. I've been trying various bounds on the terms of the sum, so that I can write something like ln(x) + O(1) >= A * sum_{p <= x} 1 = A * pi(x) but nothing I have tried has given me a tight enough bound. Ideas? 
20061019, 14:00  #2  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}·1,889 Posts 
Quote:
Now, do a different estimate of the left hand side using a Stieltje's integral with respect to pi(x). i.e. int from 2 to x of log(y)/y d[pi(y)] Integrate by parts. 

20061023, 21:08  #3 
Aug 2004
New Zealand
2·5·23 Posts 
Thanks Bob. I still haven't got it sorted, although I now understand a lot more about the Stieltjes integral than I did before. I'll spend some more time on it, and may ask you privately if I still can't get it sorted in a few days.
Cheers, Sean. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A Mersenne number exercise  lukerichards  Number Theory Discussion Group  12  20180122 16:45 
Exercise for gaming time  jasong  jasong  7  20130920 11:20 
The original paper on the Crandall/Fagin DWT  Barry Fagin  Math  2  20060104 19:46 
Crandall & Pomerance  Numbers  Math  16  20051016 00:53 
Crandall/Pomerance/Euler series question?  grandpascorpion  Math  23  20050124 20:11 