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

2×5×23 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
 
"Bob Silverman"
Nov 2003
North of Boston

22·1,889 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

2·5·23 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 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔