Prime counting function- no error.

In summary, the conversation revolves around the development of a prime counting function that is claimed to be error-free and able to calculate the exact number of primes equal to or less than any given number. The function utilizes easily computable functions and is not dependent on any list of primes or the knowledge of the nth prime number. The conversation also discusses the efficiency and practicality of this function, as well as other methods and algorithms for computing the prime counting function. Some members also share their own algorithms for computing pi(x) exactly without needing a list of primes or knowledge of the nth prime. The conversation ends with a summary of the methods and their computational complexities.
  • #1
Nash
7
0
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:
Physics news on Phys.org
  • #2
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
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
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
Thank you. I'll have to look at that.
 
  • #6
How fast is your function? Can you count the primes up to, say, 10^20 for us with your formula?
 
  • #7
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
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
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
What is your algorithm?
 
  • #11


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:)
 
  • #12


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


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


talanum1 said:
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.

talanum1 said:
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


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

1. What is the prime counting function?

The prime counting function, denoted as π(x), is a mathematical function that counts the number of prime numbers less than or equal to a given number x.

2. How is the prime counting function calculated?

The exact formula for the prime counting function is π(x) = li(x) + O(sqrt(x)log(x)), where li(x) is the logarithmic integral function. However, there are also various approximations and algorithms that can be used to calculate the prime counting function more efficiently.

3. What is the significance of the prime counting function?

The prime counting function is important in number theory and has practical applications in fields such as cryptography and computer science. It also plays a crucial role in the study of prime numbers and their distribution.

4. Can the prime counting function have an error?

Yes, the prime counting function can have an error due to the use of approximations and algorithms. However, as the value of x increases, the error decreases and becomes negligible.

5. Are there any open problems related to the prime counting function?

Yes, there are several open problems and conjectures related to the prime counting function, such as the famous Riemann Hypothesis which concerns the behavior of the prime counting function at extremely large values of x.

Similar threads

  • Linear and Abstract Algebra
Replies
6
Views
3K
Replies
10
Views
990
  • Quantum Physics
Replies
5
Views
693
  • General Math
Replies
1
Views
1K
Replies
2
Views
3K
  • Linear and Abstract Algebra
Replies
15
Views
4K
Replies
5
Views
5K
  • Linear and Abstract Algebra
Replies
2
Views
3K
  • Programming and Computer Science
2
Replies
65
Views
2K
  • Atomic and Condensed Matter
Replies
5
Views
1K
Back
Top