Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

If you knew Pi(x) for every number

  1. May 3, 2006 #1
    If we knew the prime number counting function [tex] \pi(x) [/tex] then how could we recover the n-th prime?..of course an easy solution would be inverting this function [tex] \pi(x) [/tex] to get for integers the p-th prime..the question is..is there no other form of getting the nth prime by summing some values of the prime counting function over n or something similar i mean:

    [tex] P_{n}= \sum_{1}^{2^{n}} F(x, \pi(x) ) [/tex] how do you get this formulas?..thank you.
     
  2. jcsd
  3. May 4, 2006 #2

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    How exactly would we store an infinite number of numbers?

    And if we could store an infinite number of numbers, why not just store all primes?
     
  4. May 4, 2006 #3
    As long as there are only a countably infinite number of numbers needing to be stored, the straightforward way of storing them would be to define a mapping from the naturals to the set of numbers needing to be stored. As long as that mapping doesn't take an infinite number of instructions, the storing can be done exactly.

    E.g. 1, 4, 9, 16, 25, 36, ... is an infinite number of numbers that can be stored by the function an=n2.

    I'm not sure that [itex]\pi (x)[/itex] has a mapping with a finite number of instructions. If it did, that mapping could be used to create a mapping with a finite number of instructions for the primes, and vice versa. I think the mapping of the naturals to the primes is what eljose is after. To get the nth prime from [itex]\pi (x)[/itex] is simply a matter of finding the smallest x such that [itex]\pi (x)[/itex]=n.
     
  5. May 4, 2006 #4

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    No!

    That's having a 1-1 mapping from the natural numbers to the set in question, we have lots of those.

    eljose said "If you knew Pi(x) for every number", not had a 1-1 mapping for it. For example I know every number which is a divisor of 6. I have a 1-1 mapping from n -- > n2, I don't know all square numbers.

    Fine point, but needs to be made.
     
  6. May 5, 2006 #5
    the question is that in "Mathworld" and other pages they give formulas for the n-th prime [tex] \p_{n} [/tex] by assuming they know the function [tex] \pi(x) [/tex] for example at the link:

    http://mathworld.wolfram.com/PrimeFormulas.html
     
  7. May 5, 2006 #6

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    So? Seems like an o.k way to do it to me.
     
  8. May 6, 2006 #7

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    And here we go again: eljose, we know exactly what pi(x) is: it is the number of primes less than or equal to x. We just do not have a way to write this in either 'elementary' functions of x, or a quick enough algorithm for finding it by brute force.
     
  9. May 6, 2006 #8
    Do mathematicians believe there is a way to write it in an elementary way or can it be proven that it cant ?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: If you knew Pi(x) for every number
Loading...