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

Proof for nonexistence of a prime counting function?

  1. Mar 22, 2006 #1
    Do you know of an attempt to disprove the existence of a formula which predicts all prime numbers, as opposed to the accustomed attempt to derive one?
     
  2. jcsd
  3. Mar 22, 2006 #2

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

  4. Mar 22, 2006 #3
    I think what is meant by a formula that predicts all primes is a formula that gives the primes and finitely many composites ... preferrably, zero of them. I have actually attempted to prove there can exist no such formula, but it depends on some theory of Fourier series that I'm not certain about. I think I remember hearing that if you have a periodic function with infinitely many discontinuities in one period, it's impossible to write a formula for the Fourier series that generates the function. It's pretty easy to find a few spots where
    [tex] \sum_{p} \frac{\sin p}{p} [/tex]
    is discontinuous. I haven't probed enough to determine whether all primes will create new discontinuities. But if they do, there will be an infinite number of discontinuities in a single period. Assuming what I think I remember hearing is correct, there should be no formula for predicting all primes.
     
  5. Mar 23, 2006 #4

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Once again I ask, what *exactly* do you mean by a "formula" that you hope to prove none exist after I've provided a link that has more than one 'formula'?

    From your post it looks like you mean to show you can't find a fourier series that has no "formula" describing it's coefficients? Same question about 'formula' applies.
     
  6. Mar 23, 2006 #5

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Here's a formula which 'predicts' the primes:

    f(n)=p_n a function from N to N, p_n is the n'th prime. Never fails to hit a prime, hits all of them....

    Of course, how you 'evaluate' that 'formula' is something else.
     
  7. Mar 23, 2006 #6
    Thanks, shmoe.
    Can one show that an evaluation generating any prime in "one step" (such as including the determination of an unknown constant or knowledge of all previous primes) is impossible, and that all one-step, finite prime generating polynomials are limited in their range of producing primes? I'm asking whether it is possible to disprove that there exists a one-step mathematical generator of all primes?
     
  8. Mar 23, 2006 #7

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    What counts as "one-step"?

    The kind of simple prime generating polynomials they are talking about are things like x^2+x+41, which gives a prime for x=0,1,2,...39. You can prove polynomials like this cannot always be prime. You might want to look at:

    http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html
     
  9. Mar 23, 2006 #8
    Shmoe, thanks again for your help.

    I suppose "one-step" can be defined as "non-iterative" (like the polynomials you just referred me to).

    Hypothesis: given n, we cannot find every prime p(n) from any one such non-iterative function.
     
  10. Mar 23, 2006 #9

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    So other than finite polynomials, what functions do you consider non-iterative?

    I mean functions like sin and cos all use iterations to calculate them numerically, along with almost all other interesting ones.

    Do you then take sums?
     
  11. Mar 23, 2006 #10

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    And, of course, evaluating polynomials, computing exponents, multiplying numbers, and even adding numbers require some sort of iteration or related concept.


    This hypothesis is false. I think you meant to say something like:

    We cannot find a non-iterative function that, when given n, computes the prime p(n).
     
    Last edited: Mar 23, 2006
  12. Mar 24, 2006 #11
    -there are lot,s of tricks to obtain the prime number counting function, firs of all the function [tex]\pi(e^{x}) [/tex] is the function wich minimizes a certain functional J making [tex] \delta{J}=0 [/tex], a trial function then could be the "eljose,s Exponential integral" (i was just joking so don,t take it too seriously) in the form:

    [tex] E_{i}(a,b,c,g,x)=\int_{-\infty}^{x}ge^{-at}/(t^{b}+c) [/tex]

    where a,b,c and g are real constant chosen in a way that dJ[a,b,c,g]=0

    another way is from beggining using the trial function Ei(x) use an interative method to obtain "corrections" to it...Newton,s method modified to include functionals imply the iteration process:

    [tex]f_{n+1}=f_{n}-\frac{\delta{J[f_{n}]}{\delta\delta{J[f_{n}}[/tex]

    where the "delta" here stands for first and second functional derivatives...with this we could obtain a certain number of approximations to the [tex]\pi(x) [/tex]
     
    Last edited: Mar 24, 2006
  13. Mar 24, 2006 #12
    Hurkyl
    To quote Charlie Brown: "That's it!"
     
  14. Mar 24, 2006 #13

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    I then have to ask what you mean by a "non-iterative" function? As Hurkyl points out even adding can be considered 'iterative', but I don't think you mean to exlude this.

    There's no way anything can be proven about a class of functions that you cannot describe precisely.
     
  15. Mar 25, 2006 #14
    I'll give it a try:

    Iterative functions fn, fn+1, fn+2 ... can be described by fn+1=g[fn] where g represents a function.
     
  16. Mar 25, 2006 #15

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    You really appear to be confusing a function with an algorithm to evaluate that function.
     
  17. Mar 25, 2006 #16

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    Given x + y = z

    Then:

    [tex]z_n = \frac{\left[ x *10^{n-1} \right] + \left[ y * 10^{n-1} \right]}{10^{n-1}} [/tex]

    And the limit:

    [tex]\lim_{n \rightarrow \infty} z_n = z[/tex]

    You can 'evaluate' edition this way, it doesn't make much sense to do so but it is a way of show addition can be described as an iterative procedure for [itex]x, y, z \in \mathbb{R}[/itex] in terms of adding numbers of integers, which themselves can be expressed as iterative procedures.
     
    Last edited: Mar 25, 2006
  18. Mar 27, 2006 #17
    Let me attempt another approach.

    Hypothesis: the most reduced function that generates all n primes, with n --> oo, has complexity approaching the most efficient process of factorization to ascertain those primes.
     
  19. Mar 28, 2006 #18

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    This is false, it's not necessary to factor a number to determine if it is prime or not, and primality testing algorithms are faster than general factoring ones (though will usually search for small factors first).
     
  20. Mar 28, 2006 #19

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Bleh, that's incredibly unclear. I really have no idea what you're saying. :frown:

    So I'll throw out some facts and hope it's helpful.

    Any algorithm that prints out the primes up to size N has time complexity at least pi(N) ~ N / log N.

    We know of algorithms that can do it in time complexity ~ N / log log N.


    This is much much better than the time it takes to test each number for primality, which would take time complexity ~ N (log N)^6.

    This is much much much better than the time it would take to actually try and factor each number up to size N.
     
  21. Mar 28, 2006 #20
    Your facts are indeed helpful. You addressed directly the (false) assertion I attempted to make.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Proof for nonexistence of a prime counting function?
Loading...