Proof for nonexistence of a prime counting function?

[Loren Booda]

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?

 

[shmoe]

There are formulas that give prime numbers- http://mathworld.wolfram.com/PrimeFormulas.html

There are explicit formulas for the various versions of the prime number theorem, such as http://mathworld.wolfram.com/ExplicitFormula.html

Maybe you should have a look at those and decide what *exactly* it is you mean by 'formula'

 

[Nimz]

I think what is meant by a formula that predicts all primes is a formula that gives the primes and finitely many composites ... preferably, 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
\sum_{p} \frac{\sin p}{p}
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.

 

[shmoe]

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.

 

[matt grime]

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.

 

[Loren Booda]

Thanks, shmoe.

There exist a variety of formulas for either producing the nth prime as a function of n or taking on only prime values. However, all such formulas require either extremely accurate knowledge of some unknown constant, or effectively require knowledge of the primes ahead of time in order to use the formula (Dudley 1969; Ribenboim 1996, p. 186). There also exist simple prime-generating polynomials that generate only primes for the first (possibly large) number of integer values.

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?

 

[shmoe]

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

 

[Loren Booda]

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 anyone such non-iterative function.

 

[Zurtex]

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 anyone such non-iterative function.

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?

 

[Hurkyl]

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

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

Hypothesis: given n, we cannot find every prime p(n) from anyone such non-iterative function.

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).

 

[eljose]

-there are lot,s of tricks to obtain the prime number counting function, firs of all the function \pi(e^{x}) is the function which minimizes a certain functional J making \delta{J}=0, 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:

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

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:

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

where the "delta" here stands for first and second functional derivatives...with this we could obtain a certain number of approximations to the \pi(x)

 

[Loren Booda]

Hurkyl

We cannot find a non-iterative function that, when given n, computes the prime p(n).

To quote Charlie Brown: "That's it!"

 

[shmoe]

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.

 

[Loren Booda]

I'll give it a try:

Iterative functions f_n, f_n+1, f_n+2 ... can be described by f_n+1=g[f_n] where g represents a function.

 

[matt grime]

You really appear to be confusing a function with an algorithm to evaluate that function.

 

[Zurtex]

I'll give it a try:

Iterative functions f_n, f_n+1, f_n+2 ... can be described by f_n+1=g[f_n] where g represents a function.

Given x + y = z

Then:

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

And the limit:

\lim_{n \rightarrow \infty} z_n = z

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 x, y, z \in \mathbb{R} in terms of adding numbers of integers, which themselves can be expressed as iterative procedures.

 

[Loren Booda]

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.

 

[shmoe]

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.

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).

 

[Hurkyl]

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

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.

 

[Loren Booda]

Your facts are indeed helpful. You addressed directly the (false) assertion I attempted to make.

 

[-Job-]

I don't think we can categorize a function as iterative or non iterative. At least it wouldn't be helpful since every function can be rewritten in iterative form. In my opinion the difference between iterative and non-iterative functions is only in how they are presented. iterative form is used to let the reader become aware of a certain pattern, or for efficient use of space, or to represent functions composed of an infinite number of operations, but there is an equivalence between Iterative and Non-Iterative functions, if we were to make such a distinction.
I think what we mean by an iterative function here is one where the number of basic operations performed is a function of the input (not that these are equivalent), so what we're really asking is about the time complexity of a given function. What we'd want to know then is, for a function f(n) = nth-prime what is the minimum number of operations required, or, what is the minimum time-complexity. We know there is an f(n) with complexity O(n), linear amount of operations. What about constant? Is there an f(n) that requires only a constant c amount of operations? I would think not, but c can be arbitrarily large so it doesn't seem like a straightforward proof.

 

[eljose]

-Use variational calculus to obtain \pi(e^{t}) :D :D :D

-Another question i think that it was matt who pointed that the prime generating function in the sense that:

a(n)=p_{n} and a(n)=\sum_{p<n}f(n)