Talk:Prime number/Archive 4

This is an archive of past discussions about Prime number. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page.

Archive 1

Archive 2

Archive 3

→

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)

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)

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)

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)

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)

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.—Preceding unsigned comment 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)

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)

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 — p₁, p₂, p₃, …, p_m (in increasing order). Then, the Euclid number n = p₁p₂p₃…p_m + 1 gives a remainder of 1 when divided by each of the given prime numbers p_i, 1 ≤ i ≤ m. Therefore, n is either a prime number or n is divisible by some other prime number greater than p_m. 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 — p₁, p₂, p₃, …, p_m — 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 = p₁p₂p₃…p_m + 1 is not a multiple of any of the presupposed prime numbers p_k, (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 p_m 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 = p₁p₂p₃…p_m (which is greater than 2 and divisible by each of the given prime p_i) and k - 1 (which is greater than p_m so, by the assumption, it is not a prime number) --- hence, both k and k - 1 are divisble by some prime p_i 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)

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)

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(\log \log n)

, 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(n^{1.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)

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)

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 OEIS: 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)

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.

applications

the first paragraph

Removal of Number Template

About the incomplete totality of the set of all prime natural numbers

Formulas yielding prime numbers

Primes in Nature

Properties

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

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

Grammar

Program

Truncatable primes

1 as prime, history, and Gowers

How can I edit the Notes section?