It's not just old books that make this claim. For example, in Bello et al., Topics in Contemporary Mathematics, 2007, the authors state
Of course, there are formulas for prime numbers; for example, there is Willans' formula from 1964: Let F(n) = [ cos2 π ((n-1)! + 1)/n ] where [ ... ] denotes the greatest integer function. Then for n ≥ 2, F(n) = 1 iff n is a prime.
Why this doesn't constitute a legitimate formula is anyone's guess, since it uses fairly standard and familiar functions from number theory. But then "formula" has no rigorous definition in mathematics and hence the claim about "no formula for the prime numbers" can't really be addressed until the definitions are made more precise.
Other books refine the claim, saying instead that there is no useful formula for the primes. Of course, the term "useful" is not defined, either. For example, David Wells writes in his 2011 book, Prime Numbers: The Most Mysterious Figures in Math
Well, how could one prove that "a formula is impossible" without giving a more rigorous definition? Yes, it's true that no nonconstant univariate polynomial can take only prime values, but is that really the only kind of formula one would allow? In that case, there is no formula for sine or cosine or exponentials, either!
Writers from the 18th century didn't know about Turing and computability theory, and modern computational complexity theory, so they have an excuse. More modern writers don't. If a "formula" for something means anything at all, it means that the something is computable and the prime numbers are certainly that. (Although I once had the strange obligation of convincing an author of popular math books that it was possible to write a program to compute prime numbers. This author initially denied it was possible, but after an exchange of three or four letters he finally agreed.)
And if a "useful formula" means anything at all, it means what Herb Wilf said it means: that the time to compute the nth object by your useful formula should be an asymptotically negligible fraction of the time to list all n of them. In that sense, also, there is a "useful formula" for the primes -- Lagarias, Miller and Odlyzko showed quite a while ago that the nth prime can be computed in about n½ time.
Can it be done in time polynomial in log n? Nobody knows. Now that's an interesting question. Let's use the language of modern complexity theory to address the really interesting questions about primes and computation, and finally put to rest the silly and embarrassing "no formula for the prime numbers" claim.
59 comments:
You might be interested in my Formula Compiler webpage: http://www.xamuel.com/formula.php It has a textbox where the user can write an arbitrary program (in a BASIC-like language) and then upon pressing a button instantly be given a (ridiculously useless but 100% machine-generated) formula for the function they programmed, using nothing but the basic arithmetic operators and finite summation.
You seemed to use "formula for prime numbers" and "forumla for THE prime numbers" without drawing attention to the difference. But mostly, I think when most people envision P(n), they expect it to produce primes for which π(P(n)) is human-scale-large (i.e. the trillionth prime or so), within a few minutes of execution time on a PC (or server) of the day. Wolfram Alpha seems to sort of do this, but the larger results are presented with only six digits of precision, so you're not actually getting a prime number result, but a set of numbers, of which at least one is prime. It could be operator error, I admit.
There is a Wikipedia article, "Formula for primes". I have no idea how reliable it is.
TomS
You seemed to use "formula for prime numbers" and "forumla for THE prime numbers" without drawing attention to the difference.
And what does the distinction mean to you?
The problem is that there is no formula giving you the distribution of prime numbers - you do not know (for large numbers) when a prime number shows up or how they are distributed. For example, while it is possible to find a large prime using a formula, you usually won't know which number will be the next prime or the one before or whether there might be some prime between two primes without directly checking. As prime numbers and their distribution play a very important for the structure of number spaces, this is unsatisfying from a mathematical point of few.
The problem is that there is no formula giving you the distribution of prime numbers
Sure there is - it's called the prime number theorem. And there are lots of papers on the distribution of primes in small intervals.
you usually won't know which number will be the next prime or the one before or whether there might be some prime between two primes without directly checking
"Directly checking" is vague prattle, not a term with a generally-accepted strict mathematical definition. You could just as well say you can't know whether there is a squarefree number between two given squarefree numbers "without directly checking".
structure of number spaces
What the heck is a "number space"?
Jones polynomial, Mill's constant, prime progressions relative to class numbers..
[I was going to send an email but this seems quicker.] Regarding integer factorization (dependent upon primes) within Z, the algorithms I have developed work but always resolve to a decision/search process [a P vs NP dilemma]..not provably deterministic. I am of the opinion that in order for a 'closed form' (see a paper on this qualitative term) prime representation to exist, it must be composed of logarithmic and circular functions and must involve complex integration..akin to Rademacher's `formulation` ..exclusive of Riemann's development (and that of one smart Iranian fellow's also).
Jones polynomial, Mill's constant, prime progressions relative to class numbers..
It makes no sense at all to refer to these unrelated topics as "number spaces".
I believe I am anonymous 2 (pun). I cannot speak for Mr.number spaces.
J.P.Jones (1976)..and not the knot polynomial, Mills Constant,Caldwell & Cheng (2005) and arithmetic prime progessions relative to complex quadratic fields with class number 1..for example. I read somewhere that J.H.Conway proposed that -1 be considered a prime number but I have not been able to source the original statement. (I would be interested in the proof/justification.) Regarding the algorithm, it's a work in progress.. and seems to be predicated upon sequenced primes. There seems to be one algebraic structure that does develop sequenced, provable primes (and Euler was there first) which I am reworking.
From #2, sourced from Mersenne Forum,
"We have confirmed the primality of the Leyland numbers 3110^{63}+63^{3110} (5596 digits) and 8656^{2929}+2929^{8656} (30008 digits) by an implementation of a version of Mihailescu's CIDE. (JFranke et al)"
Admirable as this is, I would expect there exists an alternative to this form of computation..Zeilberger's methodology perhaps?
Willan's Formula is a means of detecting primes, from your description. Is there a formula that produces primes? That is, some function P(x) where P(1) = 2, P(2) = 3, P(3) = 5, P(4) = 7, P(5) = 11, P(6) = 13, etc., that lists either exclusively prime numbers? The images you offer seem, to me, to be referring to the latter, not the former.
One Brow:
I guess you didn't understand much of what I wrote. Yes, there is a function P(x) like you describe. Here it is: P(x) = the x'th prime. Voila.
From Anon2:
Godel's numbering and the results of Shannon (amongst (many) others) are fundamental to the concept of primality. Regarding one aspect of your blog, based on the prior sentence, you can assess the provability of religious/creationist/crankish statements and decide how much you wish to tune them in or out. (Your site-meter analytics may be of assistance here.)
Godel 's numbering is not "fundamental to the concept of primality"; it's the other way around.
Shannon's informationtheory has nothing to do with primality.
A prime number is a form of information and can be defined in terms of rate/capacity/channel relative to a counting system. All forms of number comprise this channel..transcendentals, surreals etc...Within this channel the rate of transmission of primes decrease replaced by another numeric form, say composites - assuming a conservation law where all numeric forms have been categorized. Godel's result is more fundamental than primality, the counting system is simply the device used to prove unprovability within a consistent logic.
An extended 'numeric' conservation law would include all self-consistent mutually exclusive logical constructs which must in some way be countable. Combining all such constructs within a single 'numeric channel' implies its capacity is calculable but unknown [ie. new types of numbers may be discovered occupying a specific 'number space `(lol)]. Thus, the measure of countability involves geometry and combinatorics [spaces,occupancy]. A quantum wave-function includes these ingredients and is directly measurable.
Could you please justify your statements succinctly? Sorry for being so wordy.
Any number is a "form of information" and prime numbers are nothing special in that regard.
I should not have made that prior post for several reasons. Unless I can concisely state a point of fact or theory then I shouldn't spout ..the wave function statement was way off base.
Regarding the paper of Brunier and Ono (Algebraic formulas ..), there is much I don't adequately understand there but I do recognize certain associations. Do you think that some of the methods in that paper apply to the theory of the distribution of the prime numbers directly or would the result of the paper be more important [as applied to the same distribution question]?
Do you think that some of the methods in that paper apply to the theory of the distribution of the prime numbers
No.
I have different opinion.
The use of Fourier expansions within the paper as well as Algebraic numbers can be used to describe aspects of the prime number distribution. The Fourier association is integral (pun intended) to the development of the distribution itself. Algebraic numbers can be calculated via the theory of binary quadratic forms which also allows for the classification of certain prime number forms relative to specific residue classes. In my opinion, both the distribution of the prime numbers and the description of partitions are related simply due to the similar concepts that can be used to describe each.
The paper could have noted connections to the diophantine Frobenius problem as well as delving deeper into the generalization of partitions into
quantitative entities other than integers. Black body radiation is
essentially a partition distribution.
Am I mistaken?
Anon 2, re Conway's suggestion that -1 be considered a prime number, here's what he says on the subject in the preface to his book "The Sensual (Quadratic) Form":
This reminds me of the fact that some people always smile indulgently when I mention "the prime -1", and continue to use what they presume to be the grown-up name "oo". But consider:
Every nonzero rational number is uniquely a product of powers of prime numbers p. For distinct odd primes the Legendre symbols (p/q) and (q/p) differ just when p=q=-1 (mod 4). There is an invariant called the p-signature whose definition involves summing p-parts of numbers. If there are p-adically integral root vectors of norms k and kp, then p is in the spinor kernel.
Each of these statements includes the case p=-1, but none of them is even meaningful when se use the silly name "oo". In the future, I shall smile indulgently back!
(I have mangled this typographically in order to use only things that I know will work in a Blogger comment box. "oo" of course denotes an infinity symbol.)
Thank you 'G.' I believe the reference I came upon was a little more explicit and may have been within "The Book of Numbers." In any case here is a link to a more direct statement, "http://mathforum.org/kb/message.jspa?messageID=1093178"
My reason for stating that point was because I have encountered something similar. Mathematical definitions may arise due to convenience or logical necessity. Within my studies it exists as a condition of consistency.
For Dr. Shallit, in keeping with this thread, I have made an empirical observation (not yet proven) of a necessary & sufficient condition for primality.
- if a number factors trivially within `this` domain then it's prime. (Domain admits exclusively non-trivial integer factors..if a trivial factorization exists anywhere in this domain then it must be non-trivial hence prime.)
Regarding the `open problems` thread, if I or anyone resolve a problem would this qualify as successfully passing a challenge exam thereby obtaining credit for the course?
[As an aside, I hope your one student succeeds in his endeavor.]
"(and that of one smart Iranian fellow's also). "
The fellow's name is Ahmad Sabihi.
-just tying up a loose end.
ommm I have a question about what u guys were talking about when it say FORMULA FOR TEH PRIMES does it mean a way to work out their disterbution and how many can exsist in a given limit like from 1-100 how many primes.LIke that is that what has not be proved cause if what I understand from the article There are formulas to find the primes but there ISN"T A WAY/FORMULA TO FIND THEIRE DISTBUTION AND THE AMOUNT THAT IS IN A GIVEN LENGHT OF X????? Plz answer
Yes, there are certainly formulas to determine the exact number of primes p in an interval x ≤ p ≤ y. For example, Lagarias-Miller-Odlyzko gave an algorithm to compute π(x), the number of primes ≤ x, and then
the number of primes in the interval [x,y] is just π(y) - π(x-1).
As for "distribution", you'll have to be more precise about exactly what you mean.
ok so yes by detrbition I mean by is there a way to find that a prime number is really a prime number like to work out the next prime in the pattern is that still explained of how such prove can be given to create such formula? if they still haven;t done it I will continue my research and find a formula........ I am just a bit confused here is there acutally anyting left about the primes that need explaining or need formula a for>?
http://www.towntopics.com/wordpress/2013/04/17/institute-professor-wins-1-million-math-prize/ also can u help me understand this so this article says that the remainnn hypothis is sloved ?
Yes, there is an algorithm to check if any given number is prime (trial division up to the square root, for example), and there is even an efficient (polynomial-time) algorithm.
There are many unsolved questions about the primes, such as
- are there infinitely many twin primes?
- are there infinitely many Mersenne primes?
No, the Riemann hypothesis has not yet been proved. Deligne won a prize for old work on the Weil conjectures, which are about finite fields.
thank you sir you have been great help for me I now know what I must do.So I just got a bit more I would like to ask this is about the renaiamnn hyphtoisis tho and other stuff involing equations of their problems so about the renaimmn hypthosis I have had money reads on the net to find a good explantion and all I got from is it about the thr remina zeta function and something about notrival zeros and yea not sure what that is about but I found a vid on youtube it says that the question is that from the vid there were waves and as the waves moved they all seems to line at the same line at stralingt line point x I send u the link herehttp://www.youtube.com/watch?v=zfoVTY9OnA4&list=FLwD9kJat8VRkxqAdh3OX2HQ sorry for the bad English there I am not good at English and thank you for your help again sir you been big help to me to put me on the right track can I still ask you question :P not related to prime numbers on this page :D? or is there a place you have I can do so?
I can only suggest you take a number theory course at your local university. I can't understand anything you are saying.
:) ok sir can I take any of those cources online?
Anonymous 3 (or is it 4?)
I understand yours and Hilf's view that a meaningful understanding of a "useful formula" could be about computation time. But what a about structural formulas like of the type pn = f(p1, p2, ....., pn-1)?
Wouldn't such formula have some analyzing meanings?
Wouldn't such formula have some analyzing meanings?
Very doubtful.
what is this about the
are there infinitely many twin primes?
it seems only logical that there are
please explain more
Matty: I don't know what kind of explanation you would want. The fact is that no one has a proof yet. There are thousands of probably-true statements in mathematics for which no one currently has a proof.
ohk but couldn't they just look at all the prime numbers and see if there are a infinite amount of twin primes? wouldn't that prove it. Or does it have to be done with a equation
Matty: what do you mean "look at all the prime numbers"? How can you "look at" infinitely many things?
Before continuing I think you should read some very basic material about number theory. I recommend starting with Beiler's "Recreations in the Theory of Numbers". After that you can go on to something like Hardy and Wright.
wil I get a prize if I prove that there are a infinvte amount of twin primes?
wil I get a prize if I prove that there are a infinvte amount of twin primes?
No prize that I know of, but you would certainly be famous.
Without trying to be too discouraging, the chances that an untrained amateur can make progress on these kinds of extremely difficult questions is essentially zero.
:( but the question seems so simple how complicated can it be?
ok I shall be back in a week with the answer maybe or in 2 weeks just making sure that what I am trying to prove is what I think it is i will ask a few questions about the uncertently I have about the problem.
So all I have to do is to prove there are a infinvite amount of primes E.g 7-9 11-13 like that? and they have to have a diffence of 2.so simply I just have to prove that there are always be twin primes no matter how big the numbers get in the primes.IF I have the meaning of what I have to do right, tell me or if I have anymistakes please list
ok http://primes.utm.edu/lists/small/100ktwins.txt
the website shows the twin primes up to 100k but I don't get it
I know 3,5 differ by 2 but what about 11 and 17 and all of the others? I don't get it
wait no sorry I got it now I can prove this !!!! or not,..ok I will report about in about 1.5 weeks or 3
I guess what people mean when they say that there is no formula for primes is that no one has found a bijection from the natural numbers to the prime numbers, but I guess they are using the word formula incorrectly.
I guess what people mean when they say that there is no formula for primes is that no one has found a bijection from the natural numbers to the prime numbers
No, this is incorrect. Not only is there a bijection, given by n associated with π(n), the n'th prime, but this bijection is also computable.
Ok :P I might need some more time on this it's a bit hard
Wait the given idea I have now to prove the twin prime conjecture is a bit hard for me to compute with all the numbers am I aloud to prove it by givening a statement or does that than also become a conjecture as a prove in words but the T.P.C is still needed a full mathematical proof for it?
Matty: sorry, I am unable to understand what you are trying to say.
Really, you need to walk before you can run. I suggest reading a good book on elementary number theory, such as Hardy and Wright. There you will learn the basic techniques, as well as what a proof is.
I mean can I just say what you have to do to proof it?Or do they only accept a proof with numbers?
cause right now I have already got a proof for it and it is written with some a bit of proof of it and some words no equations or anyting well a bit but yea.Sorry for the inconvience but I have a limited amount of information in my reach so yea I can really get a book about that also I have English diablities I suck at English.
can I just say what you have to do to proof it?Or do they only accept a proof with numbers?
Again, I don't know what you mean. For a mathematician, a proof is a logical argument that goes from the hypotheses to the conclusion by a series of logical steps. I don't know what "a proof with numbers" means.
cause right now I have already got a proof for it
No, you don't.
As I said before, if you don't know what a proof is, and you have no experience writing up proofs, then there is no chance at all you could have solved such a celebrated and difficult problem in a few days.
hey I really think I got the prove for it it isn't much of a good written proof but I will try to explain it to my teacher see what he think.or is there a place I can submit my work plz reply
Matty: as I said, let's be realistic. There is simply no chance in hell that you've solved this difficult problem. So no, I definitely do not suggest you submit it to a journal.
You need to take some basic courses in number theory before you can even begin to work on it. And if you don't know what a proof is, how can you say that you have proved it?
More humility, more study is needed.
But really i can't get those coruses i am 14 the library but only calculas books.te proof i have right now makes perfect sence i will show my teacher torrmow see what he says
wait this twin prime conjecture is like fermates last therome where it seems so easy but than a lot of work is needed to prove it ?
Yes, I understand that you are a young person; it is clear from the way you write.
Any good bookstore or library will have books on number theory. I already suggested a couple to you.
Nobody has a proof of the twin prime conjecture yet, so nobody can say for sure how easy or hard the proof will be. But if thousands of mathematicians have worked on it for hundreds of years, of course the very strong likelihood is that the proof will be very very difficult; otherwise someone would have already found the proof.
Ok cause i am failing to find a really good explation of really what the twin prime conjecture is can u please explain to me?
The twin prime conjecture is:
There are infinitely many prime numbers p such that p+2 is also prime.
So the conjecture just says that there will be a infintei amount of twin primes.And a prove is needed ?
Is that what It is all about?
Yes. At this point my ability to help you understand the problem is exhausted. No more comments from you will be posted.
Nice blog entry! I've made it my recommended web link from Theorem of the Day no. 211: Willans' Formula
Post a Comment