mersenneforum.org Legendre's prime counting function
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2011-07-14, 00:47 #1 pbewig   Feb 2011 St Louis, MO 32 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

 Similar Threads Thread Thread Starter Forum Replies Last Post D. B. Staple Computer Science & Computational Number Theory 50 2020-12-16 07:24 kwalisch Computer Science & Computational Number Theory 34 2020-10-29 10:04 MarcinLesniak Miscellaneous Math 41 2018-03-29 16:30 Steve One Miscellaneous Math 8 2018-03-06 19:20 Steve One Miscellaneous Math 20 2018-03-03 22:44

All times are UTC. The time now is 10:51.

Fri May 7 10:51:16 UTC 2021 up 29 days, 5:32, 0 users, load averages: 3.11, 3.12, 3.09