Talk:Prime number

From Wikipedia, the free encyclopedia

You have new messages (last change).
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics.
Mathematics grading: B Class Top Importance  Field: Number theory
A vital article
History is too short. Advanced material on generalisations needs to be moved from lead.Tompw 14:30, 7 October 2006 (UTC)
Prime number was a good article candidate, but did not meet the good article criteria at the time. Once the objections listed below are addressed, the article can be renominated. You may also seek a review of the decision if you feel there was a mistake.

Date of review: 19 September 2006

Some page format added. Charles Matthews 07:49, 4 May 2004 (UTC)

Contents

[edit] Formula for yielding primes

On the Prime number page it gives the formula f(n) = n^2 − n + 41 but on the link to the "formulas for primes" page it gives the formula as f(n) = n^2 + n + 41. I don't care to confirm which one is the correct one, or if they both are. Just pointing it out for someone else.

Both are correct and both are cited by sources. If f(n) = n^2 − n + 41 and g(n) = n^2 + n + 41, then f(n) = g(n-1), so the only difference is a change by 1 in the n values which give primes. PrimeHunter 14:07, 23 February 2007 (UTC)

[edit] Initial segment of primes

Links: http://www.utm.edu/research/primes/

The first 750,000 primes: http://www.geocities.com:80/ResearchTriangle/Thinktank/2434/prime/primenumbers.html

Now here's an interesting question which may even provide a valid use for subpages.

Would adding a list of all the prime numbers known to mankind be counter-productive to the idea of the Wikipedia? It is "a compendium of human knowledge", regardless of how obscure and arcane.

(I suppose one could extend this to listing Pi to a quadrillion digits, to be somewhat hyperbolic.)

Thoughts? --Colin dellow

I'd say that the encyclopedia should be a compendium of all useful knowledge. Digit number 323454 of Pi and the temperature at noon on May 7, 1976 in Salt Lake City are part of human knowledge, but really, nobody has a use for this information except maybe some highly specialized experts, who know where to look it up.

I perhaps didn't make my point clear. Wikipedia presents the ability to have "useless" trivia because of the Wikipedia is not paper argument.

Perhaps it will be useful only to a specialised group, but does it hurt to have it? It would increase the amount of information available in the Wikipedia. (I found the comment about temperature

s

in Salt Lake City at a

given year to be somewhat unrelated to this question, BTW.) --Colin dellow

Actually, I don't think it would be possible to list all the known primes. There are just too darn many of them, and it's too easy to find more. - Hank Ramsey

I don't think it would be a waste of space to have a separate article that lists say, all the primes less than 10,000. This is actually very little raw data, but having available the primes in this range is very useful to many people, especially for testing conjectures, making conjectures, playing around with numbers, etc. The information would NOT just be trivial as in the temperature of Salt Lake City at a certain time. Also, I think it would be very useful if there were an article that listed the complete prime factorisations of all integers less than 10,000. Again, this is not trivial information, it's very important if someone wants to quickly test whether or not a conjecture may or may not be true.

Agreed --Haggis 14:39, 24 Feb 2005 (UTC)

But don't forget, that there exist prime-tables (2-100.000, 100.001-200.000, ... ) in wikisource. --Arbol01 02:19, 25 Feb 2005 (UTC)


correcting Wikipedia entry of Euclid's Infinitude of Primes proof

Fixed font - Proportional font


Archimedes Plutonium Apr 14, 10:17 am show options Newsgroups: sci.math, sci.logic, sci.edu From: Archimedes Plutonium <a_pluton...@iw.net> - Find messages by this author Date: Thu, 14 Apr 2005 12:17:05 -0500 Local: Thurs,Apr 14 2005 10:17 am Subject: correcting Wikipedia entry of Euclid's Infinitude of Primes proof Reply | Reply to Author | Forward | Print | Individual Message | Show original | Report Abuse

Thu, 14 Apr 2005 12:23:29 -0000 SunCode wrote:

> > Yes, thanks, I will execute on your suggestion.

> Yes! do so, but please read this page first =)

> http://en.wikipedia.org/wiki/Wikipedia:No_original_research

> SunCode.

Correcting Euclid's Infinitude of Primes (IP) proof is not original research, especially in light of the fact that out of 31 authors of a publicly written IP proof only 3 of them gave a valid rendition, and the others which includes MathWorld and Wikipedia gave a flawed and invalid IP proof. So that hardly counts as original research in the fact that 3 authors of the past of Flath, Landau, and Stillwell managed to give a valid IP proof in a textbook and that it was the misfortune of MathWorld and Wikipedia to have chosen the other 28 authors who rendered a invalid and error filled rendition. If Wikipedia had copied Stillwell's rendition plus adding a line saying that Euclid gave a Direct Method Proof of increasing set cardinality then Wikipedia would not be on the list of flawed and invalid proofs.

So this is not original research but the correction of flawed and invalid past thinking and understanding.

I have not pinpointed as to where in the history of mathematics that this stain and tarnish on Euclid's IP started. I have a educated guess that it was Gauss himself who started the flaw because Gauss used Reductio Ad Absurdum so much in his own work of Number Theory that later mathematicians would fall into the trap of thinking that Euclid's IP was Reductio Ad Absurdum (the Indirect Method).

So thanks to SunCode, I am still going to apply to Wikipedia today to start the motion for them to change their entry on Euclid's Infinitude of Primes proof. If Wikipedia had a webpage where they claim that the addition of 2 plus 2 comes out to be equal to 3, then that should not be called original research when someone trys to correct them by pointing out it is equal to 4.

Thanks SunCode, and I think I will apply for a brevity Euclid's Infinitude of Primes proof considering that full details can always be referred to my website of File 106 in www.iw.net/~a_plutonium

Correction to Wikipedia website of Euclid's Infinitude of Primes Proof:

Euclid, from his own language of "prime numbers are more than any assigned multitude" gave a Direct Proof Method for Infinitude of Primes. This method is one of increasing the set cardinality of any given finite set of primes which by logic then generalizes to an infinite set. Many mathematicians in the 19th and 20th century erroneously thought that Euclid gave a Indirect Proof Method which caused them to render an invalid proof attempt by searching for a prime-factor.

Direct Proof of IP: Given any finite collection of primes 2,3,...,pn possessing a cardinality n We find another prime by considering P!+1 = (2x3x...xpn) +1 Either P!+1 itself is a prime or else it has a prime factor not equal with any of the primes on the finite list. Thus the cardinality of every finite set can be increased. And since all/any finite cardinality set can be increased by 1 more prime therefore the set of primes is an infinite set.

Euclid's IP was not Indirect or Reductio Ad Absurdum but I give it here anyway to show for instruction sake:

Proof: The prime numbers are the numbers 2,3,...,pn,... of set P Suppose finite, then 2,3,...,pn is the complete set of primes. Form P!+1 = (2x3x,...,xpn) + 1 Now P!+1 is necessarily a new prime because all the primes that exist leave a remainder of 1 when divided into P!+1 and so by the very definition of what it means to be prime this new number of P!+1 in this restricted space of primes is necessarily a new prime not on the original list. Contradiction, hence set of primes is infinite.

Euclid never used the Indirect Method to prove his Infinitude of Primes. Somewhere around the time of Gauss was the erroneous claim that Euclid used the Reductio Ad Absurdum for IP. Worse yet was the mixing up of methods of making a prime factor search in the Indirect Method when P!+1 once formed is automatically the new prime.

So I have corrected two items in Euclid's Infinitude of Primes proof. One item is the history of the proof is Direct and not Indirect method. The second item is that in a Indirect proof of IP there cannot be a prime-factor search because the definition of prime forces the new number P!+1 to be automatically the new prime given that restricted space of primes.

Copy send to Wikipedia editors.

Please note I can make the correction as brief as possible to one short paragraph.

Archimedes Plutonium www.iw.net/~a_plutonium whole entire Universe is just one big atom where dots of the electron-dot-cloud are galaxies

Archimedes Plutonium has been posting much to sci.math under the bizarre impression that Euclid's proof is somehow imprecise, too verbose, or incorrect. It is none of these things, and his strange explanation of how Euclid did not use a simple (in fact, seen by most as the protypical) reductio ad absurdum proof is merely clutter. Incorrect clutter. This is the first time I've edited a wikipedia page; I am going to attempt a revert. Tez 08:40, 15 Apr 2005 (UTC)
Of course, Archimedes Plutonium is correct and Euclid is wrong. Euclid's proof is formally incorrect because it actually states that given any three primes, one can find a fourth not on the list. Sometimes, I wonder if anyone has actually read Euclid's actual proof, which is widely available in English. -ilan
I have read Euclid's actual proof, in English transaltion, and I thought that it was clear that Euclid meant to imply the general case as an obvious extrapolation from the case of one and then three primes. He didn't explicitly say anything like "extending this argument to the general case proves the theorem," but I believe that was what he was thinking, and that he considered it too obvious to put in. Certainly it is implausible to suggest he meant nothing of this kind, and that he made an error of logic, since the proof is so obviously defective without it; Euclid was not so foolish as that. -- Dominus 19:20, 25 May 2005 (UTC)
Well, considering how much anger and frustration is observed in professors grading students who only did 3 steps in a mathematical induction proof, it is ironic to see that this was the exact method used by Euclid and Archimedes. I guess they would have miserably failed finite mathematics courses. The final irony is Doron Zeilberger's observation that doing 3 steps in an induction is actually a formally correct proof for the formulas for the sum of the first n positive integers. -ilan

[edit] Infinitude of primes

Note regarding the proof of the infinitude of primes: we use the fact that every composite number has a prime factor. I think that requires proof in itself.

Yes, perhaps, if it isn't obvious. It is clear that if a given number has a composite divisor, then the divisors of that divisor are also divisors of the original number (if A=B*C and C=D*E then A=B*D*E). If any of these divisors are composite, we can apply this principle recursively to find more divisors of the original number. We cannot recurse indefinitely because the number cannot have an infinite number of divisors. So eventually we must reach a point where all the new divisors are prime. QED

Re: every composite number has a prime factor; this is a direct corollary of the fundamental theorem of arithmetic. Done.

sub page or article on infamous research project "A Short List of Even Primes" which is of course, mainly acknowledgements and academic scaffolding, followed by the list, viz. 2

I wouldn't mind a link to a joke if it's clearly labeled as such. For that matter, I wouldn't mind adding the old "proof" that all primes are odd. -LC

The article says:

There are infinitely many prime numbers. The oldest known proof for this statement dates back to the Greek mathematician Euclid. It is also one of the oldest known proofs by contradiction.

I thought that Euclid stated the theorem as "Given any prime, there is a larger prime." With the theorem stated like this, the proof isn't a proof by contradiction -- the existence of the larger prime is shown directly. Can someone confirm this, or am I misremembering? --Zundark, 2001 Oct 11

I think you're right; I'll take the contradiction bit out. --AxelBoldt

I see someone has put it back in again. I will remove it (or reword it) if no one can provide a justification for it. --Zundark 15:09 Apr 3, 2003 (UTC)

Yes, I believe it IS a proof by contradiction. We wish to show there exist infinitely many primes. So, suppose not; suppose there only exist finitely many primes. Then certainly there exists a _largest_ prime since there are only finitely many. But given this largest prime, I can show that there must exist another prime larger than the largest prime. This is a contradiction. Hence, there must be an infinite number of primes.

It's not a question of what we wish to show, but of what Euclid actually showed. There is an English translation here. Euclid claims that there are more than any given finite number of primes, and proves this directly by taking a finite number of primes, and showing that there is another. To read this as a proof by contradiction that there are an infinite number of primes is to add a modern gloss that does not exist in the original.
If you read the above-mentioned translation you will see that Euclid's proof - like many of his other proofs - does involve a proof by contradiction: he proves by contradiction that G is not a member of the finite set of primes. But our article is wrong to claim that Euclid's proof of the theorem as a whole is a reductio ad absurdum. I will maybe try to rewrite that part of the article later today. --Zundark 11:19, 13 Oct 2003 (UTC)
It seems to me, at least from the translation linked above, that the theorem certainly does involve proof by contradition. It says, in part:
"I say that G is not the same with any of the numbers A, B, and C. If possible, let it be so. ... Therefore G, being a number, measures the remainder, the unit DF, which is absurd. Therefore G is not the same with any one of the numbers A, B, and C."
Euclid assumes that G (previously constructed as a prime factor of ABC+1) is identical with one of A, B, or C, derives a contradiction, and concludes the oppoisite, that G is distinct from A, B, and C. I don't know how free the translation is, but to assert that the proof is not an example of reductio ad absurdum in the face of the phrase "which is absurd" is rather absurd. -- Dominus 19:33, 25 May 2005 (UTC)
There is a difference between "involves a reductio ad absurdum" (which the proof certainly does, as I already pointed out above some 19 months ago) and "is a reductio ad absurdum" (which the proof isn't). --Zundark 20:38, 25 May 2005 (UTC)
Well, the distinction is lost on me personally, in the present case, then. Can you elaborate?? Revolver 05:28, 26 May 2005 (UTC)
The translation linked above is an eleven-paragraph proof, of which two-and-a-bit paragraphs near the end are a proof by reductio ad absurdum that G is not equal to A, B or C. You could even remove this reductio ad absurdum part and the proof as a whole would still make sense, so I don't see how the proof as a whole can possibly be considered as a reductio ad absurdum. --Zundark 08:20, 26 May 2005 (UTC)
I see. I was thinking again that it started "Thm: There are an infinite number of primes. Pf: Suppose not, then...", again forgetting this isn't how it's stated. Revolver 08:51, 26 May 2005 (UTC)

It seems that the source of confusion or differing interpretations is coming from different ways of translating Euclid's statement into logical statements involving quantifiers. The modern definition of an infinite set is usually taken to be the following (if not, then it is easily shown to be equivalent to the definition):

A set S is infinite if it cannot be put in 1-1 correspondence with a natural number or the empty set (if 0 is not considered a natural number).

This is a definition by negation. An infinite is defined to be one that is not finite. So, to prove by definition that a set is infinite, one can do the following:

Suppose for sake of contradiction that S CAN be put in 1-1 correspondence with a natural number or 0. Then....<contradiction is achieved>. Thus, S is infinite.

The way of expressing this definition in terms of logical quantifiers would be

~ (exists A)(P(A))

where ~ is negation and P(A) a statement involving A.

By modern rules of logic (at least, most logical systems, and certainly the one most working math people use), this is logically equivalent to

(for all A)(~ (P(A)))

This is the form of the theorem as stated by Euclid. He gave a direct proof of the positive assertion that for all A, ~ P(A) is true. What is happening is we come along, almost subconsciously without thinking, identify this statement with the logically equivalent form given above, and then realize that by the definition of infinite set, this is really a proof that the set of primes is infinite.

Now, how this should all be interpreted and presented, I don't have all the answers, maybe a short disclaimer explaining what I've mentioned above is in order. At any rate, it's open for discussion.

[edit] Types of primes

I took this out for now:

multifactorial, compositorial or binomial primes

since the terms are not defined. I couldn't understand the examples

Multifactorial prime is for example 43328! · 7 - 1, compositorial prime 8711!/ ∏(8711) - 1 and binomial prime 104087!/(52043! ± 52044!) + 1.

And in this paragraph

and can have many other properties in collecting of different terms or can be derived from some well known sequences as for example as the primitive part U(n) of the nth term in the Fibonacci sequence e.g. U(40295) or as V(n) in the Lucas sequence e.g. V(25504) and many more.

what is the "primitive part" of the nth term in the Fibonacci sequence? AxelBoldt

Yes, Axel I'll soon make those definitions more clear. And on the other hand if you understand the first two definitions (primorial and factorial prime) you should understand the next three ones, because they are just futher extendings of the first two ones. These short contributions stole me some 3 to 4 hours of intense work just to get them together and one can easily put them out in a minute. The topic of pure and just pure primes is for me at a highest interestings. I think Axel you're looking for too much "usefull" and wonderful definitions, theorems, proofs and such inhere. Math is not just that. The good example for this is for instance (a pure mathematician) Keith Devlin with his piercing work for better understanding of the whole past, present and future math or I can say this for our mathematician France Križanič who wrote some nice Devlinlike books - and he is still writting them. For example integral in a complex is not for a high school, but he had put it in his huge textbook for secondary schools. He put there some beautifull work of theoretical astronomer Möbius as well. I can talk on and on - but I am afraid someone would say in Marley's manner I've got so much things to say, ha, ha. XJam keep on moving and try putting some more stones in math knowledge on this icy road. For the term "primitive part" I need more Time because nobody told me about, hey ho. (Back to work XJ again, - come together and make it work, whoahh, we got five days to go, working for the next day, hey hey, now ... [Bob Marley, Work, live at final tour in Berlin 1980 ]). And I have enough Time because I really do not want to steal anything from Nature. I do believe that Fibonacci never dreamed that someday someone would talk some more about his "obscure" sequence found everywhere in a Nature itself. That goes for Lucas (and many, many others) too. I hope I'll achieve at least fair level of Axel's rigorousness soon.

Another thing (I'll say this as fast as I can :-) ) as of the first above external link someone put in this talk. I'll generate with that list an Ulam-(Möbius) cloth and I'll post a picture of it in Wikipedia's digital archives as soon as possible. We can then Distiquence Arithmeticaenniolus (this is a weird Gausslike verb) some more, if ya agree. This list is for me very Hardylike "usefull" for me, because I have no current working algorithm to produce it. But if someone had already made an Ulam cloth of primes, please let me (us) know.
XJam [2002.03.23] 6 Saturday (0) - the 3rd day of spring 2002. Natty Dread 20000 miles away from home.

[edit] Largest known primes

This sentence appears under the heading 'Largest known prime': "This result with purely PC based computer with < 1GHz Pentium processor beat some previous prime-runners as supercomputer Cray T94 was." I can't be certain as to the meaning of this sentence, making it rather difficult to fix. Anyone?

Yes Ostrich as it is evident from your user profile page you're already in computer's world so you should understand that (almost simple) computer's net fight of David against giant Goliath. I would not refuse one such model T94 if it would by a New Year's Day's present but anyway. You should check at fist GIMPS term to see how a small or a huge connected computers via the net can work very efficiently together. We can say that Wikipedia works in the same way. There are many examples (I know not all of them) of such work: Odlyzko's mathematical work with te Riele on Mertens conjecture (see for the current wikipedia status of this at http://www.wikipedia.com/wiki/Talk:Moebius_function, SETI@home, ISDN-ODETTE conection of European automobile industry and many more) It is good to know Odlyzko and te Riele used for the job one of the "first" models of Crays - a model 1 (It sounds just like a fomous Ford's model T1). And probybly Odlyzko had decided to make some of his outstanding calculations on such dispersed "systems". He wrote some article on this subject too. As you like fractals can you give me any help on my previous instance about Ulam's cloth of primes? And actually it was exactly 500 MHz Pentium based PC to gain that recorld on the biggest (Mersenne) prime up to date. I hope this will kill the curiosity in cat. Greets to Ox from Ce. --XJam [2002.03.23] 6 Saturday (1st ed)
Sorry folks - above - I was talking nonsenses about Ulam's cloth. Ulam's prime spiral is as it is. I have already put its representation on wikipeda (see mobius function) so I don't have to make it again but anyway I do believe that mentioned list of primes is very important for everyone who wants to deal with primes. --XJam [2002.03.24] 0 Sunday (0)

Someone should update this section . . . . The 42 Mersenne prime has now been found (February 2005).

[edit] Gaps between primes

I moved the following material here for now:

For example the gap bettween 1693182318746351 and 1693182318746371 is g = 1693182318746351 - 1693182318746371 - 1 = 19, but the next consecutive gap g64 is 1131. This kind of gap is called maximal prime gap with property of occurences of gaps of at least of this length following initiating prime p and is the largest known maximal prime gap, found by T. Nicely and B. Nyman in 1999.
Jose Luis Gomez Pardo in 2001 found the largest first known occurence prime gap greater than 1131, which is 21611, following the initiating and certified prime 10999 + 24196831 but with its consecutive prime to be probabilistic, that is, proven to be statistically prime (with a probability extremely close to 1), using, for example, Miller-Rabin test with multiple bases or some other primality test. There are of course many prime gaps with sizes from 1131 to 21612 but 1131 is the maximal one. This will probably change soon. Cramér showed that if the Riemann hypothesis holds, it would be:
      g < k √p log p .

Specifically, I have the following questions: what exactly is a maximal prime gap. I do not understand the example and explanation given above.

Second, it seems that Pardo did not infact find the largest gap, but just a probable gap, is that correct?

Third, if there are many gaps with sizes between 1131 and 21612, how can 1131 be the maximal one? AxelBoldt

[edit] Primorials

The largest known Primoral seems to be outdated; [1] mentions 392113#+1

Let me say these things:

//-1 Yes, strictly speaking primorial primes are not special case of factorial ones. Generating a 'prime product' for n as ∏(n) goes in 'a same manner' as a function n! = 1 · 2 · 3 · 4 · 5 · 6 · ..., but we have to 'check' first its argumets for primality what is a bit harder than adding a number by 1. Thus 1 · 2 · 3 · 5 · 7 · 11 · ... is easy just for first numbers of n. Try to get ∏(1234567890) by hand. I don't believe that even Gauss would solve in one hour ∏(100) as he did Σ(100). Another strictly mathematical question would be which primorial primes are members of factorial prime set or vice verse as for arbitrary n is n!>∏(n). (Is this proven?) Are there any? I've found trivial 3!± 1 = ∏(3) ± 1 = {7,5}, but here Nash's logic already ends...

Primorial primes can never be factorial except in the two cases you list. The reason is that all factorials beyond 3! are divisible by four, but products of different primes are never divisible by four. AxelBoldt

//0 You didn't move just above material but you moved out also this: << This gap was discovered by Euclid in 300 B.C.. Others define it to be simply G = q - p, so the gap G1 following the prime 2 has the length 1. Another definition for gap is with a parameter r = g/2 and some other authors have specified a gap by the terminating prime pk+1, rather than the initiating prime pk. >>

Yes, the slight variations in the definition of prime gap didn't seem to be important; the concept itself is more important. What exactly did Euclid discover? AxelBoldt

Euclid was probably first one who was thinking about gaps, so that's why I had put him in the article. I've noticed that someone sometimes wants definitions and nothing more than definitions and sometimes not. I think I have explained also good enough what initiating prime and its 'bounded' partner are. Gaps are very close connected with primes, so they should be well defined for better understanding of primes themselves.

Have no futher knowledges about Euclid's discovery.

//1 The example explains the ambiguity of maximal gaps. There are no gaps with greater size than 1131 from 2 to initiating prime 1693182318746371. So 1131 is the largest one bellow this prime and it stands on 64th place. g1=0 is first one. I don't know if a list of all known maximal gaps is appropriate for the article? We can put it in, if someone wants.

I see, that makes it clear. I'll put the maximal gaps back in. One more question: you say above that g64 = 1131. Does that mean in your notation that the 64th prime minus the 63rd prime + 1 equals 1131? AxelBoldt
No, no. Indexes of gaps and primes here are not equal at all. Perhaps 'late enough' would be pn-pn-1=gn+1-1 for some period or (it would be infinitive) after some initiating prime p. In this case is: g64-g63+1=1131-923+1=208. But it is here pX(of the 64th gap)-pY(of the 63th gap)-1=pZ=1693182318746371-1686994940955803-1=6187377790567. It is correct pX(n)-pX-1-1=gn-1 as it is in this first three examples: p2(of the 2nd gap)-p1-1=g1=3-2-1=0,p4(3)-p3-1=g2=7-5-1=1, p9(4)-p8-1=g3=23-19-1=3 and so on). For now on we need pencil and paper to produce more examples. And after some time we would need a computer soon. And finally 923 is 63th maximal gap. Initiating prime for g64 is 1693182318746371 but is not 64th prime.
Oh, so the n in gn refers to the fact that gn is the n-th maximal gap? Then we have to change the notation in the article. AxelBoldt

//2 (Probably) Yes.

//3 I think gaps above 1131 were found in this way. Someone took some special types of primes and he calculated with one primality test gaps between them. Some were greater than 1131 but these primes were much bigger and much 'far away' than primes near 1 &middot 1016. Someone should examine all primes above initiating prime of the maximal gap g64. I do believe that there exist a gap, let us say, gx1=24242824248748732872000000000000000000000001, but, first nobody knows where and second, if he knows it, what would this help him to complete a gapopedia. And finally what are the still uknown properties of gaps we should look for? (I do hope I had understood Pardo's discovery and of others well enough. --XJam [2002.03.27] 3 Wednesday (0)

[edit] Defining 'prime number'

The first section gives two contradictory definitions of prime. The first definition would imply -2 is not prime. The article should either give a single definition, or it should explicitly say that there are two different definitions in common use. The math dictionary I own gives only the second definition: an integer not equal to 0, 1, or -1, whose positive divisors include only 1 and itself.

The first section gives two definitions of prime, but they aren't really contradictory. One is a definition of primes in N, the other of primes in Z. Perhaps this should be made clearer. If the term "prime numbers" is used without further clarification it usually means primes in N, and I think this is how the term is usually used in Wikipedia. --Zundark, Thursday, April 4, 2002
Yes the first definition is a bit deficient. In the second section is then said that primes can be negative natural numbers too. (In fact 1 is prime, but this is a convention, right?) How about 0? Why 0 is not a prime? We can't make natural factorization on it perhaps this would be too trivial. --XJam [2002.04.04] 4 Thur's day (0)
By the fundamental theorem of arithmetic, -2 cannot be prime, since (-2)² = 2² = 4. You also can't prime factorise -1 (and you can't uniquely prime factorise any negative number, or 0). Unless someone can demonstrate the usefulness of 'negative primes', implying 'prime natural number' every time you say 'prime' seems superfluous. We can also use the theorem to define primes P as the increasing sequence of integers {p1,p2,p3,...} such that for all n ∈ N there is a unique sequence of integers X {x1,x2,x3,...} where p1x1·p2x2·p3x3·...=n (i.e. the primes are exactly those integers which can uniquely prime factorise every natural number). We can then show 1 isn't prime (or the prime factorisation of 1 wouldn't be unique, and therefore the corresponding set X has all elements set to zero), and 2 is prime, and no prime can be negative, etc (you can probably also show that there is only one P which satisfies these conditions, but I haven't proved that in my head yet). (I allow for xi to be negative, but that still results in only one set of primes, which is trivial to prove. We can also use n ∈ Q, since rational numbers must also have a unique prime factorisation with some negative xi) Elektron 11:34, 30 Apr 2004 (UTC)
I've also corrected it and made it prettier and added bits. Elektron 12:14, 30 Apr 2004 (UTC)
On the other hand, for a unique factorization domain and its appropriate definition, −2 is a prime; because then uniqueness is defined up to multiplication by a unit in the ring. Charles Matthews 12:08, 30 Apr 2004 (UTC)
That went completely over my head Elektron 12:14, 30 Apr 2004 (UTC)
The point is that we have a concept of prime elements in any integral domain. The integers form an integral domain whose prime elements are the negative primes and the positive primes. The Fundamental Theorem of Arithmetic can be restated for this more general concept of primes, and it applies to all unique factorization domains. --Zundark 12:44, 30 Apr 2004 (UTC)
Right - but prime number really ought to stick to natural numbers, anyway. Other stuff should be done by links. By the way, this page pretty well takes the biscuit for being a confusing talk page. Anyone here competent and able to clean it up/archive stuff, without infringing any wikiquette? Charles Matthews 15:04, 30 Apr 2004 (UTC)
You can uniquely prime-factorise 1 (203050...), but you can't uniquely prime-factorise 0 or -1 no matter what you define as 'prime'. You can uniquely prime-factorise integers less than -1 (using the primes -2,-3,-4,-5,-6,-7,-9,-11,-13), but this limits you to an odd number of prime factors for every integer. My point is this: each natural number is uniquely represented by a sequence of prime indices (e.g. 1 ~ {0,0,0...}, 10 ~ {1,0,1,0,0,...}, 12 ~ {2,1,0,...}), and each sequence of prime indices uniquely represents a natural number. Extending this to zero or negative numbers doesn't work, and changing the fundamental theorem of arithmetic so that no 'uniqueness' is necessary seems icky. Elektron 09:19, 1 May 2004 (UTC)
OK, perhaps it isn't so hard to understand, for example, that unique factorisation of polynomials is naturally stated as 'up to constants'. In any case anyone who wants to know the standard usage on unique factorisation in more abstract contexts has to get over this hurdle. Charles Matthews 10:39, 1 May 2004 (UTC)
Elektron, I just wanted to re-assure you that what Charles and Zundark are saying is standard undergraduate mathematics (and has been for decades) and not some wacky left-field thing. "Uniqueness up to" is a pervasive and undoubtedly useful concept in algebra, although it may seem a little odd when meeting it for the first time. Pete/Pcb21 (talk) 09:06, 4 May 2004 (UTC)

-1, 0, and 1 are not prime, by definition, because that definition is more useful than one that includes them. --LDC

When discussing primes it has always been the convention to assume we are only discussing primes in N: this is not a Wikipedia convention, it is found in all number theory AFAIK. When discussing negative primes (those not in N but found in Z) people will usually clearly identify this as such. Most mathematicians do not regard negative primes as particularly interesting, however one day someone may discover some fascinating property exclusive to negative primes and change this attitude.
The definition of 1, 0 and -1 as neither prime nor composite occurred because (as LDC rightly pointed out) there was no perceived benefit to a prime definition that included them, and it messed up an otherwise very useful definition. Until someone can prove that there is a genuine benefit to changing this definition (which has been around for several hundred years) this will probably remain the case. The quotient of 1/0 is left as "undefined" for similar reasons - having a defined value for 1/0 only messes things up and doesn't serve any (identified) useful purpose.
A request - could someone (Axel, LDC, other?) write the article on illegal primes? It sounds really interesting and I was keen to learn the rest of the story. - User:MMGB

The reason that 1, 0, -1 are not considered prime nor composite can be best explained by thinking in terms of the concepts of general ring theory. We are looking at a commutative ring with unity. Prime elements in these rings are usually defined as elements p such that whenever p divides ab, then either p divides a or p divides b. EXCEPT that we exclude those elements that trivially divide everything in ring, in the case of the integers, these elements are 1, -1, which are called the UNITS of the ring. A prime is defined as a non-zero, non-unit, that satisfies the above property. 1 and -1 are excluded because they trivially divide everything. Zero is excluded because it only divides itself, nothing else. The reason the NEGATIVE primes are considered not so interesting is that we only really care about primes "considered up to a unit", i.e. primes which differ by a unit element are identified or associated with each other. Since 1 and -1 are the only units, this means every class under this relation has 2 elements, namely itself and its opposite, -3 isn't important because it's ALREADY identified with 3 by multiplication up to the unit element -1.

The Shorter OED definition includes 1 as a prime number. Also, since every definition of "prime" explicitly excludes 1, one is led to believe that it really ought to be anyway. Peter T.S. 02:33, 5 November 2005 (UTC)
I suggest the following shortest possible and correct definition of prime for the Wikipedia article "Prime number":
A prime number is a natural number with exactly two natural divisors.
Hans Rosenthal (hans.rosenthal AT t-online.de -- replace AT by @ )
PS: Never forget that here we are just seeking for a fine and simple definition of the term prime number !

The definition given in the first paragraph is contradicted by the information given later on primes in rings, which is more modern. A link in the first paragraph to the more general definition would be helpful.

Re: "When discussing primes it has always been the convention to assume we are only discussing primes in N" This clearly does not correspond to the page as it stands. Nor should it, entirely. I am coming here from a discussion in which the definition from this page was cited inappropriately, based on its first paragraph alone. So what is up currently is misleading. The question "is -2 prime?" is fairly subtle; the answer is: if you are in fact working with all integers, then in that context -2 is indeed prime; and if you are working only with positive integers, then the question does not arise. Abu Amaal 19:58, 26 February 2006 (UTC) [moved to proper subsection, condensed] Abu Amaal 15:13, 27 February 2006 (UTC)

In mathematics one should strive to have as little as possible definitions. If something follows from the definition it should nót be ín the definition. The definition given by Hans Rosenthal, A prime number is a natural number with exactly two natural divisors, is the shortest and most accurate definition possible. That 1 and the prime number itself are its only (Natural) divisors logically follows from this definition. After all:

1 = 1 \times 1,

therefore:

\frac{1}{1} = 1.

Since we know that \forall_{n\in\mathbb{N}}\left [ n \times 1 = n \right ], it goes without saying that:

\forall_{n\in\mathbb{N}}\left [ n \times \frac{1}{1} = n \right ].

And thus it follows that for every natural number, 1 is a divisor. Something similar can be done for the prime number itself. Because it follows from the definition that, if a natural number has exactly two (different) divisors, these divisors are 1 and the prime number it self, this should nót be included in the definition.

Ruud

[edit] Ulam spiral

According the the article, the Ulam spiral question is an open one. However, there is information about the origin of this pattern in M. Gardner, Sixth Book of Mathematical Games, Scribner?s, 1971 if someone would look it up. Anyhow, one quick explanation is that any prime (excluding 2 and 3) is equal to a multiple of 6 +/- 1. The reason for this is as follows: Break the primes into 6 columns (http://www.geocities.com/~harveyh/Image_No/Plot_Lin.gif, from http://www.geocities.com/~harveyh/moreprimes.htm . Anything in column 2, 4, or 6 is divisible by 3. Anything that is in column 3 is divisible by 3. Those numbers form the basis for diagonal patterns when using a spiral since the spiral offsets these numbers by 1 in each loop (looking at one particular side of the loop).

Have also a look at the discussion in Talk:Ulam_spiral. There is probably not much mystery left in Ulam's spiral. FvdP 11:53 Nov 19, 2002 (UTC)

[edit] Formulae for primes

Here are the explicit formula for prime numbers, twinprimes, number of primes, number of twinprimes. It was published in the Proceedings of the Indian Academy of Sciences and reviewed by other mathematical journals. The formula was examined as correct by world renowned mathematicians such as Dr.Paul Erdos, Dr.Halberstien and Dr. K.Ramachandra of TIFR. The four formulae were discovered by Venu Atiyolil in the year 1983 and are presented below in the pdf format. The proof may be difficult to follow to some mathematics students as the method of writing was from a world class School of Mathematics where the author was a research member.

http://www.ias.ac.in/jarch/mathsci/92/00000050.pdf http://www.ias.ac.in/jarch/mathsci/92/00000051.pdf http://www.ias.ac.in/jarch/mathsci/92/00000052.pdf http://www.ias.ac.in/jarch/mathsci/92/00000053.pdf http://www.ias.ac.in/jarch/mathsci/93/00000068.pdf

<End of article> ____________________________________________________________________

I was going to change the formulas to TeX, but some of them don't seem to make sense.

Under "Formulas generating prime numbers", the first "alternately" definition given subtracts (j-1)! from itself. Thus the summation function is just 1/j.

The second "alternately" divides j by itself. This also effectively means (j-2)! is subtracted from itself, so the summation function is 0.

These are obviously incorrect. What exactly is to be done about these? Eric119 06:30 Feb 17, 2003 (UTC)

Um, never mind this. Silly me, I didn't catach on that [x] was given as the floor function. I thought it was just normal bracketing. Okay there are no problems with the formulas now (except I still need to convert to TeX...). Eric119 06:41 Feb 17, 2003 (UTC)

An anon user added some bogus about prime number formulae. Please do note that the number of computations in these formulae is at least as big as the number of computations involved in optimised versions of Erastothenes' sieve for a number of comparible size. Can someone make it NPOV? Gebruiker:Dedalus 12:24, 28 Feb 2005 (UTC)

I've reverted the page, and I'm moving the information about Venu Atiyolil's contributions to formula for primes, where I will rewrite it NPOV. -- Dominus 14:47, 28 Feb 2005 (UTC)
I replaced the link to the author's GeoCities site (which was unreliable, since the paper in question was only downloadable at bitmap images that soon exhausted his bandwidth quota) with links to the PDF archive version of the pages on the official web site of the Indian Academy of Sciences. -- Dominus 15:09, 28 Feb 2005 (UTC)

I've reverted all the changes by this anon guy. He keeps adding info to articles when it's been moved from one article to another, and he also has been deleting/altering comments on talk pages. CryptoDerk 03:13, Mar 5, 2005 (UTC)

The two classic formula n * * 2 − n + 41 and n * * 2 − 79 * n + 1601 return a better prime density than the asymptote n / log(n) thru the 1st 9999 integers unaltered. One would expect approx. 2500 primes (10000/log(10000))and each eqn yields approx. 4150.--Billymac00 21:55, 9 June 2006 (UTC)

[edit] First 25 primes

I don't like the table "The First 25 Primes". Apart the number themselves, there is no really interesting and relevant information. The length of periods of inverses in base 10 has some interest but is not relevant or interesting enough for this article. Who minds how one writes the prime numbers in binary ??? That should be an "exercise left to the reader" ;-) --FvdP 20:53, 30 Oct 2003 (UTC)

So I removed it ("be bold" !) and here is it:

n pn Binary 1/p Len
1 2 10 0·5 1
2 3 11 0·3... 1
3 5 101 0·2 1
4 7 111 0·142857... 6
5 11 1011 0·09... 2
6 13 1101 0·076923... 6
7 17 10001 0·0588235294117647... 16
8 19 10011 0·052631578947368421... 18
9 23 10111 0·0434782608695652173913... 22
10 29 11101 0·0344827586206896551724137
931...		 28
11 31 11111 0·032258064516129... 15
12 37 100101 0·027... 3
13 41 101001 0·02439... 5
14 43 101011 0·023255813953488372093... 21
15 47 101111 0·0212765957446808510638297
872340425531914893617...		 46
16 53 110101 0·0188679245283... 13
17 59 111011 0·0169491525423728813559322

0338983050847457627118644

06779661...		 58
18 61 111101 0·0163934426229508196721311

4754098360655737704918032

7868852459...		 60
19 67 1000011 0·0149253731343283582089552
23880597...		 33
20 71 1000111 0·0140845070422535211267605
6338028169...		 35
21 73 1001001 0·01369863... 8
22 79 1001111 0·0126582278481... 13
23 83 1010011 0·0120481927710843373493975
9036144578313253...		 41
24 89 1011001 0·0112359550561797752808988
7640449438202247191...		 44
25 97 1100001 0·0103092783505154639175257

7319587628865979381443298
9690721649484536082474226

804123711340206185567...		 96

[edit] The Bear

Should there be a link to Prime Number Shitting Bear on this page? Right now that page is essentially an orphan :) Adam Bishop 20:30, 3 Dec 2003 (UTC)

I've added it. Arvindn 03:59, 4 Dec 2003 (UTC)
There is no such Wikipedia page, must have been deleted or something since 2003. And I question the value of the external link. I was surpised to see the word "sh**" in relation to primes. Does anyone else see value in it? MathsIsFun 10:02, 19 December 2005 (UTC)
I do. -- Dominus 21:59, 19 December 2005 (UTC)

[edit] What is a prime number

A prime number is a number with exactly two factors. What is wrong with this simple definition? Why worry about 1?

It is stated, that the definition given is used throughout Wikipedia. Check that out (e.g. german version).

6 has two factors, 2 and 3, but isn't prime. Dysprosia 12:15, 26 Feb 2004 (UTC)
6 has four factors (1, 2, 3, and 6), not two. -- Dominus 22:09, 26 Feb 2004 (UTC)
That's what one gets when one edits late at night ;) I was thinking proper divisors only... Dysprosia 22:51, 26 Feb 2004 (UTC)
"What is wrong with this simple definition?" Well, it's simple, but the word "exactly" looks quite arbitrary at first sight (at least it did so to me, when I saw it for the first time, quite a long time ago). The real reason for not including 1 is that somehow, from the point of view of products, 1 is "empty", while the primes "have content". Where "to have content" can be defined as "to have at least 2 factors". That's why it's "exactly" rather than "at most". I think this should be explained, instead of asking people to blindly rely on definitions. --FvdP 18:52, 26 Feb 2004 (UTC)

Really, this is a FAQ. Should it have its own page? Not because there is a second point of view on whether 1 is a prime. But perhaps because some historic tables of primes did start at 1.

Charles Matthews 22:12, 26 Feb 2004 (UTC)

Being bored one summer I sat down and with nothing more than a pen and some paper worked out all the primes between (but not including) 1 and 10000. I later found out that I had created an optimised version of the Sieve of Eratosthenes (o=N*N). However, by doing this I came to the conclusion that the divisors definition is wrong and taught only because it is simple to write down.

If you look at the sieve method you should see that what you've got is NOT a definition of what is prime, but rather what is non-prime. From that you work out that what is remaining of your set of numbers is a set of primes.

To put it another way...

 a non-prime = X * a prime. Where X can be either prime or non-prime.

This simple equation has some important consequences. If we include 1 in the set of non-primes it can be used in the equation by replacing X with 1, then we'd get the following equation...

 non-prime = 1 * a prime. Therefore non-prime = prime. Which of course would make all primes also non-prime! (still with me?).

The alternative is to make 1 prime, which would produce the following equation...

 non-prime = X * 1. Therefore non-prime = X. Which would make every value non-prime, including 1! (didn't we just make it prime?)

As you can see this is a problem, but only if we place the value '1' into one of the sets 'prime' or 'non-prime'. The answer is remarkably simple - it's neither.

Once I realised this it pointed out how remarkably stupid the divisors 'definition' is and meant I finally knew why the value of 1 is not prime.

I haven't looked into what other consequences this could have, like in the negative realm - I'm not a mathemagican! However I did go back to my maths teacher and explained this to him, he was very impressed, but decided to keep teaching the old system, but such is life.

In a sense your are correct: 1 is regarded in mathematics as a 'unit', which is object distinct from primes and composite numbers.
But your equation non-prime = X * a prime is simply not true if X is allowed to be 1 (what in mathematics is called a 'multiplicative identity'). You've generalized an equation past its point of truth, and then think that its consequences are somehow profound.

-- Saforrest 14:58, Feb 11, 2005 (UTC)

I learned counting starting with zero. Prime numbers have exactly two divisors. For example, 2 has divisors 1 and 2. And 1 has only 1 divisor, and that divisor is 1. Therefore, 1 is not a prime. Neither is it a composite. A composite has at least three divisors, or at least two proper divisors. The table of prime factors included 1 as a prime factor of 1, that was to silly. Gebruiker:Dedalus 21:59, 15 Feb 2005 (UTC)

I see where I have gone wrong. The method I was taught was - a prime is a number which can be DIVIDED only by itself and 1 (a truely incorrect definition!). I apologise about the confusion that I may have caused with divisors. However, I still believe that the definition of a non-prime has value and can reduce confusion about what is prime. Especially since everyone I have ever talked to about this believe 1 to be prime (or non-prime)!

[edit] List of prime number topics

what about an article "List of prime number related articles"? I think it'd be nice to gather them all in a page so people could read all about prime numbers that wikipedia has... Kieff 02:42, May 4, 2004 (UTC)

It's not a bad idea. Th raw material should all be at List of number theory topics, if someone wants to compile such a list. Charles Matthews 09:44, 4 May 2004 (UTC)

[edit] Prime Numbers in Science

I have moved this from the article:

Pradeep Kumar, Plamen Ch. Ivanov, and H. Eugene Stanley discovered an interesting pattern in the distribution of prime numbers.

This is recent work (see http://xxx.lanl.gov/abs/cond-mat/0303110); it might merit inclusion somewhere, but I'd like to see more background. After all, the statistical properties of the primes have been studied intensively.

Charles Matthews 09:31, 4 May 2004 (UTC)

Removed: The first recorded prime numbers were found in Africa on the Ishango bone dating back to 6,500BC. They were 11, 13, 17, 19.

As firstly it's unclear what this statement actually means, and secondly googling there seems to be little evidence that these numbers were intentionally prime.

--Gunter 22:18, 31 Dec 2004 (UTC)The statement is obvious. lunar calendar or not is besides the point, they are the first recordings of prime numbers

From the "Prime gaps" entry:

"We say that g_n is a maximal gap if g_m < g_n for all m < n. The largest known maximal gap is 1131, found by T. Nicely and B. Nyman in 1999. It is the 64th smallest maximal gap, and it occurs after the prime 1693182318746371."

Is the second sentence of the above statement still up-to-date ?

Hans Rosenthal (hans.rosenthal AT t-online.de -- replace AT by @ )

[edit] Website

I don't want to put it right into the article since I made it myself, and I would feel like I was spamming, but someone might enjoy <<SPAM FILTER>>/maths/books/prime/ , which is an article on Prime Numbers I wrote.


[edit] This page

Could "some part" of this page be put into an archive (as it is getting long)?

[edit] Primes in other base systems

How do prime numbers work when numbers other than 10 are used (eg base 6, base 23 etc)? Would there be different primes, more of them or less of them?

Prime numbers are not defined in terms of a base. They are the same numbers however you write them. --Zundark 18:12, 23 May 2005 (UTC)
What Zundark is saying is not entirely clear. If you were in base 6, the base 10 prime numbers (2,3,5,7,11,etc.) would be converted to base 6 (2 to 2,3 to 3,5 to 5,7 to 11,11 to 15). Interesting thought, though. —The preceding unsigned comment was added by 69.253.29.7 (talk) 20:07, 16 March 2007 (UTC).
Zundark is right. Changing base means to change the numeral used to represent a natural number, but it does not change the value of the number. Primality is a property of the value of a number and it's irrelevant how the number is written, just like 3/2 = 1.5 is the same number and has the property of being in the middle between two integers, no matter how it is written. PrimeHunter 00:18, 18 March 2007 (UTC)
Some of the divisibility tests change, though. You can't use digital roots to test divisibility by 3 or 9 in duodecimal like you can in base 10, to give just one example. Anton Mravcek 18:35, 18 March 2007 (UTC)

[edit] Likelihood x is prime

From prime number theorem:

One can also derive the probability that a random number n is prime: 1/ln(n).

I know this is normal shop talk (I am a number theorist myself), and I have heard such statements for years, but that still doesn't stop me from having the right to the opinion that such a statement is complete nonsense. Actually, the way it is worded now in the article is fine with me...I included "randomly-chosen" just for all the non-math, or non-number theory oriented readers. But, I still feel that statements such as the above are misleading at best and damaging at worst. I am not alone in this sentiment: while talking a number theory/complex analysis class at Univeristy of Oregon, the teacher (Dick Koch) recalled a conversation he had with a non-number theorist and when he said "the prime number theorem tells you the probability that n is prime", his colleague insisted he was talking nonsense. Of course, we all know what we "really" mean when we say something like this, but I think it's more instructive to give an example: if you choose the 1,000 natural numbers between 1,000,001 and 1,001,000, then you will expect to find roughly 1,000/ln(1,000,000) primes amongst them. This is a more helpful way of explaining it, I think. But, again this is just my opinion. Revolver 10:05, 31 May 2005 (UTC)

As I keep repeating, the problem with people writing pages that they don't understand very well is an inability to be imprecise. The reason is that they need the details in order to understand the concepts. This leads to overly technical explanations that fail to address the basic conceptual issues. Moreover, this whole field is about forgetting details (asymptotics). As I wrote elsewhere on this page, heuristic (that is, non rigourous) probabilistic reasoning leads to correct conjectures about the distribution of primes. Not only that, but rigourous results are often obtained by trying to make these arguments precise, in particular, sieve theory. For example, the large sieve is essentially based on the hypothesis that the primes in different arithmetic progressions are probabilistically independent. ilan 10:34, 31 May 2005 (UTC)

I understand what the PNT says, and I understand what the intended meaning of your original wording was. My point is that the ability to be imprecise is an achievement that only comes from lots of experience and familiarity with these areas of research. For the seasoned researcher who has been thinking about these issues for years, such imprecise thinking is very useful in many ways, in the manner you describe. I'm less optimistic about how useful it is to people trying to learn this stuff for the first time. I'm really pessimistic about how useful it is to the kind of general, mathematically naive reader who visits a popular page like this. Saying "for large n, the probability that n is prime is 1/ln(n)" means a lot, if you already have a fundamental understanding about what the PNT says, and you have experience in interpreting these kinds of statements. If you don't already understand PNT, or you have little experience thinking in this way, I wonder if such a statement is more confusing than enlightening, that's all. You said it yourself -- "they need the details in order to understand the concepts". You were talking about authors, but doesn't the same observation apply to readers? Revolver 11:08, 31 May 2005 (UTC)


I believe that the person who doesn't understand probability in a technical sense, e.g., thinks he understands when he hears the weather report saying that the probability of rain is 50%, will accept a statement like: "the probability that a large number is prime is 1/its digits" and will have some kind of understanding which is a lot better than the student trying to understand all the steps in the actual proof of the prime number theorem, taught by someone who never gave any motivation. It reminds me of me, when I was taking analysis in university, and I never understood Fourier series, as taught by my pure math professor. Years later, I looked at signal processing books, and the following explanation came to mind: "Fourier coefficients are the graphic equaliser on your stereo," which would have helped me a lot earlier. On the other hand, you have a point, that suppressing details can be more of a barrier for people who actually know the subject somewhat. However, these people should look at a textbook, instead of this site. ilan 11:29, 31 May 2005 (UTC)


(so theoretical physicists would just regard them as being true)

This seems to be stretching it. Even theoretical physicists still acknowledge the distinction between convincing heuristic arguments and according-to-Hoyle proof?? Or am I missing something? Revolver 11:20, 31 May 2005 (UTC)

[edit] Polynomial log(N) deterministic

Is there a source for this claim? --MarSch 13:38, 20 October 2005 (UTC)

[edit] I give up! Verification of prime numbers take too long... (pun intended)

I tried thinking of a way to include this information without to much contreversy. Anyone here, a regular editor want to venture into adding this information. http://www.magazine.carleton.ca/2004_Fall/1342.htm --72.57.8.215 00:58, 7 January 2006 (UTC)

[edit] Removal of "spam"

EJ, you apparently removed my "spam" prime number program which was actually legitimate. Reread the page I wrote with the program on it - it is legitimate. You can go ahead and download it for yourself. Do tell, what qualifies it as spam that caused you to remove it so I can correct it? I rewrote the link title so it doesn't look as spammy as it was before to eliminate confusion. STufaro 02:29, 6 February 2006 (UTC)

I did check the page before removing the link. Just in case you didn't notice, Wikipedia is an encyclopedia, and the "External links" section is supposed to give pointers to on-line resources with useful additional information on the subject, which are not already covered in the article. Specifically, it is not a repository of links to every trivial implementation of trial division which someone posts on Web. -- EJ 03:01, 6 February 2006 (UTC)
Therefore you should remove all prime number calculators because they are trivial implementations of trial division. As far as I have checked there is no other executable prime number calculator linked to in "External links". It is useful information. It is relevant. It is not covered in the "external links" section. No reason to remove. STufaro 03:12, 6 February 2006 (UTC)
The fact that there may be other links in the section without merit is not an excuse to add yet another one. And no, it is neither useful nor information. It is already covered in the section "finding prime numbers" and in the article on primality testing. -- EJ 03:26, 6 February 2006 (UTC)
I ask, what is the harm? I'm not making money off of it in any way by posting it in wikipedia, I'm not hurting anyone - I'm providing a resource. This program generates a text file with prime numbers. That's all it does. It's relevant and it's useful. What's the harm in leaving it? It is not added because I take pleasure in adding it. I add it only to provide the resource. By the way, try not to be so snooty-sounding in your replies. I believe that's covered in an article entitled personality disorder. (I don't mean that to hurt your feelings or anything. I mean that to remind you that though you may be researching numbers all day and your IQ is ten times that of mine, that you and I are equals and you should not be disqualifying me by using snooty phrases such as "Just in case you didn't notice, Wikipedia is an encyclopedia"). Watch how you come across, my friend. And be consistent. Remove all the other prime number calculators too. STufaro 03:34, 6 February 2006 (UTC)

[edit] Cleanup of links

The external links section is way too long, so I did some cleanup. Here are the removed links, with rationale.

Nothing an average CS student cannot do in an hour.

Duplication.

One online calculator is enough, and the WIMS one is more powerful.

Is more relevant to AKS primality test, I'll move it there.

May be relevant to probable prime, where at least the reader knows what it is about. In fact, the link is already there.

A funny picture of bear, but it does not appear to do anything useful. If there is some deep connection of bears to primes which would explain the joke, then I can't see it.

Nothing noteworthy.

One link on the prime spiral is enough.

There are 30 billion or so 12-digit primes, and being a divisor of Googolplex - 1 is a pretty random property.

Only God knows why it was there hidden in an HTML comment.

I will not remove the last link again (see above), as I didn't count whether or not it already was a third revert, but it clearly isn't noteworthy.

Other dubious links which I didn't yet remove:

A lot of fancy graphics, but if there is some informative content, it is well hidden.

  • Factorizer Windows software to find prime numbers and pairs of prime numbers less than 2,147,483,646.

Commercial software. -- EJ 04:55, 6 February 2006 (UTC)

I do apologize for the hostility, EJ. I was really steamed last night over a few issues at home, and I don't mean to insult you or your intelligence. Was having a mad-at-the-world moment. I hope you understand, and many thanks for leaving my link (I just made the program slightly faster). The reason I want to keep it up there, simply, is because I know two things: One, my 7th grade math teacher had a gigantic list of prime numbers on the board, and two, calculating them is a lot faster than downloading them for some people. Once again, apologies. Thanks very much for leaving it. I'm in the process of making the page slightly more informational now :D. STufaro 23:36, 6 February 2006 (UTC)

[edit] Probably dumb question from a non-mathematician

But I'm curious: It's been frequently said that one is not a prime number, but it's never been explained why. It, too, is only divisible by one and itself. Where's the distinction that makes one non-prime? Ie., what is the mathematical usefulness of excluding one from this category? -a puzzled Kasreyn 08:36, 11 February 2006 (UTC)

A very important theorem of number theory is the so-called fundamental theorem of arithmetic, which says that every number has a unique factorization into primes. If you admit 1 as a prime, this theorem is false, since, for example, 6 = 2×3 = 1×2×3 = 1×1×2×3 = ... . So you'd have to qualify the fundamental theorem with a lot of uninteresting qualifications about 1. Then similarly, suppose you want to explain how to find the prime factorization of a number n. If n is prime, you're done; otherwise n is composite then it has the form pq, where p is prime; find the factorization of q by the same method, append p, and you're done. Simple. Except no, if p might be 1, then the algorithm might never terminate. So again you have to clutter up the explanation with a bunch of exceptions for 1. And then again: if p and q are prime, and p divides q, then p=q. Oops, unless p=1. So again you have to make an exception for 1 if you have admitted 1 as a prime.
Admitting 1 as a prime number messes up all these theorems, which otherwise have simple statements. If the messing up accomplished something of real value, it would be all right. By this, I mean that if the explanations had to be complicated in order to help people understand some subtle point that was of real interest, that would be all right. But in these examples and many others, the additional complication introduced by admitting 1 as a prime number does not lead anyone to any better understanding of what is going on. Perhaps you can think of more examples yourself.
So it's easier to make the exceptions up front, all at once, and just say that 1 is not prime. -- Dominus 18:35, 11 February 2006 (UTC)
Thanks for taking the time to explain it! I guess I hadn't realized how disruptive a little old one could be in an equation, but it makes sense now that I consider it. ;) So basically, no one is denying that one shares important similarities to prime numbers, but it's simply seen as easier to have the "except one" language, one time, as opposed to having to append it to every theorem to keep one from breaking the math. For some reason, that makes me smile. -Kasreyn 10:14, 12 February 2006 (UTC)
Exactly so. Of course nobody is denying that 1 shares important properties of the prime numbers. But it also lacks many important properties of the prime numbers. So it makes sense to put it into a third class (called "units") and this is exactly what mathematicians do.
Some integral domains have more than one unit, and in such contexts there the classification of 1 as nonprime makes even more sense. For example, in the Gaussian integers, there are four units. You don't want to say that i (√-1) is prime, since i = i5, which would be bizarre. But you don't want it to be composite either, since it has no smaller factors. It really is a unit.
Similarly, if you consider the positive rational numbers as a domain, you come to the conclusion that every number is a unit, and everything else is nice and consistent.
So the short explanation is that dividing numbers into two classes (prime and composite) doesn't work well, but dividing it into three classes works just fine. For the usual case of the positive integers, the two systems are a lot alike, and the problems with the prime-composite dichotomy are simple enough that it might be tempting to sweep them under the rug. But when you study the same ideas in more general contexts, you get into trouble and conclude that the three-way division is the more appropriate one. -- Dominus

[edit] applications

Regarding the novel "Contact", would it be appropriate to add under Applications that it has been suggested that a sequence of prime numbers, being clearly distinguishable from background noise, would be a good way to catch the attention of ETI's? For instance, a message sent from Arecibo as part of the SETI program encoded data in a 23x73 grid, using prime numbers to assist in any decoding. Other proposed methods resemble the fictional alien signal in "Contact", prefacing a signal with a sequence of primes in order to say "hey, pay attention, this is information, not noise!", since it can probably be safely assumed that a species that has radio understands primes. Would anyone object to my adding this application of prime numbers to the article? -Kasreyn 12:44, 12 February 2006 (UTC)

[edit] the first paragraph

/Prime/ numbers are of course of /prime/ importance - Was that really nessecary? :) --Thenickdude 02:59, 17 February 2006 (UTC)

Huh? ^_^;; I'm confused -Kasreyn 10:50, 21 February 2006 (UTC)

[edit] Removal of Number Template

I'm removing the number template from the prime number page, because prime numbers are not apart of quantity or listed in that template. Is a template for integer sequences in order? Timothy Clemans 06:19, 5 March 2006 (UTC)

I perfectly agree that it was the wrong template. Templates are nice if they take just little room, and have very relevant related links. Otherwise, a category at the bottom does a better job. Oleg Alexandrov (talk) 00:09, 6 March 2006 (UTC)



[edit] About the incomplete totality of the set of all prime natural numbers

Essay and discussion moved to User:BenCawaling/Essay. Gandalf61 08:35, 14 April 2006 (UTC)

[edit] Formulas yielding prime numbers

I moved here the following comment by 68.38.126.159 from the article. -- EJ 04:46, 26 March 2006 (UTC)

I've also seen the beginnings of a formula for prime numbers. Consider the rule that if a number(N) is odd, you should square it, then subtract the number that is one above the original number. (N*N)-(N+1)= a prime number. If the original number is even, then it should be squared and the number one below the original number should be subtracted from it. (N*N)-(N-1)= a prime number. This only works for N = Integers less than ten. Once double didgits are involved, the rule will mutate in a fashion that is unbeknown to me at this time. Any help would be greatly appreciated. P.S. I will consent to the idea that 1 is not a prime number due to prime factorizations, but the rule still seems valid. (Zepher)

[edit] Primes in Nature

Hiya. I'm sorta new to this wiki thing, I've only done a few minor edits before this. I agreed with most of the discussion on Prime numbers in nature, that the cicadas bit was the only bit worth mentioning, none of the others were present in nature because they were prime, they were just coincidences. So I Copied the cicadas bit, twiddled it a little bit, and added a little bit explaining that not every occurence of a prime in nature is significant. I couldn't, however, bring myself to delete the link to the 'main article', since it hasn't been deleted yet. Should I?

Or have I overstepped the mark here; should I have left it how it was?—The preceding unsigned comment was added by Bumnut (talk • contribs) 08:03, 30 March 2006 (UTC)

As I understand it, the GFDL requires that you copy (the relevant part of) the history of Prime numbers in nature to this talk page (or a subpage thereof) if you copied the cicada text. If you had restated the information in the cicada text, then no acknowledgment is required under copyright law, and none is required here.
I could easily be wrong here, but I think that's what you need to do. Of course, I've only be active here a few months .... — Arthur Rubin | (talk) 21:35, 30 March 2006 (UTC)
Since the separate was article was merged and redirected, the history is still available in the history of Prime numbers in nature, so everything should be ok. Schutz 12:48, 9 April 2006 (UTC)

Someone should check the news about theses cicadas, I'm sure I read something saying this is actually false; I changed the article to show this uncrtainity.—The preceding unsigned comment was added by 132.206.124.48 (talk • contribs) 20:47, 10 December 2006.

The content of the article was relatively well sourced; I don't feel comfortable adding assertions such as "this seems to have been proven false" without any source. Your claim may be correct, but I have reverted your change until someone can provide a reference. Schutz 20:09, 10 December 2006 (UTC)

[edit] Properties

I am going to remove the following "properties" from the list:

  • Each prime number p > 3 is ± 1 (mod 6).
  • For each prime number p > 2, there exists a natural number n such that p = 4n ± 1.
  • For each prime number p > 3, there exists a natural number n such that p = 6n ± 1.

The first one says that any prime greater than 3 can not be a multiple of 2 or 3; the second says that any prime greater than 2 can not be even, and the last one is the same as the first one, so that they are all trivial, even written in terms of modulos. Schutz 12:48, 9 April 2006 (UTC)

[edit] Suggested merge of an article about the primality of segments of a certain decimal number

This notice was slapped on the top of the main article.

{{mergefrom|357686312646216567629137}}

This is inappropriate, as articles are meant for readers who should not be distracted by editing notes.

Moreover the suggestion that the content of the article in question is significant enough to include in the article itself seems unsupportable. This is a curious property of the decimal expansion of an integer, and is of very minor mathematical significance. Decimal expansions in general are of little mathematical significance - certainly no more than many other bases - and their relationship to prime numbers is of no particular importance. Elroch 00:02, 17 April 2006 (UTC)

Good idea to add a trivia section, although the addition uses an unreasonable amount of space for a quirky fact with very little mathematical significance. Elroch 15:56, 18 April 2006 (UTC)

The only reasonable thing to do is to create an article called truncatable prime. Trivia sections must die. Fredrik Johansson 16:02, 18 April 2006 (UTC)
I feel loathe to do it, but to save the main article from an ugly pile of decimal numbers, it seems a good course of action. However, I think a trivia section with one line for each of the two numbers is reasonable to address the needs of people who are interested in quirky, offbeat facts. Elroch 16:19, 18 April 2006 (UTC)
I don't think it would be worth creating an article just for truncatable primes; I don't really mind having the trivia section (the illegal prime stuff fits ok in there), but the information on truncatable primes would indeed fit better in an other section, maybe a new one about "special primes". However, before we start adding new sections, this article needs to be cleaned up (there are way too many sections, sub-sections, sub-sub-etc); in the meantime, I think we could keep the truncatable primes under trivia. What do you think ? Schutz 19:23, 19 April 2006 (UTC)
The thing is, there are countless types of "special primes" (see list of prime numbers for an incomplete list). There's no use even trying to add them all to this article. We have similar articles for probably hundreds of other special numbers and number sequences, so I don't see what the problem is with truncatable flavor in particular. Fredrik Johansson 19:48, 19 April 2006 (UTC)
So let's do it the usual way: have a summary section on this page called "Special primes", with a link to the main page on the topic which could be either list of prime numbers, or special primes, or whatever. I don't particularly mind if truncatable primes are defined on this page or not; however, if we do not have much more to add on the topic that what is currently on the web, we do not necessarily need a whole new article. Schutz 20:29, 19 April 2006 (UTC)

[edit] Suggested edits to section “The number of prime numbers” subsection “There is an infinite number of prime numbers”

Change section heading —

The number of prime numbers

to —

The count of prime numbers

Change subsection heading —

There is an infinite number of prime numbers

to —

There is an infinite count of prime numbers

Change the quoted phrase —

"there are more than any given [finite] number of primes"

to —

“there are more prime numbers than any given finite count of prime numbers”

Change the paragraph —

Suppose you have a finite number of primes. Call this number m. Multiply all m primes together and add one (see Euclid number). The resulting number is not divisible by any of the finite set of primes, because dividing by any of these would give a remainder of one. And one is not divisible by any primes. Therefore it must either be prime itself, or be divisible by some other prime that was not included in the finite set. Either way, there must be at least m + 1 primes. But this argument applies no matter what m is; it applies to m + 1, too. So there are more primes than any given finite number.

to —

Suppose there are only a finite count m of prime numbers — p1, p2, p3, …, pm (in increasing order). Then, the Euclid number n = p1p2p3…pm + 1 gives a remainder of 1 when divided by each of the given prime numbers pi, 1 ≤ i ≤ m. Therefore, n is either a prime number or n is divisible by some other prime number greater than pm. Either way, there must be at least m + 1 prime numbers. Since m is arbitrary, there are indeed more prime numbers than any given finite count of prime numbers.

Delete the paragraph (it is nonsensically circular) —

This previous argument explains why the product of m primes + 1 must be divisible by some prime not in the finite set of primes.

Add the paragraph (as second-to-the-last paragraph in this subsection) —

The early Greeks defined a _prime_ number as “a number measured by no number but by a unit only” or “a number that appears _first_ as a basis for other numbers to be multiples of” [Euclid, The Elements (Book VII, Definition 11) — translated with introduction and commentary by Sir Thomas L. Heath (New York: Dover Publications, 2nd edition unabridged) Volume II, pages 284 – 285].
In modern times, the Peano axioms for arithmetic formally defines the natural numbers {0,1,2,3,…} [wherein every natural number n has a successor natural number n + 1]. The fundamental theorem of arithmetic (or, the unique factorization theorem) states that every natural number greater than 1 is a unique product of powers of prime numbers — that is, the prime numbers are the “atoms” or the “building blocks” (this conforms with the early Greeks’ definition of prime number) of all the natural numbers.
Thus, at all times, the question about the infinitude of all the prime numbers is really just asking whether a finite count m of natural numbers greater than 1 — p1, p2, p3, …, pm — could appear first (prime) as the basis for all the other natural numbers greater than 1 to be multiples of. The simple answer is no because, for example, the Euclid number n = p1p2p3…pm + 1 is not a multiple of any of the presupposed prime numbers pk, (1 ≤ k ≤ m). [This non-multiple counterexample suffices to establish the infinitude of the prime numbers (that is, there are more prime numbers than any given finite count of prime numbers) — it is not necessary to contend that either n is a multiple of a prime number greater than pm or n would appear first (prime) as a basis for some other natural numbers to be multiples of.]
  • I'm still asuming good faith, but this is just wrong, as mathematics. Perhaps Ben would be happier editing philosophy articles. — Arthur Rubin | (talk) 17:44, 24 April 2006 (UTC)
For those of us who are not mathematicians, could you at least make some effort to show why it's wrong? It's not like we can decide which of you to trust in any other way. Kasreyn 17:57, 24 April 2006 (UTC)
The best thing I could recommend is for you to discuss the issue (copy the paragraph) with some mathematics professors --- you can e-mail any of the faculty members in the prestigious universities anywhere in the world through their online directories for their respective mathematics department (I have just sent messages to Professors Caldwell and Ribenboim --- I will inform you of their responses). Take three or more opinions --- then you decide.
I just received the following response from Professor Ribenboim's secretary —
Dear Benjamin -
I am Professor Ribenboim's secretary. He is currently out of the country (he will be back in Canada in July). As he does not have a computer (he has severe eye problems and reads with the aid of a machine), I will print your email message and send it to him by post. Please be patient waiting for a reply.
Best regards,
Connie Brobeck <mathstat@mast.queensu.ca>
As for my part, consider the following:
"The resulting number is not divisible by any of the finite set of primes, because dividing by any of these would give a remainder of one. And one is not divisible by any primes." --- Here, you had already obtained a remainder of 1 which already means non-divisibility so why would you still invoke indivisibility of 1? Kummer's proof (see Prime Pages in the Internet by Professor Chris Caldwell) involves k = p1p2p3…pm (which is greater than 2 and divisible by each of the given prime pi) and k - 1 (which is greater than pm so, by the assumption, it is not a prime number) --- hence, both k and k - 1 are divisble by some prime pi and so must be their difference 1, which is absurd (thus, Kummer's proof invokes the indivisibility of 1).
By definition, "a prime number is a natural number" --- so the natural numbers come first. Indeed, from among the natural numbers, the prime numbers are singled out as generators or factors of the natural numebers greater than 1. So the question is: could you have finitely many prime numbers to generate all the natural numbers greater than 1? The simple answer is no --- you need infinitely many prime numbers. BenCawaling 09:29, 25 April 2006 (UTC)
If the aim was to obfuscate Euclid's proof, introduce some odd (and non-standard) ways of saying things that are clearly understood as they are, wander off a a little ramble (rather than pointing out the crux of the theorem so that the maximum number of readers will get the point), I would support Cawaling's suggestion. But it isn't. Elroch 20:16, 24 April 2006 (UTC)

[edit] Grammar

Interesting how the phrase "there is an ... number of ..." seemed perfectly correct to me (and presumably many mathematicians as it survived here a month) until it was just changed. Google suggests this choice is used about a hundred times less than "there are a ... number of ...", which makes it rather eccentric to argue for the former. Doesn't seem any reason why the grammatical rule should be different from "there is a herd of cattle in the field", where the common choice is the opposite one, but common usuage wins in what is not really a technical use of language. Elroch 13:01, 25 April 2006 (UTC)

[edit] Program

I added the program to find primes im not good at explinaing so if nyone else can? or if you want to contact me im here Wolfmankurd 21:20, 29 April 2006 (UTC) also, do I need to write some sort of release copywrtie thing like for images.

No need to add any copyright tag; since the program is in the text of the article, you have licensed it under the GFDL when you added it to the page. Schutz 12:03, 2 May 2006 (UTC)

Before everyone starts spending too much time writing programs in their favourite language, it may be a good idea to discuss what we need on the page... Personaly, I am not even sure if we need the explicit program to be part of the article; it is rather trivial and is well summarised in less than 2 lines of text in the section "How this works". In addition, the article is already quite long and dense. However, if the consensus is that this program is worth keeping, I'd suggest to follow Donald Knuth's practice (in The Art of Computer Programming) and describe it as an algorithm rather than as a specific implemtntation (and no, I am not suggesting to write it in assembly language...). Schutz 12:03, 2 May 2006 (UTC)

My vote is to drop the programs. They are trivial and add nothing to the article. Gandalf61 12:49, 2 May 2006 (UTC)

Please stop adding programs to the page. We are already up to 3 versions of the same program; do we really want this page to look like List of hello world programs ? I am waiting a little bit more since there has been only one comment above (thanks, Gandalf61 !), but if noone else comments, I will remove all the programs soon. Schutz 06:35, 3 May 2006 (UTC)

I agree with Schutz suggestion to follow Knuth's example. To that end, I replaced the three programs with C++/Javaish pseudocode, which is pretty much a standard (e.g., Crandall & Pomerance Computational Perspective). Anton Mravcek 17:39, 3 May 2006 (UTC)
Well, as I wrote above, I think we should get rid of the program (be it pseudocode or real code) altogether, as it is trivial and does not bring anything about prime numbers. My proposal was that if there is consensus to keep the program, then pseudocode is the best solution; for now, the only clear comment is from Gandalf61's, who agrees, so that the "consensus" leans towards removing the program. Schutz 11:32, 4 May 2006 (UTC)
Keep the pseudocode. And by pseudocode I mean a kind of language from which someone who doesn't know a programming language (like me) can understand the process step-by-step, and someone who does know a programming can create a program from the pseudocode just by adding the device-specific commands. Robert Happelberg 19:10, 4 May 2006 (UTC)
I agree. You would think it would be clear enough already, but just so that no one interprets the "concensus" to their liking, here goes: Keep the pseudocode. The implementation of Eratosthenes' sieve is a classic programming exercise. With pseudocode, this idea is presented without bogging down the page with dozens of programs in different programming languages. Anton Mravcek 22:30, 4 May 2006 (UTC)
Keep pseudocode. PrimeFan 22:52, 4 May 2006 (UTC)
But wouldn't it fit better on the page Sieve of Eratosthenes, then ? Because it is really about the sieve rather than about prime numbers per se. And the sieve article is pretty short, compared to this one. Schutz 23:17, 4 May 2006 (UTC)
Well, yes, right now it does make more sense in the sieve article. But I would like this page to also have a pseudocode for a more elegant algorithm, too. Also, so that we can tell those users who added programs that their additions to the page were not entirely in vain. Anton Mravcek 22:11, 5 May 2006 (UTC)
Do I understand it correctly that you are suggesting that a slow and stupid trial division algorithm, which used to be here before, is more elegant than Eratosthenes' sieve? I hope it's a joke. -- EJ 00:13, 6 May 2006 (UTC)
If you're referring to the algorithm that tried dividing each possible prime by the primes already in its list, then yes, you're right, that is less elegant than the sieve. But perhaps it's worth putting it in if you can show that that's what a great majority of programming students come up with first. What I was thinking of by a "more elegant" algorithm was something involving some kind of advanced math, like calculus. That would really benefit from being shown with pseudocode. Anton Mravcek 18:02, 6 May 2006 (UTC)
I'm sorry for my tone last night. I agree that trial division is the likely first attempt of most programming students, but I think that's an excellent argument for not putting it in the article: it would be redundant (as anyone will figure it out on his/her own), and it would reinforce the false impression that it is a good algorithm for the task.
As for more elegant algorithms: do you have anything specific on mind? I may be mistaken, but I'm afraid that humanity simply didn't invent enough algorithms for enumeration of primes to choose from. (Not surprizingly, as Eratosthenes' sieve has already almost optimal running time.) AFAIK variants of Eratosthenes' sieve were the canonical method of choice since ancient Greece until the end of the 20th century. Then Atkin and Bernstein discovered Atkin's sieve which cut the running time by a factor of O(loglogn), and that's it. I'm quite skeptical about putting in pseudocode for Atkin's sieve. The algorithm is rather complicated so a simple "implementation" in pseudocode may be infeasible, and more importantly, Schutz' remark still applies: the pseudocode would be more suitable for the sieve of Atkin article. -- EJ 20:58, 6 May 2006 (UTC)
I vaguely remember seeing an algorithm using integrals and rational approximation in a book a few years ago and thinking it was needlessly complicated. The sieve of Atkin seems refreshingly simple by comparison. Anton Mravcek 20:45, 8 May 2006 (UTC)

OK, so pseudocode for the sieve of Atkin is not that difficult after all. However, the current version in the article got it all wrong. Traversing the list of candidates and computing the number of solutions for each of them separately brings the running time back to O(n1.5), just like trial division, hence it is much slower than the sieve of Eratosthenes. It has to be done differently, I may try to fix it later. -- EJ 19:26, 9 May 2006 (UTC)

Done. Now it is O(n), but to make it actually fast would require a much more elaborate way of tracing those quadratics. I've omitted the elimination of numbers divisible by 5 (hidden in the congruences mod 60), as it is only a minor optimization by itself, it is irrelevant to the basic idea of the algorithm, and without it the lists of magic constants become much simpler. -- EJ 01:32, 10 May 2006 (UTC)
Very well done. I think I understand Atkin's sieve better from your pseudocode than from the explanation given in the Atkin article. PrimeFan 21:05, 10 May 2006 (UTC)

[edit] Truncatable primes

Just wondering: how can there be an even digit in any truncatable prime?

No problem if you are talking about a left truncatable prime, as long as the even number is not the last digit. To take a simple example, 23 is left-truncatable because it is prime and 3 is prime as well; the digit "2" is never considered alone. However, you are right in the case of right-truncatable numbers. All the best, Schutz 06:29, 3 May 2006 (UTC)

[edit] 1 as prime, history, and Gowers

For what it's worth the quote from (Gowers 2002) is wrong, mathematically. It may be a correct quote, but it's wrong. — Arthur Rubin | (talk) 23:38, 3 May 2006 (UTC)

Does anyone know the exact quote ? The statement in the article may only be an approximate paraphrase. As for the website about the arguments for and against the primality of 1, I don't think we should link to it. Some of the arguments are wrong (e.g. "The fundamental theorem says nothing about order"), and some are even indicated as such (e.g. the "pro" magic square argument), but are still kept in the list. Reading the page is interesting, but it is not something an encyclopedia should use as a reference. Schutz 06:50, 4 May 2006 (UTC)
If I were to have deleted the link, I probably would have violated 3RR by now. I hope moving it to a different section doesn't count as a revert. — Arthur Rubin | (talk) 18:33, 4 May 2006 (UTC)
Page 118 of the 2002 edition says: "The seemingly arbitrary exclusion of 1 from the definition of a prime ... does not express some deep fact about numbers: it just happens to be a useful convention, adopted so there is only one way of factorizing any given number into primes." Robert Happelberg 19:07, 4 May 2006 (UTC)
This does not look too bad to me (I have updated the reference in the text with the information); Arthur, what is the problem you alluded to above ? Schutz 19:43, 4 May 2006 (UTC)
The quote is OK, but the paraphrase doesn't reflect the quote.
The reason for the change in label is not that everything fits together better with the reclassification, but simply that it is slightly more convenient.
An accurate edit of the paraphrase might be:
The reason for the change in label is that concepts fit together better with the reclassification, adopted so there is only one way of factorizing any given number into primes.
— Arthur Rubin | (talk) 21:33, 4 May 2006 (UTC)
Done. Schutz 22:17, 4 May 2006 (UTC)
I don't mind deleting the link, but I don't want to start an edit war about that either. So, just like for the program, I'd rather get some consensus here about the general feeling of people before deleting it again — so far, I count two people against... any other opinion ? Schutz 19:43, 4 May 2006 (UTC)
If you can find a more rigorous exposition of the arguments, by all means delete the link to PrimeFan's page and link that instead. But I doubt you will, most people are too lazy to question what they were taught in school and ask why. Anton Mravcek 22:27, 4 May 2006 (UTC)
For what it's worth — I'm not going to revert your edit to the article, but the concepts of (unique) factorization, unit, and prime do fit together better with 1 not a prime. It's not just convenience. And some of PrimeFan's arguments (both for and against) are just wrong. The question of whether we want to link to incorrect web pages without warning is yet another question of WikiEthics. — Arthur Rubin | (talk) 22:40, 4 May 2006 (UTC)
Primefan's page is right enouhg for Neil Sloane's OEIS (see A008578)but Wikipedia is too snooty for it. I wonder if a colllege professor who grades her students down one full lettre grade for using wikipedia as opus cit would change her mind if she knew their was something called "wikiethics" .please.
what is sposedly wrong wiht teh page? Arthur Rubin's say so? that's enough? while we're at it let's accept his conjectures as theoremes. Numerao 17:13, 5 May 2006 (UTC)
I have pointed some of the errors in a comment above, but noone seems to have noticed that. Schutz 17:38, 5 May 2006 (UTC)
Yes, you have, and I'm grateful, it's more than what Arthur has done. You have pointed out one specific item that contained a mistake and I have adjusted it (the commutative property is what I was thinking of, not distributive). As for the prime magic square arguments, Bob presented me both arguments in that order. It reflects what Eric Weisstein says that "the number 1 is sometimes allowed in such squares." PrimeFan 20:41, 5 May 2006 (UTC)

[edit] How can I edit the Notes section?

As I open the edit window I just see '<references/>' inside.

To edit, say, note 2, find the paragraph in the article with that footnote number and edit that section. This might seem confusing but it has the advantage of allowing automatic renumbering of notes. PrimeFan 20:37, 21 June 2006 (UTC) P.S. I took the liberty of adding a "nowiki" tag to your comment.

[edit] Exploration of primes in other bases

I notice another question above about using other bases. I understand that of course primes are not base-dependent. However I would like to learn more about exploration of primes in other bases. Can someone recommend a place to visit to learn more (for a non-mathemetician who isn't afraid of math)? A couple things I'm wondering... First, does using base 15 (or perhaps 16? or 7.5?) shed any light on prime quadruplets? Second, does exploring non-integer bases shed any light on searching for patterns in primes? I'm sure mathematicians have explored this thoroughly, so I figure I might as well see what they found out rather than bashing my relatively-uneducated head against base conversions. Thanks! — Epastore 22:03, 22 August 2006 (UTC)

The integer bases where patterns would be most obvious would be the primorials (e.g. 6, 30, 210, etc.). You would notice, for instance, that in base 6, all primes except 2 and 3 end in 1 or 5, and in base 30 (using the letters A-T to represent the digits 10-29), prime quadruplets always end in {B, D, H, J} and the rest of the number to the right of first digit mod 7 is always 0, 3, or 6. But that's pretty basic stuff for anyone who's played around with prime numbers much. Hopefully someone else can give a more sophisticated response to your question. --Mwalimu59 22:22, 22 August 2006 (UTC)
Thanks for the input. I just wanted to point out that on further reflection, it occurs to me that since primes are a function of integers, using a non-integer base would change things pretty radically. Or would it? — Epastore 01:13, 23 August 2006 (UTC

[edit] Reasons for not promoting to good article

Hi all,

I have not promoted this article to the status of good article because I feel there are structural issues with the article. The article reads like a collection of information on prime numbers, not an article on prime numbers. My specific suggestions are to cut-down and focus the lead (for example, the ring theory and knot theory information could probably be placed elsewhere) and look at how to amalgamate some sections and remove other sections (Primes in pop culture could probably go altogether). Generally, try to get a good flow through the article and don't be afraid to leave some information out. Once you feel these issues have been addressed feel free to renominate the article.

Cedars 05:35, 19 September 2006 (UTC)

Thanks for the suggestions to improve the article. -Hyad 01:48, 21 September 2006 (UTC)

[edit] So-called Second Generation primes

I haven't seen this classification either, and am (was...) somewhat more familiar with classification- if one can call it that- by remainder modulo various powers of 2, generally speaking? Schissel | Sound the Note! 14:46, 5 October 2006 (UTC)

[edit] Talk page archiveing

This talk page is now over 100KB in size. Could someone who knows how please archive any inactive discussion. Tompw 14:30, 7 October 2006 (UTC)

[edit] Random series

It is often told that the prime numbers are randomly scattered over the naturals. Peahaps, anybody can elaborate what does it mean? Should there be a rule inducting whether the following n+1 number is prime or not? But we have such a rule. Does it mean that the test isPrime(N) must be somewhat (sub)linar O(N)? Is, for instance, the factorial series 1, 1*2, 1*2*3, ... a random one and what is the difference to the primes? Googling fot the meaning of "random", I have got this nice explatantion:

"It is evident that the prime numbers are randomly distributed but, unfortunately, we don't know what 'random' means." R. C. Vaughan (February 1990, [2])

--Javalenok 14:24, 15 November 2006 (UTC)

I think "random" here means more of a perception than a mathematical fact. Choose a random group of 50 consecutive integers. Half of those will be even and half will be odd. At least half will be composite. How many will be prime? Anton Mravcek 17:05, 15 November 2006 (UTC)
I haven't seen anything sensible about "randomness" of primes which is claimed proven by a reliable source and suitable for the article. And I haven't seen an acceptable (for me) formal definition of "complete randomness" which the primes might satisfy. However, there are many published plausibly conjectured properties one might expect from primes if they are "random", but all these put together are not enough (in my opinion) to call the set itself 'random' - I basically agree with R. C. Vaughan. The prime number theorem (PNT) roughly says a randomly chosen number around n has around 1/log(n) chance of being prime, but many definitely 'non-random' sets also satisfy that. There are many unproven conjectures based roughly on the thinking: "If we assume primes thin out as PNT but otherwise behave 'randomly' (e.g. has 1/log(n) chance of being prime independently of eachother, except for known patterns of prime factors), then there are probabilistic arguments that we would expect them to have certain statistical properties in the long run". These properties can e.g. be about the expected number of certain prime patterns, as in the broad Hypothesis H with quantification. I often search prime patterns and they usually behave approximately as I expected based on probabilistic arguments, but that proves nothing in general. PrimeHunter 20:00, 15 November 2006 (UTC)
The theory of algorithmic complexity defines randomness as infinite complexity, which corresponds to infinitely long program to describe it. But the algorithm discovering all the primes is quite finite. Indeed, the sequence of primes is not random, since using this algorithm we can always induce next prime.
//The primes generating algorithm
next_p: for p = 2 to infinity {
        for q = 2 to sqrt(p)
                if p mod q = 0 then
                        continue next_p;
        output(p);
}
The article Prime numbers not so random? in nature.com alludes the randomness to the lack of patterns. Indeed, more regularity means more patterns (or less patterns). Brrr. The less rules there are in the language including exceptions the simpler the language is the easier it is to figure out looking at its sentencies. Here, the grammar consisting of only one rule "there are no rules" is equivalent to infinite-rule (complex) grammar (like telling n natural is equivalent to n = 1,2,3,...). OK, peahaps by the randomness of a sentence they mean (im)possibility to figure out the grammar, the sentence-generating rule (looking at 2, 3, 5, 7, 11, ...)? --Javalenok 10:02, 21 November 2006 (UTC)
 n      | 1 2 3 4 5 6 7 8 9 10 11 12 13
 isP(n) | 1 1 1 0 1 0 1 0 0 0  1  0  1
G. Chaitin defines randomness via the algorithm complexity (size) generating the series [3]. I have shown in the previous post a simple algorithm generating the infinite sequence isP(n). Since such algorithm exists, the series is not random. What is wrong? --Javalenok 07:37, 7 February 2007 (UTC)
There are different definitions of "random", and the term is often used without a mathematical definition. Professional mathematicians have said things like primes "appear"/"seem" randomly distributed, so we shouldn't just dismiss it based on one definition of randomness. Assuming some level of randomness when working with primes often gives good results, e.g. when guessing the number of twin primes in an interval. The only "random" claim the article currently contains is:
"when looking at individual numbers, the primes seem to be randomly distributed, but the "global" distribution of primes follows well-defined laws"
I think that is acceptable: It says "seem" (implies a human perspective to me), it doesn't mention a randomness definition which the primes might fail, and sayings like this are common in reliable sources. The primes are exactly defined using finite space so they by definition fail some randomness definitions. Any well-defined notion of "randomness" would probably have to be formulated with primes in mind, in order to give the primes a chance of satisfying it. If the infinite sequence of primes has sufficiently many properties which have "heuristic probability 1" based on certain randomness assumptions, then calling them "randomly distributed" may be sensible. PrimeHunter 15:48, 7 February 2007 (UTC)

[edit] Twin prime conjecture

Is it not proved yet? I think this is already known. (???) Franp9am 00:50, 10 December 2006 (UTC)

It is not proved yet. Many amateur mathematicians claim to have proved it but their "proofs" are usually trivially false or nonsense. A few more serious mathematicians have also attempted to publish proofs with errors. No alleged proof satisfies Wikipedia:No original research and Wikipedia:Verifiability. See also Talk:Twin prime conjecture. PrimeHunter 03:04, 10 December 2006 (UTC)

[edit] Wording of section on Open Questions

My eyes landed on the following line in the article:

There are infinitely many Mersenne primes but not Fermat primes.

and was startled to see unresolved conjectures stated as fact . . . until I realized that I was reading from the Open Questions section, and that all declarative statements in this section are solely conjectures.

This misunderstanding leads me to think that it would be better to phrase all -- not just some -- of the Open Questions as questions, rather than declarative statements, to avoid future misunderstandings of this kind.Daqu 18:38, 20 December 2006 (UTC)

[edit] The Core

Should we mention that in The Core, one of the scientists is sent a coded message using prime numbers? This could go under the pop culture section. Bio 19:36, 20 December 2006 (UTC)

[edit] Executable prime numbers?

The current version of the Trivia section contains an astonishing statement: "Such numbers, when converted to binary and executed as a computer program, perform acts encumbered by applicable law in one or more jurisdictions." If they can indeed be executed as programs, this is quite strange and definitely needs a citation. More likely the text should say that the numbers will let you unlock the encryption, which is encumbered by law etc., or something to that effect. I leave it to someone who knows about this encryption to decide exactly what it should say. QuickFox 10:18, 18 January 2007 (UTC)

It's correct as it is, and I don't know why you think it's strange. See the illegal prime article for more information. --Zundark 13:47, 18 January 2007 (UTC)
Oops! My bad, I should have checked that link. Reading that it makes perfect sense. I've modified the description a little so the meaning becomes clearer. QuickFox 22:50, 19 January 2007 (UTC)
Retrieved from "http://en.wikipedia.org../../../p/r/i/Talk%7EPrime_number_6025.html"