Talk:Prime number/Archive 3

Archive 1

Archive 2

Archive 3

Archive 4

Archive 5

→

Archive 9

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

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)

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

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)

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

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.

This page

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

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)

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)

Polynomial log(N) deterministic

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

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)

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)

Cleanup of links

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

• C/C++ implementations of some well known methods to find primes. Search for 'prime' in www.tekpool.com

Nothing an average CS student cannot do in an hour.

• Prime curios at the prime pages

Duplication.

• Online Prime Number calculator

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

• The "PRIMES is in P" FAQ

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

• List of largest known probable primes

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

• The Prime Number Shitting Bear

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.

• Prime Factorization Worksheet generates new questions every time the page is loaded

Nothing noteworthy.

• Prime Spiral pattern (Wolfram)

One link on the prime spiral is enough.

• 12 digit primes Known 12-digit prime factors of Googolplex - 1

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

• PHP Prime Number Calculator PHP Prime Number Calculator script. Goes until PHP overloads:)

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:

• The Music of Primes

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)

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 = i⁵, 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