Prime Number Formulas: Find the Nth Prime

[Hurkyl]

I'm not trying to be stupid, i really think this is a semantic / linguistic confusion, not an argument.

Sure -- that's why, in mathematics, we strive to define things precisely, and then do our reasoning with our precisely defined notions.

Given the usual definition of 'function', it's obvious that there exist all sorts of functions defying your limitations. For example, there is the n-th prime function. Explicitly, it's a function of the positive integers satisfying p(1) = 2 and p(n+1) = smallest prime exceeding p(n).

And there are subclasses of functions which we can prove other theorems about. For example, every (nonconstant) polynomial function with integer coefficients must take on at least one nonprime value. Similarly, if f is such a polynomial, and it satisfies f(p)=0 for every prime p, then f is the zero polynomial.

On the other hand, we have Matiyasevich's theorem which implies that there exists a polynomial g in many variables with integer coefficients for which
$$g(p, x_1, x_2, \cdots, x_k) = 0$$
has an integer solution for the x's if and only if p is prime.


If you want to say interesting things about some subclass of functions, you are going to have to find some way to express precisely what sorts of functions you want to talk about, otherwise your posts won't really have much content.

 

[CRGreathouse]

So I think i am using a much more limited definition of function than you are.

Yes, and I'm not clear on what your definition is. First of all, though, can we stop using the term "function" in that sense? I'll refer to your meaning as a thompson-function instead (and qualify it with "integer", "real", "complex", or "quaternion" as needed). Here's my first go at a definition:

The class of integer thompson-functions is the least class of functions $$f:\mathbb{Z}\to\mathbb{Z}$$ including

• $$f(n) = 1$$
• $$f(n)=n$$
• $$f(n)=g(n)\star h(n)$$ where g and h are integer thompson-functions and $\star$ is exponentiation, multiplication, integer division, subtraction, or addition
• $$f(n)=g(h(n))$$ where g and h are integer thompson-functions

This allows functions like 5n^2 + 7 but not n!. How close did I come to your meaning of "function"?

Once we hash that out, you can explain the meaning of your conjecture: "All I mean is, there is no function F(M)=P for some input M that guarentees P is prime, and M is any single valued input, be it real, integer, complex or quaternian. If there where, it would be bloody famous and there'd be no need for prime testing algorithms. Especially if it was an invertable function!"

My guesses:

thompson's Conjecture (rev. 1): There exists no integer thompson-function f for which f(n) is prime for all n > 0.
thompson's (weak) Thesis (rev. 1): An integer thompson-function violating thompson's Conjecture would be strictly more efficient than any prime-listing algorithm that cannot be expressed as an integer thompson-function.
thompson's (strong) Thesis (rev. 1): A quaternion thompson-function violating a version of thompson's Conjecture would be strictly more efficient than any prime-listing algorithm that cannot be expressed as a quaternion thompson-function.

 

[thompson03]

My, this is quite the group of sarcastic and antagonistic people.

I'm so sorry that the point has been lost in favor of nitpicking semantics.

I will submit my last post with these quotes;

Prime numbers can be generated by sieving processes (such as the sieve of Eratosthenes), and lucky numbers, which are also generated by sieving, appear to share some interesting asymptotic properties with the primes. Prime numbers satisfy many strange and wonderful properties. Although there exist explicit prime formulas (i.e., formulas which either generate primes for all values or else the nth prime as a function of n), they are contrived to such an extent that they are of little practical value.

Euler commented "Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the mind will never penetrate" (Havil 2003, p. 163).

But if you mean a polynomial or some other simple formula, then no,
there is no such formula. I am quite sure it has been proven that
there is no polynomial whose values are exactly the prime numbers. If
you want a similar proof for other kinds of simple formulas, then you
need to specify what kinds of formulas you are talking about. (For
example, you want to make sure you rule out things like p_n and
related functions.)

But there are formulas for prime numbers, and sums of prime numbers,
and sums of their logs, and such things, that have to do with
complicated transcendental functions like the Riemann Zeta Function


If you wish to argue these, please sent your argument to

http://mathworld.wolfram.com/PrimeNumber.html
Prime Number -- from Wolfram MathWorld

and

http://mathforum.org/library/drmath/view/68246.html
Math Forum - Ask Dr. Math

I for one, have had enough.

Thank you so much for enlightening me to the attitudes of this particular community.

 

[huba]

My, this is quite the group of sarcastic and antagonistic people.

I do not agree.
Greathouse has been trying to help.

As far as I am concerned, I find it very valuable that anybody interested in maths, at whatever level, has the chance in this forum to ask questions and make comments, with a good chance that they will receive help or constructive criticism.

 

[CRGreathouse]

My, this is quite the group of sarcastic and antagonistic people.

I'm not being sarcastic and I'm not antagonizing you. I'm just trying to define, precisely, what you mean by a function.

I can't speak for the true feelings of the others on this thread, but I have not sensed any antagonism from anyone here -- though Hurkyl seems to be somewhat frustrated by the lack of a clear definition.

I'm so sorry that the point has been lost in favor of nitpicking semantics.

I thought you had said this was a question of semantics?

Although there exist explicit prime formulas (i.e., formulas which either generate primes for all values or else the nth prime as a function of n), they are contrived to such an extent that they are of little practical value.

Yes, I agree with that. I did see a paper once that had an explicit formula that had been optimized for computation, but it was still quite slow compared to the best-known algorithms.

Euler commented "Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the mind will never penetrate" (Havil 2003, p. 163).

I would argue that since the time of Euler we have penetrated much of this mystery -- though only a tiny fraction of the way toward the kind of understanding we have of, say, Euclid's geometry.

But that's getting a bit toward the philosophical, yes?

But if you mean a polynomial or some other simple formula, then no,
there is no such formula. I am quite sure it has been proven that
there is no polynomial whose values are exactly the prime numbers. If
you want a similar proof for other kinds of simple formulas, then you
need to specify what kinds of formulas you are talking about. (For
example, you want to make sure you rule out things like p_n and
related functions.)

There is no polynomial P(x) where P(1) = 2, P(2) = 3, and in general P(n) = p_n. But there are polynomials which take on positive values that are exactly the prime numbers.

 

[CRGreathouse]

I do not agree.
Greathouse has been trying to help.

Thanks for the vote of confidence. I thought I put together a reasonable post. I thought about the features thompson03 wanted in his functions, worked out a simple axiomatization, and worried that Hurkyl might be able to show by a simple example that it didn't have the properties I claimed for it. :D I'm still not entirely happy with it; nothing prohibits the function 0/0 = (1 - 1) / (1 - 1) from being defined, for example. But I wanted to get an example up more than I wanted to polish it, because perhaps thompson03 would think that some features were too much (exponentiation? integer division?) or that it left out important tools (trig functions, certain special functions to make up for the lack of series) that made the results too weak.

And I know that the conjectures I guessed at were too strong: for any reasonable definition f(n) = 2 is a function which always evaluates to a prime, so perhaps 'nonconstant function' is needed? But I wanted thompson03 to explain these restrictions himself since he, better than we, know what he's looking for.

 

[DeaconJohn]

I do not agree.
Greathouse has been trying to help.

As far as I am concerned, I find it very valuable that anybody interested in maths, at whatever level, has the chance in this forum to ask questions and make comments, with a good chance that they will receive help or constructive criticism.

Greathouse, Hubba has "hit the nail on the head," here.

You are to be commended for your patient effort to help lift Mr. Thompson to a higher level of understanding of modern efforts to find formulas for prime numbers.

Your experience with Mr. Thompson is indicative of the danger that a person submits himself to when he (or she) decides to "follow a call" to do something in this life with the hope that it will make a positive difference in the world. Even if that "call" comes in the form of a call to help others better understand and better appreciate the beauty of mathematics.

It is the "call" that makes the difference between a dull teacher and a great teacher. A teacher who is following a "call" will combine a love for his (or her) subject with a desire to communicate that love to others. Your contributions to this board clearly demonstrate that you are one of those individuals who have received such a "call," whether or not you are personally aware of it.

But, I do not mean to "put Mr. Thompson down" or to treat him with any lack of due respect. Everybody is "called" to treat every other human being with respect, and, personally, I take that as one of my highest priorities to do just that. I do not always succeed of course, but, at least I try.

On the other hand, there are a lot of people, sometimes including even me, that feel personally attacked when one of their cherished ideas (like "I am good at math and I know a lot about it") are attacked. There is no doubt that I suffered from this failing much more when I was younger, so I have a lot of sympathy for those who fall into this trap.

An unfortunate result of this situation is that the student (or the person who has put himslef in the position of student by his vast display of his own ignorance - like Mr. Thompson) rather than understanding the good intentions of the teacher, actually attacks the teacher and accusses him (or her) of being "sarcastic," "unfelling," "snotty," "pompous," "pedantic," "contolling," or whatever negatively overtonned term happens to pop into their mind. Do not think for a second that by stating this truth that I am putting myself above these people. I have made this mistake, and I continue to make this mistake, so I myself am one of these people! Naturally, it is helpful to me to be aware of this problem, and, when I do find myslef doing it, I do my best to apologize as best I can and as quickly as I can. This situation is simply one more example of the fact that nobody is perfect.

Coming under these kind of attackes is a serious danger that people like you face, but there are even more serious dangers that teachers who take their jobs seriously also face.

For example, when I was a young math teacher at LSU Baton Rouge, 40 years ago, I struggled to find a reason to give a student a "D" who really should have received an "F" in a math course for high-school math teachers. After considerable work, I found a reason and gave him a "D." Unfortunately for him, the state required that he receive a "C" in the course to be able to continue teaching math in High School. He called me up one morning at my house and threatened to burn down my house when my wife and children were in it unless I pormised him on the spot that I would change his grade to a "C." (I did have the power to change grades after the course was over.) I told him that my conscience would not allow me to do that and he hung up. Fortunately, it was a empty threat. But, such threats are not always empty and I was really shook up after that telephone call.

Notice that if I had given him the "C," he would have been teaching in a math class. He would not have been teaching mathmatics, since he had such screwed-up ideas about what mathematics is all about, but, he would have been teaching something, and, much to the detriment of his students.

One of my dedicated colleagues in a similar situation did give the student a "C," and his own son ended up in that person's math class the next semester. That colleague (Professor Heron S. Collins, author of "Finite and Infinite Dimensional Linear Spaces") told that story many time to us younger teacher for the purpose of demonstrating how wrong it is to make that mistake.

All of my colleagues at the time had similar stories to tell. That is, the colleagues of mine who took their teaching seriously. There were those who never discussed their teaching so I have no way of knowing if they were serious about their teaching or not.

And, these stories were not all about high-school math teacher bummers, in fact, far from it. There are simply many dangers that lie ahead of anybody who desires to make a positive difference in this world.

DJ

 

[DeaconJohn]

... there are polynomials which take on positive values that are exactly the prime numbers.

Greathouse, I know that what you say is true, but, I think that I saw recently that even more spectacular results have been obtained in recent times.

Do you happen to know what they are?

For example, I thought I saw that there exists a polynomial whose image is exactly the set of prime numbers when the domain of the polynomial is restricted to positive integer values of its variable (or variables). Did I get that right?

[I.e., Does there exists a polynomial p and a natural number n such that

{prime numbers} = {p(x₁, ..., x_n) | (x₁, ..., x_n) is an element of Nⁿ} where N is the set of natural numbers, N = {1, 2, 3, ...}.]

 

[CRGreathouse]

He called me up one moring at my house and threatened to burn down my house when my wife and children were in it unless I pormised him on the spot that I would change his grade to a "C." (I did have the power to change grades after the course was over.)

Words fail me. I'm sorry to hear that you had to go through that.

That seems to be a strong argument that professors should not have the power to change grades after the end of the course.

For example, I thought I saw that there exists a polynomial whose image is exactly the set of prime numbers when the domain of the polynomial is restricted to positive integer values of its variable (or variables). Did I get that right?

[I.e., Does there exists a polynomial p and a natural number n such that

{prime numbers} = {p(x₁, ..., x_n) | (x₁, ..., x_n) is an element of Nⁿ} where N is the set of natural numbers, N = {1, 2, 3, ...}.]

I think I've heard of that; certainly it sounds plausible. Actually, I might be able to construct such a polynomial from the Diophantine equation I mentioned.

So the idea is that a variable p is prime exactly when a series of formulas $f_1,f_2,\ldots,f_k$ are identically 0 for some value of the other variables. So this is the same as finding a solution to
$$f_1^2+f_2^2+\cdots+f_k^2=0.$$

Call this quantity on the left A. If p is prime, there is some assignment with A = 0; if p is composite, A is at least 1. So let's take, say,
$$\frac{4A}{4A-1}$$
which for a satisfying assignment is 0/-1 = 0 but otherwise is in (1, 4/3]. So
$$1-\left\lfloor\frac{4A}{4A-1}\right\rfloor$$
can be 1 for prime p and is 0 otherwise. Then
$$(p-2)\left(1-\left\lfloor\frac{4A}{4A-1}\right\rfloor\right)$$
can be p-2 for prime p and is 0 otherwise. Then voila!
$$2+(p-2)\left(1-\left\lfloor\frac{4A}{4A-1}\right\rfloor\right)$$
can be p for prime p and is 2 otherwise.

Since there is at least one satisfying assignment for each prime p, this gives the polynomial you wanted.

 

[DeaconJohn]

Words fail me. I'm sorry to hear that you had to go through that.

Why, thank you Greathouse. I was pretty shook up. I actually felt better two years later when we moved to Rochester, New York. That was when I finally "put it behind me."

That seems to be a strong argument that professors should not have the power to change grades after the end of the course.

Thank you for the sympathetic response. However, it does seem to me that it is desirable for professors, instructors (I was an instructor at the time), and other teachers to have that power.

Too many times students are involved in unavoidable situations and it only makes sense to let the teachers "help out" - by letting them take the final exam the next semester - or whatever - if the teachers feel it is appropriate.

In addition, sometimes there is a real "mistake," like copying down one students grade for the grade of another student, that is not discovered right away and needs to be corrected.

And, there are so many other "dangers" or "unfortunate situations" that it seems "out of place" to plug up just one of them - and a relatively minor one at that.

I think I've heard of that; certainly it sounds plausible. Actually, I might be able to construct such a polynomial from the Diophantine equation I mentioned.

Thanks. Your construction looks good to me, though I am far from an expert in this area. Nevertheless, the techniques you use in your construction look very similar to the techniques I have read about in constructing such polynomials. That is also an indication that your construction is correct.

 

[CRGreathouse]

Thank you for the sympathetic response. However, it does seem to me that it is desirable for professors, instructors (I was an instructor at the time), and other teachers to have that power.

As a non-educator, I have no feelings about the value of letting instructors change grades late. But it seems very much like letting the bank manager open the vault: if everyone knows that he can do that, the manager and the manager's family is at risk for assault/kidnap/etc. Obviously the problem is less bad for educators, but the situations are similar.

Thanks. Your construction looks good to me, though I am far from an expert in this area. Nevertheless, the techniques you use in your construction look very similar to the techniques I have read about in constructing such polynomials. That is also an indication that your construction is correct.

Heh, just a bit of inspiration there.

 

[slider142]

For example, I thought I saw that there exists a polynomial whose image is exactly the set of prime numbers when the domain of the polynomial is restricted to positive integer values of its variable (or variables). Did I get that right?

[I.e., Does there exists a polynomial p and a natural number n such that

{prime numbers} = {p(x₁, ..., x_n) | (x₁, ..., x_n) is an element of Nⁿ} where N is the set of natural numbers, N = {1, 2, 3, ...}.]

You can use the Lagrange interpolation formula to get a polynomial of degree n that passes through n+1 specific points. Just input the first n+1 natural numbers and the first n+1 primes. :)

 

[DeaconJohn]

Slider142,

That's very true, Slider. Thank you for mentioning it. It's a little more difficult to get one that pass through all the primes. Give it a try! If you have any trouble, take a peak at the one Greathouse came up with! I think it's pretty neat.

Yours,

DJ

 

[CRGreathouse]

You can use the Lagrange interpolation formula to get a polynomial of degree n that passes through n+1 specific points. Just input the first n+1 natural numbers and the first n+1 primes. :)

Yes, but that only works for a finite collection of primes.