mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2011-07-14, 00:47   #1
pbewig
 
Feb 2011
St Louis, MO

32 Posts
Default 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
pbewig is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Prime counting function records D. B. Staple Computer Science & Computational Number Theory 49 2020-11-06 22:02
New confirmed pi(10^27), pi(10^28) prime counting function records kwalisch Computer Science & Computational Number Theory 34 2020-10-29 10:04
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

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

Thu Nov 26 04:48:55 UTC 2020 up 77 days, 1:59, 3 users, load averages: 1.44, 1.31, 1.39

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.