2011-07-14, 00:47 | #1 |
Feb 2011
St Louis, MO
9_{16} Posts |
Legendre's prime counting function
I am reading the discussion of the prime counting function in pages 10 through 34 of the second edition of Hans Riesel's book "Prime Numbers and Computer Methods for Factorization" and writing programs to compute pi(x) and phi(x,a) based on that discussion. Reisel gives two equations:
1.9: phi(x,a) = phi(x,a-1) - phi(x/p[a],a-1) 1.26: pi(x) = phi(x,a) + a - 1, with a = pi(sqrt x) Here p[n] is the nth prime, with p[1]=2. So I wrote a couple of quick little programs and calculated pi(10^6) = phi(10^6,168) + 167 = 78331 + 167 = 78498, which is correct. But then I noticed that I had made an error in my program, and instead of calculating a = pi(sqrt 10^6) = 168 I calculated a = p[sqrt 10^6] = 7919. Then pi(10^6) = phi(10^6,7919) + 7919 - 1 = 70580 + 7919 - 1 = 78498, which is also correct. My result holds for all the values of pi(x) that I attempted. Have I done something wrong? Or have I inadvertently done something right? Phil |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
New confirmed pi(10^27) prime counting function record | kwalisch | Computer Science & Computational Number Theory | 26 | 2020-05-29 18:49 |
Proof of Legendre's conjecture, that there is always a prime between n^2 and (n+1)^2 | MarcinLesniak | Miscellaneous Math | 41 | 2018-03-29 16:30 |
Counting Goldbach Prime Pairs Up To... | Steve One | Miscellaneous Math | 8 | 2018-03-06 19:20 |
Prime counting function | Steve One | Miscellaneous Math | 20 | 2018-03-03 22:44 |
Prime counting function records | D. B. Staple | Computer Science & Computational Number Theory | 43 | 2016-12-25 22:15 |