mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2006-10-19, 00:43   #1
sean
 
sean's Avatar
 
Aug 2004
New Zealand

3·73 Posts
Default 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?
sean is offline   Reply With Quote
Old 2006-10-19, 14:00   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by sean View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2006-10-23, 21:08   #3
sean
 
sean's Avatar
 
Aug 2004
New Zealand

21910 Posts
Default

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.
sean is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A Mersenne number exercise lukerichards Number Theory Discussion Group 12 2018-01-22 16:45
Exercise for gaming time jasong jasong 7 2013-09-20 11:20
The original paper on the Crandall/Fagin DWT Barry Fagin Math 2 2006-01-04 19:46
Crandall & Pomerance Numbers Math 16 2005-10-16 00:53
Crandall/Pomerance/Euler series question? grandpascorpion Math 23 2005-01-24 20:11

All times are UTC. The time now is 00:15.

Thu Aug 13 00:15:28 UTC 2020 up 26 days, 20:02, 0 users, load averages: 1.92, 1.49, 1.45

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.