Prime counting function- no error.

  • Thread starter Nash
  • Start date
  • #1
7
0

Main Question or Discussion Point

Prime counting function-- no error.

I have developed a prime counting function with no error; it returns the exact number of primes equal to or less than any number one chooses.

I am rather ignorant of progress in this field... Has this been done before? Please, ignore any skepticism you might have about my claim; even if were somehow wrong, I would still like to know if such a function is already in existence.

(edit) Note: This function does not require any list of primes or knowledge of the "nth prime number". It does not utilize any functions that are not valid, known, and easily computable.
 
Last edited:

Answers and Replies

  • #2
shmoe
Science Advisor
Homework Helper
1,992
1
Of course it can be found exactly, a basic sieve of Eratosthenes will do this. It can even be found exactly without explicitly making a list of all primes up to x (Meissel's and variants).

I'm possibly unfairly wary of your claim of "easily computable". We've had claims here before of being able to compute pi(x) in constant time, so I'll give you a chance to explain before becoming too judgemental. You might want to look at http://mathworld.wolfram.com/PrimeCountingFunction.html and compare your algorithms complexity with the ones listed.
 
  • #3
7
0
Mm... Well, the functions utilized within the larger function are easily computable (what I meant in saying so before was only that I haven't utilized any difficult functions that are defined by an algorithm and not a formula, and that everything I've done is "easily" computable, not necessarily "quickly"); the overall thing will become rather time-consuming as the numbers involve get longer. In practice, it wouldn't be very useful as a quick calculation, but it is exact.

I certainly don't have anything that can be computed in constant time. I would have to wonder if that would even be possible...

And has the sieve of Eratosthenes been written as an explicit mathematical function, or only as an abstract algorithm?

(edit) Many, if not all, of the methods for computation on that site depend on knowledge of the nth prime... I wasn't aware of any function that gives this value, or at least not through a method of practical complexity. It's common use, though, would indicate that there is...?
 
Last edited:
  • #4
shmoe
Science Advisor
Homework Helper
1,992
1
Nash said:
And has the sieve of Eratosthenes been written as an explicit mathematical function, or only as an abstract algorithm?
It's a very computable thing. No different than if you wanted log(4506) to 5 decimal places.

Nash said:
(edit) Many, if not all, of the methods for computation on that site depend on knowledge of the nth prime... I wasn't aware of any function that gives this value, or at least not through a method of practical complexity. It's common use, though, would indicate that there is...?
There are unwieldy asymptotics for the nth prime, but the use of [tex]p_n[/tex] in the algorithms you saw there is a notational one. If you look at Meissel's basic formula it involves a sum over the primes less than sqrt(x), the time it will take to find these will be inconsequential to the overall time of the algorithm. You might want to look at some of the papers at

http://www.dtc.umn.edu/~odlyzko/doc/cnt.html

where they have a very improved variant of Meissel's as well as a nifty "analytic" method.
 
  • #5
7
0
Thank you. I'll have to look at that.
 
  • #6
CRGreathouse
Science Advisor
Homework Helper
2,820
0
How fast is your function? Can you count the primes up to, say, 10^20 for us with your formula?
 
  • #7
92
0
Nash said:
I have developed a prime counting function with no error; it returns the exact number of primes equal to or less than any number one chooses..
Congratulations - can you tell us the number it returns for the largest known prime 2^25964951-1

By the way above prime has 7816230 decicimal digitits
 
  • #8
shmoe
Science Advisor
Homework Helper
1,992
1
AntonVrba said:
Congratulations - can you tell us the number it returns for the largest known prime 2^25964951-1

By the way above prime has 7816230 decicimal digitits
I'm sure you know that the current best algorithms can't come anywhere near finding pi(2^25964951-1) in what could be considered a "reasonable" amount of time.

A claim of an algorithm for computing pi(x) exactly is not an unreasonable thing, I've mentioned a few methods in this thread. What is most interesting (assuming the method is correct) is both it's speed and whether the approach is novel in some way. Of course there's no way to judge any of these criterea without seeing the proposed method.
 
  • #9
7
0
Yes, I assume that mine is not any sort of a breakthrough. I lack any software to run it efficiently, though, so I really can't test to see how fast it does run.

I have a formula for the nth prime, as well (actually, I have a formula for the product series of all primes 1 through [tex]\pi (w)[/tex], and I have one trivial equation to work out in order to complete the formula for the nth prime)-- this one is insanely inefficent, and I'm sure there are infinitely better ones, but it was still interesting to make.

Might you have any suggestions as far as mathematics software goes?

Note: By "inefficent" I mean that it will take a long time to calculate, not that it is in any way inaccurate.
 
Last edited:
  • #10
789
0
What is your algorithm?
 
  • #11
25
0


I can also compute pi(x) exactly without finding ANY primes smaller than x or sqr(x). It also do not require successive division by primes or the value of a previous pi (y) for y < x. The terms are required to be computed like in:

max {n in IN : 5*7 + 6*5*7(n-1) <= x}

and uses only four constants, all discardable. This is equivalent to computing:

floor ((x - 5*7 + 6*5*7)/6*5*7).

There are many terms however. The formula coefficients needs to be computed and stored in memory.

The method is much simpler than Extended Meissel-Lehmer algorithm but requires more storage space for large x. The storage requirement is of order:

b_4 = 4
b_n = b_(n-1) + n -1

for large n. Can this be written in big O notation?o:):surprised
 
  • #12
CRGreathouse
Science Advisor
Homework Helper
2,820
0


It's O(n^2) -- actually, b(n) = (n^2 - n - 4) / 2.

That's a huge amount of memory, though. Every time I start Pari it calculates the primes up to a trillion (taking maybe 1-2 seconds). If your memory is in bits, this size calculation would take 56,000 terabytes!
 
  • #13
25
0


Thank you. It looks totally impractical then. Just sending it through a register will take 35925 days at 25M per second.

I will post the formula compution method somwhere. The formula can be studied statisticly (distribution of coefficients). There are terms that may be zero if computed in the sets congruent to 1 (mod 6) or 5 (mod 6) and they may be predictable.

Maybe someone can fit more powerfull ideas to it or find the complement calculation of it (it counts composites). Maybe it is not so useless theoretically and can be used in proofs.

How is O(n^(1/2 + e)) for any e > 0 a better upper bound than O(n^2) - doesn't it mean the storage is <= Cn^(1/2 + 1/1000) or Cn^(1/2 + 1000) or ...
 
  • #14
CRGreathouse
Science Advisor
Homework Helper
2,820
0


Maybe someone can fit more powerfull ideas to it or find the complement calculation of it (it counts composites). Maybe it is not so useless theoretically and can be used in proofs.
That does happen -- sometimes new ideas are more important than being immediately practical (because practical improvements come later). AKS was improved, for' reasonable' numbers (say, 100 digits), over a billionfold since its original publication.

How is O(n^(1/2 + e)) for any e > 0 a better upper bound than O(n^2) - doesn't it mean the storage is <= Cn^(1/2 + 1/1000) or Cn^(1/2 + 1000) or ...
It's better because e can be chosen to be less than 1.5.
 
  • #15
25
0


The pi(x) counting method is posted at:

http://www.scribd.com/doc/21131936

entitled:

"Upper and Lower Bounds for the Divisor Function"

I post it there for comments or help with improving it. If someone can help me improve it I will add the name as co-writer.
 
  • #16
25
0

Related Threads for: Prime counting function- no error.

Replies
27
Views
5K
Replies
21
Views
6K
  • Last Post
Replies
10
Views
5K
Replies
5
Views
3K
Replies
3
Views
2K
Replies
1
Views
2K
Replies
3
Views
3K
  • Last Post
Replies
5
Views
3K
Top