mersenneforum.org Exercise 1.23 in Crandall & Pomerance
 Register FAQ Search Today's Posts Mark Forums Read

 2006-10-19, 00:43 #1 sean     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?
2006-10-19, 14:00   #2
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22·1,889 Posts

Quote:
 Originally Posted by sean 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) (eqn 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?
Take (what I have marked) equation 1 as given.

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.

 2006-10-23, 21:08 #3 sean     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.

 Similar Threads Thread Thread Starter Forum Replies Last Post lukerichards Number Theory Discussion Group 12 2018-01-22 16:45 jasong jasong 7 2013-09-20 11:20 Barry Fagin Math 2 2006-01-04 19:46 Numbers Math 16 2005-10-16 00:53 grandpascorpion Math 23 2005-01-24 20:11

All times are UTC. The time now is 04:38.

Thu Jun 1 04:38:20 UTC 2023 up 287 days, 2:06, 0 users, load averages: 1.01, 0.97, 1.10