# Proof for nonexistence of a prime counting function?

1. Mar 22, 2006

### 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?

2. Mar 22, 2006

### shmoe

3. Mar 22, 2006

### Nimz

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
$$\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.

4. Mar 23, 2006

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

5. Mar 23, 2006

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

6. Mar 23, 2006

### Loren Booda

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?

7. Mar 23, 2006

### 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

8. Mar 23, 2006

### 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 any one such non-iterative function.

9. Mar 23, 2006

### Zurtex

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?

10. Mar 23, 2006

### Hurkyl

Staff Emeritus
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
11. Mar 24, 2006

### 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 wich 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)$$

Last edited: Mar 24, 2006
12. Mar 24, 2006

### Loren Booda

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

13. Mar 24, 2006

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

14. Mar 25, 2006

### Loren Booda

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.

15. Mar 25, 2006

### matt grime

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

16. Mar 25, 2006

### Zurtex

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.

Last edited: Mar 25, 2006
17. Mar 27, 2006

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

18. Mar 28, 2006

### shmoe

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

19. Mar 28, 2006

### Hurkyl

Staff Emeritus
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.

20. Mar 28, 2006