Wikipedia

Talk:Prime number/Archive 9

< Talk:Prime number
Latest comment: 6 months ago by LandonL in topic set of potential primes > 7
Archive 5←Archive 7Archive 8Archive 9

Improving towards Good Article criteria

Latest comment: 6 years ago17 comments6 people in discussion

Please discuss what changes are necessary for this article to achieve GA status.

My thoughts:

  1. Well written
    1. Prose, spelling grammar: acceptable
    2. Manual of style guidelines
      1. More consistency in the markup for mathematical notation is needed
  2. Verifiable
    1. Reference list: yes
    2. Reliable sources: yes
    3. No original research: yes
    4. No plagiarism or copyright violations: unsure
  3. Broad in its coverage
    1. Addresses the main aspects: in my opinion, yes
    2. Does not go into unnecessary detail: some work could be done
      1. It is in my opinion that this article is on the border of going into too much detail
      2. The second half to section 5.4 seems out of place. Perhaps the search for primes could be its own section or subsection
  4. Neutral: yes
  5. Stable: yes
  6. Illustrated
    1. Contains images: yes, nine
      1. Article lead: Demonstration that 7 is prime
      2. Section 1: Demonstration that 12 is composite and 11 is prime
      3. Section 3: Sieve of Eratosthenes animation
      4. Section 6.2: Plot of the prime counting function
      5. Section 6.3: Illustration of an arithmetic progression with modulo 9
      6. Section 6.4: Ulam spiral illustration
      7. Section 6.4: Table illustrating a Ulam spiral
      8. Section 7.1: Plot of the Riemann zeta function
      9. Section 8.2: animation of the construction of a pentagon
    2. Images are tagged with copyright status: yes to all
    3. Images are relevant and captioned: some work needed
      1. Images 1 and 2 could possibly be re-ordered considering Image 2 demonstrates that 12 is composite, and both prime and composite numbers are defined in the article lead
      2. Image 3 could possibly be moved to the Sieves section
      3. Caption to Image 4 could be improved (e.g. what conclusion can we make from the comparison of these three functions?)
      4. Image 5 has no caption
      5. Not sure if both Images 6 and 7 need to be included. At the very least, it would be preferred if Image 7 were an actual image and not a table of numbers.
      6. Caption to Image 8 could be improved (e.g. what does this plot tell us about prime numbers?)
      7. Caption to Image 9 could be improved (e.g. why is this animation relevant to Fermat primes, or prime numbers in general?)

Derek M (talk) 23:01, 8 January 2018 (UTC)

There need to be some typesetting improvements. Formulas that are set apart should generally be done in <math>...</math> mode, while inline formulas can be either way depending on what's needed, but it should be consistent between either plain wiki markup (i.e., ''n'' giving n), or template markup (i.e., either {{mvar|n}} or {{math|''n''}} giving n). I'm not crazy about {{math}}, but it's probably better than the alternative. There's also some inconsistency between showing multiplication with a dot or with a cross; personally, I think a dot should be used. That was just a quick glance, I'm sure there's more. –Deacon Vorbis (carbon • videos) 23:30, 8 January 2018 (UTC)
I guess it seems that such considerations don't seem to affect GA status, but I think they're fairly important for a math-heavy article. –Deacon Vorbis (carbon • videos) 23:36, 8 January 2018 (UTC)
It's in pretty good shape, but I think some topics that should be mentioned in the lead aren't (notably the entire history section and the Riemann hypothesis subsection). Re the math formatting: I don't have strong opinions between <math> and {{math}}, but I prefer either of them over plain wiki markup because I think it's important for variable names to have close to the same appearance in inline formulas as they do in displayed formulas. Additionally, whichever way we end up going on this we should aim for more consistency than we have now. Another area where we should try to be more consistent is reference formatting. Currently we have some references given in their entirety in a footnote, some given by a short {{harvnb}} footnote pointing to an entry in the references, and some expanded in inline text (e.g. Euclid's "Book IX, Proposition 20"). Also, in a GA review, we are likely to get dinged for having many sentences (at the ends of their paragraphs) and some entire non-lead paragraphs without sources. —David Eppstein (talk) 00:12, 9 January 2018 (UTC)

I have added the math notation suggestions to my list above.

Can you explain in further detail what you mean by "some topics that should be mentioned in the lead aren't (notably the entire history section and the Riemann hypothesis subsection)"?

I don't have prior experience in assisting improving an article to GA status, so I can only compare this article to other Top Importance, GA mathematics articles like Derivative. I've noticed that the lead to Prime number goes into much more detail than the other article's lead. Additionally I think it is a bit disorganized in comparison. This is what it looks like now:

  1. Definition of prime and composite. Example. Role in number theory (fundamental theorem of arithmetic). 1 is excluded.
  2. Primality: Trial division, faster algorithms e.g. Miller-Rabin, AKS. Faster algorithms for primes of special forms. Size of largest known prime.
  3. Infinitely many primes. No known formula that separates primes from composites. The distribution of primes can be modelled. Prime number theorem.
  4. Open questions: Goldbach's and twin prime conjecture. Questions of primes have lead research in other fields. Uses for large prime numbers in technology e.g. cryptography. Uses in algebra.

Some things that could improve the lead:

  • The last part of paragraph 2 seems out of place for that paragraph. This should probably be moved to its own paragraph along with the "Uses for large prime numbers in cryptography" part of paragraph 4.
  • Some sort of "why is this important?" conclusion to paragraph 3 would be useful. For example, it is interesting that there are an infinite many primes because you'd expect they'd continue to get rarer and rarer and eventually we'd "run out"

Additionally, my area of interest is in distributed computing and thus in my opinion I think this article would benefit from a section dedicated to the search for large primes. Derek M (talk) 14:58, 9 January 2018 (UTC)

This article also has some stale cleanup tags and associated categories: Articles with dead external links from May 2011; Articles with unsourced statements from August 2015; Wikipedia articles needing clarification from June 2011; Articles containing potentially dated statements from February 2011; Articles with specifically marked weasel-worded phrases from June 2014. All these need to be cleared up before it can be nominated for GA (they would be cause for immediate failure under the GA rules). —David Eppstein (talk) 08:02, 11 January 2018 (UTC)
 
How about this new image instead? —David Eppstein (talk) 04:32, 19 January 2018 (UTC)
  • Maybe I am fully off track with my suggestion to find a better top-right image for this article. Even the boring "primes within 1 to 100" seems to me more appropriate than the current, dubious commercial for Cuisinaire Rods®, which to my perception are innately unable to demonstrate any prime property. They just demonstrate the PR-abilities of someone pushing C. Gattegno, and his idiosyncratic methods to success in popularity about teaching methods with these rods and his Silent Way, possibly mostly based on mass material in WP. Purgy (talk) 12:20, 18 January 2018 (UTC)
    • I agree. I'm also not entirely happy with the Eratosthenes animation. It colors an initially monochromatic square, but what do all the colors mean? Has anyone checked whether the colors meet our accessibility standards? And what do the two different dimensions mean, when the sequence of integers is only one-dimensional? I think File:Eratosthenes sall.jpg (pixelated as it is) is far clearer. —David Eppstein (talk) 01:11, 19 January 2018 (UTC)
I actually like the image we currently have (of course, we should absolutely avoid referring explicitly to commercial material, though). IMO, David's image (which looks nice visually!, what about 1 though?) primarily visualizes composite numbers. Then we would have to say in words (e.g. the image caption) that primes are the numbers which are not composite. The image with the rods (or some other equivalent visualization) has the advantage of directly showing that a certain number is a prime, which is the most immediate task of the article (and its lead). It also gives an opportunity to refer to it later in the text, when discussing elementary primality tests. Jakob.scholbach (talk) 08:08, 19 January 2018 (UTC)
What the current image actually shows (I think) is a highly non-optimized version of trial division that goes all the way up to n-1. I don't see how that's a clear demonstration of the definition. —David Eppstein (talk) 08:21, 19 January 2018 (UTC)
 
another option Jakob.scholbach (talk) 08:31, 19 January 2018 (UTC)
On a partly independent note, I suggest to avoid the word "divisor" in the article lead, at least in the first sentence. It is unnecessary jargon here. I believe the target audience for the article lead, at least partly, can be a 10 year old kid. So the sentence
For example, 5 is prime because 1 and 5 are its only positive integer divisors, whereas 6 is composite because it has the divisors 2 and 3 in addition to 1 and 6.
should be reworded, IMO, to something like:
5 is prime because it cannot be written as a product other than 5 * 1 or 1 * 5, whereas 6 is the product of 2 * 3 (in addition to 1 * 6), and therefore is compiste.
Do you agree? If yes, and if our goal with the image is to illustrate the definition, then the image is just fine. And yes, of course it is suboptimal, but this is not the point in the lead.
How do you like the image on the right? Jakob.scholbach (talk) 08:31, 19 January 2018 (UTC)
I agree with both the intended level and the specific complaints about "divisor" and have edited along the lines you suggest. I think, by the way, that "×" is probably more recognizable to a 10-year-old as a symbol of multiplication than either "*" or "·", so I have used that notation — opinions on that? —David Eppstein (talk) 19:12, 19 January 2018 (UTC)

(edit conflict) I prefer the current image on Eratosthenes and suggested an explicative caption. David Eppstein's suggestion is certainly more compact, but I am in doubt if the small upper bound suffices to make the mechanism obvious to beginners. Additionally, I am not willing to sacrifice indisputable advantages (e.g.: colors) in favour of some irrational inclusion missions. In principle, I share a certain reluctance to animated diagrams, they should at least be stoppable, but their didactic power is not negligible. I was not bold enough to exchange the top images, but I certainly prefer David Eppstein's suggestions. The reservations regarding 1 and 2 are imho covered by the dimensionality argument: both have simply only one-dimensional arrangements (in arbitrary directions). OTOH, I do not see why obviously commensurable rods (if not in inch, perhaps in mm) should be able to introduce a rigorous notion of primes, not plagued by misleading analogies.

The suggestion by Jakob.scholbach does not show the connection to primes like David Eppstein's does.

I share the opinion of "divisor" being jargon, but "evenly divide" is elementary accessible. Dis-proving any existence is hard, and taking care of non-commutativity is excessive, so my suggestion (introducing the jargon at the end) is 

5 is prime because it is not evenly divisible besides by 1 and 5, whereas 6 is composite for being evenly divisible by 2 and 3, additionally to the obvious trivial divisors 1 and 6.

Addendum 08:53, 19 January 2018 (UTC)Purgy (talk) 08:43, 19 January 2018 (UTC)

The colored animation has some irritating features: when a new prime is added, its multiples with the existing primes are not colored, whereas its other multiples for which it is not the smallest factor are colored. For example, when 3 is added, 6 is not colored but 12 and 18 are; when 5 is added, 10 and 15 are not colored but 20 and 30 are. This seems hard to justify, would be difficult to explain in the caption, and is not currently explained correctly in the caption. --JBL (talk) 12:59, 19 January 2018 (UTC)
As I see it, re-marking numbers only happens for the square and higher "already marked multiples above the square" correction 16:11, 19 January 2018 (UTC) of the prime in consideration. So for 3 all multiples above and including 3x3=9 are colored in green (not 6), and for 5 all multiples above and including 25 (not 10, 15 and(!) not 20) are made blue. Accordingly, 56, 63, 70, 84, 98 and 105 are recolored in the course of dealing with 7, but not 14, 21, 28, 35, 42. This seems to be quite reasonable, and my suggested caption might not be exhaustive, but I do not think it is incorrect. Purgy (talk) 15:06, 19 January 2018 (UTC)

Thoughts about the new lead image

Latest comment: 6 years ago7 comments2 people in discussion

I suggest to get rid of one of the alternative factorizations of twelve, and just keep either 2x6 or 3x4. This would allow for a narrower pic (keeping 3x4 even more), and the factorizations are not exhaustive, anyway.

Adjusting the colors to the sieve-image (primes in magenta, 3-rows in green, ...) and narrowing the vertical space between "prime" and "composite" are overrun finesses, but maybe easy to do for sages (hint, hint ... :) ) having opened the file in an editor.

For the caption I'd like to read something about the number of dots in one row and the number of dot-rows representing the two "smaller numbers" in the "product", making up the considered number, e.g., something like this: 

 ..., the prime numbers are the ones that cannot be expressed as the product of two smaller numbers, one factor given by the number of dots in a row, the other by the number of dot-rows.

The caption I consider as quite appropriate to change, but the image changes are grain size. Purgy (talk) 11:57, 20 January 2018 (UTC)

The image colors are deliberately chosen from a restricted palette that I have been using from User:KSmrq. I have checked them with a color blind friend and found them to be highly distinguishable from each other, even for the color blind. If you want to use the sieve image colors instead, can you provide some evidence that they meet MOS:CONTRAST? —David Eppstein (talk) 18:19, 20 January 2018 (UTC)
To follow up on this, I checked the contrast of some of the color pairs of the sieve image against MOS:CONTRAST "Ensure the contrast of the text with its background reaches at least Web Content Accessibility Guidelines (WCAG) 2.0's AA level, and AAA level when feasible" using the tool at https://snook.ca/technical/colour_contrast/colour.html#fg=000000,bg=99C0F8 . The black-on-blue (3238C6) used for #5 is not compliant at any level. The black-on-red (BE3F3B) used for #2 is compliant only at the AA level, and only at font sizes of 18+ (not true for this image). And the black-on-magenta (BD45C6) used for larger primes is compliant for AA, but not for AAA at small font sizes. The same is true for the black-on-lighter-blue (6D73D7) used for multiples of five, and the black-on-lighter-red (CF7571) used for all even numbers. I didn't check whether the pairs of lighter colors that are supposed to contrast with each other are also distinguishable from each other (because the tools is intended to check contrast of text on background, not of contrasting color fields) but I suspect not. If we consider that the text in the image is not really a pure black because of its anti-aliasing, the situation becomes even worse; using the color of darkest pixel I found in the gray-on-black text gives 30322F-on-BBBBBB, also not compliant at AAA for small font sizes. In conclusion, this image does not appear to pass MOS:CONTRAST and should not be used as guidance in creating other images. —David Eppstein (talk) 20:48, 20 January 2018 (UTC)
I almost feel like apologizing ... Certainly, I did not want to have the colors of the sieve pic as a guidance. I just thought them to be way harder to change, compared to the (perfectly selected) colors of the lead-pic. I came to mention the colors just because I was dragged myself to consider them in detail. At first sight I did not notice myself the slight difference in coloring the primes and their multiples. Nevertheless, even given all the detrimental color/contrast properties, I would not expunge this image (it was once featured?) without some substitute.
The reason for asking for a narrower image was triggered by the high share of whitespace in the whole image, which could be reduced by trimming at the right (after removing the 2x6 dot-block) and, perhaps between prime/composite.
What do you think about a more explicative caption? Purgy (talk) 11:25, 21 January 2018 (UTC)
Anyway, I've tightened the image. Better? I think there's definitely room for improvement in the caption but the aim should be to work better for the target 10-year-old audience for the first paragraph of the article rather than to be more explicative. —David Eppstein (talk) 19:58, 21 January 2018 (UTC)
- Not only the layout of the lead image is now perfect, but also the colors are so, imho. Depicting all composites in one color not only fits to the heading, but also takes out any inappropriate hint to any prime number. I revised my original stance.
- Re the caption, I still think that being explicit about the factorization in two smaller numbers within the pic supports intuitive understanding by the targeted readership. E.g., like so?
...  not products of (at least) two smaller numbers, like is shown by the quadrangles for composites.
- Re Ishango bone: may I suggest to reconsider engraved vs. included?
- Re Rhind papyrus: I came to insert just this pic, because the current one is sort of ubiquitous in references, and I looked for an attractive, mathy looking image. In fact, I inserted both pics to the History section to make some soft science noise (Paleolithikum, Rhind) and create optical wellbeing.
Please, do not assign any significance to my opinion beyond your own considerations, it's just my desire to explain myself that makes me look so insistingly. Purgy (talk) 08:21, 22 January 2018 (UTC)
I would support changing the current image of the papyrus to one that showed part of its table of 2/n Egyptian fraction expansions, if you want to find and upload one. (I don't think there should be a problem with copyright.) The issue was merely that the other image was from a part of the papyrus that had nothing to do with prime numbers. —David Eppstein (talk) 20:04, 22 January 2018 (UTC)

Removal of unsourced applications

Latest comment: 6 years ago3 comments2 people in discussion

It became a well acknowledged factoid that trivial facts are hard to source soundly. I think that the coprime numbers of teeth on on gears within a gearbox is such a fact within engineering, as is the selection of checkdigits for accounting numbers, according to their properties wrt excluding zero divisors which leads to primes, among bankers. So I think that the removal of the parts referring to these topics in the Applications section is a bit harsh. Maybe these mentionings generate interest within a casual readership, and, imho, they are appropriate within this article for this reason. Not shooing away any good sources! To be honest, I am more bored by the abundance of (non-famous) conjectures about prime gaps. Purgy (talk) 08:37, 24 January 2018 (UTC)

Checkdigits rely on the specific properties of the numbers 10 and 11, not on primes more generally. Gear ratios are a possibility, though, if more substantial sourcing can be found. In any case, some thought should go into the overall structure of the article rather than shoving things in where they sort of fit. I'm not at all certain the current structure is right, but with the current structure those topics were part of the top paragraph of a section with subsections, whose content should have been purely a summary of those subsections. —David Eppstein (talk) 08:48, 24 January 2018 (UTC)
I admit not to be a (math) purist when stating my above opinions, but I do have some sexyness of articles in mind (imho, "prime gaps" are unattractive, "gearboxes" and "accounts" appeal to certain user groups, as do words like "skin")[citation needed] ;). I also do not want the least to revert the specific edit, or to remove some conjectures, I just humbly dare to invest in some PR and (as said) make unscientific, soft sciency noise. Purgy (talk) 09:21, 24 January 2018 (UTC)

Suggestions on structure

Latest comment: 6 years ago1 comment1 person in discussion

- Placing "History" as first section.
- Including "Primality of one" into the History section, since the debate about it seems to be settled.
- As a consequence of above, re-title the heading to "Factorization" and include "Integer factorization", including the associated complexity remarks, and perhaps hinting to the Generalizations for non-unique factorizable constructs. This would lead to one more new heading "Testing primality".
- Shifting also the clumsy "Number of prime numbers" in to this "Factorization" paragraph, motivated by not only the naturals being infinite, but also their necessary factors.
- "In games, arts, and literature" could find a place under "Applications".
Just my two cents. Purgy (talk) 14:56, 29 January 2018 (UTC)

Complete?

Latest comment: 6 years ago7 comments2 people in discussion

Ok, I've completed a pass over the entire article, working to make the sourcing complete and avoid unnecessary technicality. Opinions on whether it's now in shape for a GA nomination or whether additional work (e.g. major restructuring to make the section order more logical) would be a good idea first? —David Eppstein (talk) 20:42, 27 January 2018 (UTC)

It looks OK for a GA nomination to me. XOR'easter (talk) 23:11, 27 January 2018 (UTC)
Whoops! I wiki-linked "place" to the wrong, er, place. But I do think it should be linked somewhere, both to parallel the other terms in that sentence and to provide further information about one of the more opaque terms I've seen in a while. Maybe the target should be Absolute value (algebra)#Completions? XOR'easter (talk) 23:57, 27 January 2018 (UTC)
I left it unlinked because I thought that complete field immediately following it in the same clause was the correct target, and had a link already. —David Eppstein (talk) 00:30, 28 January 2018 (UTC)
I've gone ahead and made a GA nom. We can continue dealing with minor issues like the link discussion above (which I don't want to cut off prematurely) while we wait for a reviewer. —David Eppstein (talk) 04:48, 28 January 2018 (UTC)

Having gone away for a bit and now read over that section again, I think I'm basically fine with it as written. I had a general sense of disquiet with the way the term place was introduced, I think because it is a very ordinary word being used in a technical way for which the everyday sense is not really an indicator. Instances of that often distract me and make me wonder just how that word ended up with that meaning. Is the connection obvious to everyone but me? Is it a literal translation of a nineteenth-century German word applied when the subject was understood less than it is now, kept on for historical reasons? Is this a case like magma, where nobody really knows what Bourbaki were thinking, but we have some sensible lexicographic guesses? XOR'easter (talk) 18:35, 30 January 2018 (UTC)

My folk etymology is that a place is where something local happens in the local–global principle. "Locale" and "localization" were already taken for other meanings. I think the term is due to Weil. "Prime" has a common everyday English meaning, too, roughly synonymous with "first". I wonder how it acquired its number-theoretic meaning? —David Eppstein (talk) 19:02, 30 January 2018 (UTC)

GA Review

Latest comment: 6 years ago134 comments5 people in discussion
GA toolbox
Reviewing
This review is transcluded from Talk:Prime number/GA1. The edit link for this section can be used to add comments to the review.

Reviewer: Jakob.scholbach (talk · contribs) 14:44, 28 January 2018 (UTC)


I will review the GA nomination in the next few days. Additional reviews welcome! Jakob.scholbach (talk) 14:44, 28 January 2018 (UTC)

I really like this article and I think it meets the 6 good article criteria. Heck why not nominate it for featured article status? Since one of the primary contributors of this article is Professor User:David Eppstein who is himself a reliable source of information, I would support the nomination directly to featured article status. Brian Everlasting (talk) 19:52, 28 January 2018 (UTC)
From previous experiences with FA, I am not sure that hasting to an FA nomination is a good idea. Anyway, it is a pleasure to review this article, which is already in a very good shape. Jakob.scholbach (talk) 20:45, 31 January 2018 (UTC)

General remarks

All comments addressed Jakob.scholbach (talk) 12:59, 13 February 2018 (UTC)
  • The formatting of mathematical symbols is highly inconsistent, mixing wiki markup, <math> markup and {{math|...}} markup in a seemingly random way. I personally like to have wiki markup wherever this does not lead to a sacrifice in formatting (this includes the large majority of expressions in this article), and <math> markup when this is not possible. In any case, a more uniform presentation is desirable, beginning in §1. Jakob.scholbach (talk) 20:45, 31 January 2018 (UTC)
    • I thought I had been doing this in my pre-nomination pass over the article, consistently using <math> because it is the only markup capable of supporting all the expressions in the article. I see that after I had done this, some other users including Derek M went back through and made it inconsistent again. Boo! And thanks for catching this. Anyway, the {{math}} should be gone again now. I also found a little more opportunity for removing notation altogether, the better approach (because less technical) when it can be accomplished. —David Eppstein (talk) 21:27, 31 January 2018 (UTC)
  • The referencing seems to be highly detailed. While I appreciate this in general, this high number of references disturbs the reading flow, IMO. In some cases it might be better to move the references at least to the end of the phrases? E.g. in the first paragraph of §1, but also elsewhere. Jakob.scholbach (talk) 20:45, 31 January 2018 (UTC)
    • Uh. What? You are saying that, when specific claims are supported by specific citations, we should instead just put a catchall citation at the end of that piece of material and let the readers figure out which sources go with which claims? Taken to an extreme, this would mean having a bibliography at the end and no footnotes. Is that really what you mean? And can you explain which GA criterion you are interpreting as justifying this request? —David Eppstein (talk) 21:27, 31 January 2018 (UTC)
Yes, exaggerating my comment to the extreme makes it absurd. My point is just that in some cases we have references for utterly elementary and non-controversial facts. While, again, I appreciate your intense work on the references, I feel we are on the border of overdoing it. Since you gladly often even provide google links to the books, it is not at all hard to find the intended reference, if we put them at the end of the sentence. This is for the readers who doubt certain statements in the article. For those who just want to read more, most readers will use a book etc. of their choice to learn. So, while adding more and more references gives a certain plus, it also has a marginal negative effect when it comes to readability.
Anyway, I don't want to make a big point here; maybe just keep it in mind in case you add further references. Jakob.scholbach (talk) 22:40, 2 February 2018 (UTC)

Definition and examples

All comments addressed Jakob.scholbach (talk) 12:59, 13 February 2018 (UTC)
  • What is the motivation to print the primes up to 1000? Either the list could be shrinked, or at least be used to illustrate some more content. E.g. the notion of a twin prime could be illustrated here, or the notion of a prime gap. A glimpse of the distribution of primes could also be illustrated here. None of this is mandatory, though, but just the bare list is a bit dry. Jakob.scholbach (talk) 20:45, 31 January 2018 (UTC)
    • I think the motivation is that readers expect to see a list of primes in this article (though not as detailed as list of prime numbers) and that 1000 is a nice round number. But it would be reasonable to shorten the list, for instance to 100. I'd prefer to keep the concepts very simple here rather than talking about prime gaps, though, which even some of our regular editors on this article have complained about as being too technical a concept. And I don't know what you mean by "A glimpse of the distribution". An illustration? Of what? —David Eppstein (talk) 21:33, 31 January 2018 (UTC)
re distribution: (If we keep the list up to 1000:) I was thinking of pointing out: there are ... primes less than 100, ... less than 1000 and maybe refer to later in the article when the prime number theorem is stated. Or alternatively, refer back to the top in the § on the prime number theorem.
In case I was unclear, I should say I am not totally opposed to having a little longer list, but I would suggest to "use" it more in the article. Jakob.scholbach (talk) 13:03, 1 February 2018 (UTC)
  • " Therefore, the prime numbers other than two are all odd numbers. They are often called odd primes." -- Is there a wording which avoids the possiblilty of mixing "They" with "all odd numbers". Also, why "often"?
  • Algorithm: Pr = (6n+1) and (6n+5); but Pr ≠ {(6n+1)k • (6n+5)m} Csikoszi 23:10, 7 February 2018 (UTC)
This is the simplicity of prime numbers.Csikoszi 09:47, 8 February 2018 (UTC) — Preceding unsigned comment added by Csikoszi (talk • contribs)

Unique factorization and primality of one

All comments addressed Jakob.scholbach (talk) 12:59, 13 February 2018 (UTC)
  • I feel the importance of the fundamental theorem of arithmetic should be stated more strongly?
    • It used to say "crucial" but I took that out as an unsourced editorialization. We would need a source for such an editorialization. They probably exist, but did you have one in mind? —David Eppstein (talk) 22:36, 31 January 2018 (UTC)
      • Barry Mazur, in §IV.1.4 of the Princeton companion to mathematics, writes:
The fundamental fact that any ordinary integer greater than 1 can be uniquely expressed as a product of (positive) prime numbers (that is, that Z enjoys the unique factorization property) is crucial for much of the number theory done with ordinary integers. That this unique factorization property for integers actually required proof was itself a hard-won realization of Gauss, who also provided its proof (see the fundamental theorem of arithmetic [V.16]).
(If you search through the book [email me if you want a pdf], there are a bunch of other statements along these lines.) Another way to testify its importance is to refer to it later in the article: in Euclid's proof, also in the discussion about ζ(s). Jakob.scholbach (talk) 13:03, 1 February 2018 (UTC)
  • I added back a different adverb "central" which I think conveys the meaning and looks less like hyperbole than "crucial". I left it unsourced, though, to avoid contributing to the proliferation of many sources for small details that you were complaining about. And it is now mentioned in Euclid's proof, and was long since mentioned wrt the product formula for zeta. —David Eppstein (talk) 18:14, 1 February 2018 (UTC)
  • The wording with "prime factors" and wikilink is not optimal: the link goes to divisor! Can the term "prime factor" be introduced less implicitly? Maybe also restructure: first the example 23244 = ..., then refer to the terms as prime factors. Then state the theorem?
  • The coexistence of the fundamental theorem of arithmetic and the primality of one in one § is odd, IMO. The former is a cornerstone of maths, the latter a historic oddity, which IMO takes way too much space in this article. The § about primality of 1 should focus on the key points, which are that the notion just becomes inconvenient otherwise, e.g. in the fundamental theorem. Parts of this should go to the history section. Precisely identifying the last professional mathematician to call 1 a prime is pointless, IMO.
    • Primality of one section moved in its entirety to become a subsection of history (and shortened a little by removing the incorrect factoid about the last mathematician and its refutation) and the fundamental theorem promoted to be a whole section rather than a subsection. —David Eppstein (talk) 05:04, 1 February 2018 (UTC)
      • The move is good, but I still think the content-length ratio of that § is low. E.g. "In the 19th century many mathematicians still considered the number 1 to be a prime.[43] For example, Derrick Norman Lehmer's list of primes up to 10,006,721, reprinted as late as 1956,[44] started with 1 as its first prime.[45]" -- the second sentence does not seem to be an "example" of the first (19th vs. 20th century). Also, the level of detail is excessive, naming the list itself is hardly relevant, nor is the number of primes in it. I will comment again in more detail when I read the history section. Jakob.scholbach (talk) 13:03, 1 February 2018 (UTC)
  • The wording "began to arrive at the consensus that 1 is not a prime number," is not optimal, I would say "that 1 should not be regarded a prime number" -- after all these are just definitions.

History

All comments addressed Jakob.scholbach (talk) 12:59, 13 February 2018 (UTC)
OK, I don't have a preference either way, just wanted to make sure the term is not connotated in any way in our context. Jakob.scholbach (talk) 21:33, 4 February 2018 (UTC)
  • "The next significant developments took place" -- this sounds a bit too general to me; maybe something like "The next significant development in the understanding of prime numbers..."?
    • Ok, yes, probably the Protestant Reformation was a significant development, but surely readers of the article can be expected to understand that this article is about prime numbers? —David Eppstein (talk) 20:08, 4 February 2018 (UTC)
Yes, we can expect that. I was trying to make a point that the sentence is quite generic and not too precise (17th and 18th century, why not also 19th?). I don't want to dig in my heels here, but I think the sentence could either be removed (maybe add "French mathematician" next to Fermat if you want to emphasize the geographical shift), or made into a somewhat sharper statement. Jakob.scholbach (talk) 21:33, 4 February 2018 (UTC)
Ok, removed. It was just a transitional sentence and the paragraph works well enough without it.
  • Did Alhazen phrase things really in terms of (n-1)! \cong (-1) mod n? If not (which I suspect), it would be worthwile to clarify this. From my superficial experience with other pieces of history of mathematics, these early insights were often formulated much less clearly than modern notation suggests.
    • My guess would be something more like (n-1)!+1 is divisible by n. But I haven't read Alhazen in the original and the source doesn't specify. I was trying to write the theorem clearly and concisely, leaving the precise details to the linked article on Wilson's theorem. —David Eppstein (talk) 20:08, 4 February 2018 (UTC)
Yes, I would also guess that. Should we than just state it this way? Or maybe write "characterizing the prime numbers, in modern notation as the solutions to the equation ..." Jakob.scholbach (talk) 21:33, 4 February 2018 (UTC)
The divisibility formulation isn't really any longer or trickier, and this isn't part of the section on modular arithmetic where the choice of congruence vs divisibility would matter, so why not just state it that way? I changed it to use divisibility. —David Eppstein (talk) 04:46, 5 February 2018 (UTC)
Good: [probably] historically more accurate, and also simpler to understand for the modern reader. Jakob.scholbach (talk) 08:10, 5 February 2018 (UTC)
  • I miss some sort of general statement what kind of methods were used in the historical development: is it true that people before Euler mainly used elementary combinatorial means and that Euler reshaped the field by bringing in analytic methods?
    • That seems a fair summary of the theoretical side to me but I'd have to find a source for it. And there was a lot of more elementary work later, on the primality testing and factorization method side of things. —David Eppstein (talk) 20:08, 4 February 2018 (UTC)
      • I added that Euler "introduced analytic methods" (I think that's clear enough without a source though if you want me to I'm sure I can find one), and reordered the list of Euler contributions to put the Euler–Euclid theorem on the pre-analysis side of things (since his proof is elementary) even though I think chronologically the analysis came earlier. —David Eppstein (talk) 04:42, 5 February 2018 (UTC)
OK, good. Now "He introduced methods from mathematical analysis to this area in his proofs of the infinitude of the primes and the divergence of the sum of the reciprocals of the primes" -- maybe reword as "He introduced methods from mathematical analysis to this area to show the divergence of the sum of the reciprocals of the primes and thereby the infinitude of primes"? Jakob.scholbach (talk) 08:10, 5 February 2018 (UTC)
That's actually a little inaccurate. In the same work, Euler gave two different analytic proofs of the infinitude of primes (both of which we discuss at different points in the article): one involving the Euler product formula for the sum of reciprocals of all positive integers (zeta(1)), and the other involving the sum of reciprocals of only the primes. —David Eppstein (talk) 08:17, 5 February 2018 (UTC)
OK, I take it back then. Thanks Jakob.scholbach (talk) 08:20, 5 February 2018 (UTC)
  • "More recent algorithms like" -- aren't these post 1950? If so, the wording should reflect the timing a little more precisely.
  • "have been found by computers " -- maybe have been found using computers?
  • "Plato, Aristotle, Euclid, and a majority of the other Greek mathematicians" -- are Plato and Aristotle considered mathematicians in the scholarly literature?
  • It is entirely clear to me that Euler didn't consider 1 a prime, since otherwise the Euler products fail. I keep wondering: how did "serious" mathematicians after Euler continue to assume 1 is a prime? I can imagine that the search of certain fancy categories of prime numbers gives little relevance to the primeness of 1. This comment might not be fully actionable, but somehow I am left unsatisfied by the section. Maybe it is possible to delineate more clearly in which parts of number theory the primality of 1 plays a role?
    • Our article states a pretty clear path for this in its description of how to handle the fundamental theorem: just talk about "primes greater than one" where today we would say "primes", listing 1 as prime for form's sake but then not really considering it. It's not really different in principle from what we do when we talk about the nontrivial zeros of the zeta function, say, listing the even negative integers as zeros for form's sake (because historically we use zeta and not some other reformulation that eliminates those zeros) but only really paying attention to the other zeros. —David Eppstein (talk) 20:08, 4 February 2018 (UTC)
Yes, OK, maybe I am asking for something unreasonable.
Anyway, to me, your argument makes it pretty clear that the primality of one is maybe not too relevant, since it can always be excluded at the expense of adding "greater than 1" throughout. Do we really want to spend this much space on the discussion of primality of 1? (Imagine a whole long subsection in Riemann hypothesis devoted to discussing whether the RH was first formulated for zeta(s), then later for the completed zeta-function?) Jakob.scholbach (talk) 21:33, 4 February 2018 (UTC)
I think we do want to spend the space, because it's the sort of question beginning students are likely to want to know. For instance, it seems to be a frequent topic in lower-level textbooks (lower-level than I've been trying to use as sources here): [1] [2] [3]. —David Eppstein (talk) 04:49, 5 February 2018 (UTC)
OK, thanks for these links. (I doubt, though, that beginning students will want (or need) to know about the historical ramifications of this point in this level of detail.) While I still disagree, I respect your editorial choice -- let's leave it as is for now. Jakob.scholbach (talk) 08:10, 5 February 2018 (UTC)

Number of primes

All comments addressed Jakob.scholbach (talk) 12:59, 13 February 2018 (UTC)
  • Is there a section title which makes the infinitude of primes immediate (and maybe also avoids the word "number" appearing twice)?
  • We could refer up to the fundamental theorem when discussing the prime factorization of N.
  • The section on Euclid should be reworked to make it more accessible (a ten-year old kid should be able to read this §): currently, the words "equivalently", "finite set", the product notation in Euclid's section should be avoided. The space needed for these explanations can be afforded by removing "It is often erroneously reported ..." -- this rather belongs to the subarticle.
  • Euler: the term partial sum could be avoided. Since we (rightfully) don't talk about the series \sum 1 / p, I would just omit the term altogether.
    • Done. I also removed the part about the growth rate being doubly logarithmic as unnecessary technical detail, and just left the pointer to the Mertens article where the growth rate is described. —David Eppstein (talk) 18:28, 1 February 2018 (UTC)
  • "For any arbitrary ..." -- it is not clear from the wording that this statement is not obvious (i.e., must be believed at this point). Again, this could be more welcoming: something like: while the terms 1 / p get smaller and smaller, the sums S(p) surpass any given threshold x, but one needs more and more primes p to do so (just sketching).
  • "occur more often" -- maybe clarify that both sets are infinite, but primes are "more dense" or the like? Jakob.scholbach (talk) 20:45, 31 January 2018 (UTC)

Computation

All comments addressed Jakob.scholbach (talk) 12:55, 13 February 2018 (UTC)
  • Is there a more meaningful title than "computation"?
Hm, "Algorithms" sounds reasonable as well, but is kind of unspecific. How about "Testing primeness and factorization into primes"? ("Factorization" is even more technical, I agree, than "computation", but the first sentence in the intro could say what it means. As the article progresses, we may not be able to completely avoid technical terms, but factorization is not too bad a term, I think.) Jakob.scholbach (talk) 10:38, 4 February 2018 (UTC)
We are supposed to avoid the title of the article in section headings, but I suppose sometimes it's unavoidable. —David Eppstein (talk) 16:58, 4 February 2018 (UTC)r
  • The hatnotes in the beginning of the subsections are sometimes capitalized, sometimes not.
  • Trial division: "grows too rapidly" -- do you think it is worthwile to explain this in more detail, especially in comparison to the modern methods outlined below?
  • I have a general concern about the entire section: we spend lots of space about elementary (and nearly useless) methods, and barely touch the methods that are really used. Can we find a better balance here? E.g. the sieve of E is nicely summarized in the image caption, and also discussed in a certain detail in the text itself. This could be trimmed. The more recent methods, or at least one of them, should be explained at least in a superficial way.
    • Ok, I replaced the abstract general testing algorithm and its failure probability epsilon with an explanation of Solovay–Strassen and its failure probability 1/2. Again, I phrased the algorithm in terms of divisibility not congruence, since the section explaining congruence is far below. Also I skipped over the quadratic reciprocity part very superficially. But trial division and the sieve of Eratosthenes are not useless. —David Eppstein (talk) 06:05, 5 February 2018 (UTC)
Thanks, that's the right direction, I believe. Jakob.scholbach (talk) 09:48, 6 February 2018 (UTC)
  • Along these lines: "Probabilistic tests with this behavior include the Solovay–Strassen primality test and the Miller–Rabin primality test" -- this gives no additional information compared to the table below.
  • "When using these methods to generate large random prime numbers" -- I am not sure how this fits into this section? From the surrounding text, the methods are used to test whether a given number is prime?
  • " can be tested for primality more easily" -- maybe more rapidly or efficiently?
  • "This is why the largest known prime has frequently been a Mersenne prime." -- the book (great that you often give the google links!) said that the largest known prime has been a Mersenne prime from 1992. Maybe add this more precise information?
  • "The largest number to be factored" -- maybe I am lame, but I think this needs more precision: 2^n can be factored for any n?
    I think that's covered by the "by a general-purpose algorithm" clause which immediately follows. Reading off the exponent of 2^n is a special-purpose algorithm. XOR'easter (talk) 18:06, 3 February 2018 (UTC)
@XOR'easter, would you mind to check the (last?) version I provided, please? Purgy (talk) 18:36, 3 February 2018 (UTC)
OK, I am lame. Anyhow, maybe it could not hurt to clarify what "general purpose" means? Jakob.scholbach (talk) 01:47, 4 February 2018 (UTC)

Distribution

  • I kind of like the quote by Zagier, but I feel it is a bit disconnected from the sequel. Can we explain better how the "growing like weed" and "almost military precision" means in more concrete terms?
  • "The corresponding question for quadratic polynomials is less well understood." -- I think a more precise statement here could not hurt, e.g. the one later in the article "No quadratic polynomial has been proven to take infinitely many prime values."
  • Again, there is a (IMO) too strong emphasis on the more elementary aspects: we mention twice (!) the existence of arbitrarily long prime gaps; we also in a way explain that this argument is almost useless by pointing out that gaps occur much earlier. IMO such detailed observations about an essentially trivial point should go to the subarticle. Here, we have more important things to say.
  • "This implies that the likelihood" -- I would say it is equivalent to it.
  • The fact that the Li estimate is more accurate is hidden in the notation   vs.  . Can we do better?
    • Is there a qualitative difference in the approximation that this notation was supposed to convey? They both have relative error going to zero, and we now have an illustration showing how much more rapidly it goes to zero for the better estimate. I changed both notations to   since that's the notation we actually explain. —David Eppstein (talk) 02:43, 18 February 2018 (UTC)
OK, the new image is a good step forward. (It could use a more detailed image caption to help the uninitiated reader though. Also, can you easily add "n" as a label to the x-axis?)
I think it is worthwile to pointing out the difference between the two approximations even more poignantly by comparing, e.g. pi(10^10) to the two approximations.
Isn't that comparison what the figure does (at the data point for n=10^10)? I expanded the caption to state something about the greater accuracy of Li. But there is already an "n" as label to the x-axis — it's under the 10^15. —David Eppstein (talk) 07:40, 22 February 2018 (UTC)
  • "The prime number theorem implies that the n th prime ..." -- I am not convinced it is good to disconnect this from the preceding explanation (which incidentally uses almost the same words).
  • " which happens when their greatest common divisor is one" -- I think the wording is unclear here, it should be: "which means that ..." or something which clarifies that this is the definition of the term coprime. (In the section intro we already mention the word coprime without explanation; one might move the explanatory definition up there).
  • Dirichlet's theorem, in its finer form (or more generally the Cebotarev density theorem), means that asymptotically each progression a+nq has the same density of primes. The article repeatedly (in the intro and the image caption) says they have a similar number. This should be made more precise.
    • Well, taken literally, "have the same density" isn't what you want to say — it's even less informative than what's there now, because their natural density is zero. The primes and the primes-in-an-arithmetic-sequence and the squares and the powers of two all have the same density. The wording was intentionally vague in an attempt to avoid saying that specific wrong thing and remain nontechnical while still hinting at what you actually want to say, that the primes in two sequences with the same b have inverse-log densities with the same constant factor. —David Eppstein ([[User

talk:David Eppstein|talk]]) 07:56, 22 February 2018 (UTC)

OK. Jakob.scholbach (talk) 14:55, 23 February 2018 (UTC)
  • I feel the section is a bit shallow: we should at least give a glimpse on how the prime number theorem is obtained. The remarkable use of (harmonic) analysis in Dirichlet's thereom is something we should convey here, I think.
  • I am also not so sure that the current article structure is optimal: the organization would be much smoother, it seems, if we aligned things along their mathematical content as opposed to whether it is conjectural "knowledge" or not. I.e., it might be good to merge the Riemann hypothesis into the distribution section. This would give an opportunity to at least point to the analytic methods used in the study of primes; would allow to at least mention Dirichlet's zeta functions. What do you think?
Overall, I think the sectioning is a definite improvement, thank you. Due to this massive reorganization, there are now various spots which need massaging. E.g. "Euler's analytical proof" should be relabeled, since we are no longer in the Infiniteness section.
Retitled as "Analytical proof of Euclid's theorem" —David Eppstein (talk) 03:31, 18 February 2018 (UTC)
Similarly "Computational methods" opens with a discussion about the (non-)applicability of primes; this is no longer reflecting the section content. Also the intro of "Related topics" does not fully fit its contents. Probably it is necessary to carefully review the entire article to look for such inconsistencies.
[Added later:] It might make sense to move much of the comments about the (non-)existence of applications to the cryptographic protocols? Jakob.scholbach (talk) 10:24, 19 February 2018 (UTC)
It's there at the start of the computational methods section because the applications were a significant motivation for the development of the general-purpose primality testing and factorization algorithms. And also it serves to summarize the whole section. —David Eppstein (talk) 08:02, 22 February 2018 (UTC)
The elementary observation about prime gaps could be moved to "Formulas for primes" or also to "Open questions".
Moved to "Open questions". —David Eppstein (talk) 03:20, 18 February 2018 (UTC)
Fermat's theorem on p=x^2+y^2 does fit into the arithmetic progressions section, but I think it would also be a good piece of motivation for the section on Gaussian primes. Jakob.scholbach (talk) 19:43, 11 February 2018 (UTC)
Moved. —David Eppstein (talk) 08:07, 22 February 2018 (UTC)

Open questions

All comments adressed Jakob.scholbach (talk) 14:55, 23 February 2018 (UTC)
  • In the § on zeta(s), it takes a long while until we arrive at an open question.
    • I added a couple introductory sentences mentioning the question.
  • Is the discussion of zeta(-1) crucial to this article? The wording "is sometimes used to assign a finite value" is at least suboptimal: it leaves it unclear what "sometimes" means, and also how that assignment is actually possible. I would remove this sentence altogether.
    • The intent was to include it as an example of how the function is not the same thing as the sum, a point many sources get confused on. (I found far too many sources saying that zeta is defined as sum 1/n^s, rather than that it is an analytic function that happens to equal the sum for the values at which the sum converges.)
This is indeed important to understand, but does it belong to this article? Jakob.scholbach (talk) 10:44, 5 February 2018 (UTC)
Ok, you raise a valid point. As there is little connection to primes themselves, I removed it (and the statement about zeta having a single pole, which is similarly an important fact about zeta but not particularly connected to primes). —David Eppstein (talk) 19:50, 5 February 2018 (UTC)
  • Again I am wondering about a more global reshaping of the article: would it make sense to have a section "Analytical properties" or "Analytical study of primes" or the like, beginning, say with the Basel problem (which I think fits nicely before the general discussion of zeta), then zeta(s), maybe the prime number theorem, and going on to Dirichlet's theorem, and the Green-Tao theorem? I would not go as far as making this into a criterion for the GA review, but maybe we could at least discuss the global structure here?
    • I'm far from convinced that the current structure is the right one. I don't think thinking of it as an elementary/analytic dichotomy is right, though — that misses too much of the current content. I could imagine a reorganization like (in some order, not necessarily this one)
      1. History
      2. Elementary properties
      3. Analytic properties
      4. Computational methods
      5. Abstract algebra
      6. Other
    This would at least allow grouping the connections to group theory better than where they're placed now. But some current topics (e.g. formulas for primes, or the twin prime conjecture) are not easy to classify along those lines. Is a problem elementary if it has an elementary statement even if the best methods for solving it are not? Is the prime number theorem elementary because it has an elementary proof? Is there anything analytic about the Ulam spiral?
      • Sounds better. How about this tweak of your suggestion:
        1. Elementary algebraic aspects (Fundamental theorem; Infiniteness à la Euclid; arithmetic in Z/p; Lagrange's theorem(?))
        2. History
        3. Distribution of primes (Euler's proof of infiniteness and zeta(s); prime number thm; RH; Dirichlet; primes in quadratic functions; further conjectures (twin prime etc); formulas for primes [this one is a bit misplaced, but I think distribution is still the best umbrella we have for it])
        4. Computation [part of this needs modular arithmetic to come before] (trial division, sieve theory including additive number theory and Goldbach etc., rest [if we want to avoid Lagrange's theorem in the beginning, this would also fit in the section on the algorithms which need it])
        5. Other (Applications, generalizations, pop culture)
      • This would require a somewhat more thorough exposition of sieving and its relation to additive aspects than we currently have. The distribution section would be pretty long, but this is the only disadvantage I see right now. Jakob.scholbach (talk) 10:09, 6 February 2018 (UTC)
  • The fact that the RH is one of the big open problems is not at all clear. Also, e.g. in Zagier's "50 million" article there is a nice chart showing how precise this estimate related to the RH is. Our current picture shows this also, but less interestingly in that one can barely distinguish the blue and red lines.
I guess this is not mandatory for the GA process, but I do think his illustration conveys more: for numbers up to 10^9, the deviation never gets more than about 600! (Deviating around ca. 5*10^6) -- this is way more precise than the pixels of the current illustration (which only goes to 10^5) can tell.
I leave it to you or anyone interested (Purgy Purgatorio, XOR'easter, what are you up to tonight?) to create an illustration using some standard software. If we don't have that illustration, it is not a big deal, but it would be kind of nice, wouldn't it? Jakob.scholbach (talk) 18:17, 7 February 2018 (UTC)
Replaced by a new image showing the (tiny) relative error. —David Eppstein (talk) 02:41, 18 February 2018 (UTC)
  • I am not sure this comment is actionable, but I find the conjectures of primes in other sequences a bit odd: in some cases there is an expectation, in others there isn't. One gets no clue of how these expectation arise. Does the literature offer more rationales behind these conjectures? Also, are they really crucial? E.g. the fact that prime order groups are cyclic is just very briefly mentioned, I personally consider such aspects of primes way more important than these conjectures. (This remark also fits maybe more nicely next to some of the primality tests, I think.)
    • Based on this comment I removed this paragraph, with only a little bit moved elsewhere. I think the Fermat and Mersenne questions are somewhat important but they're both covered in more detail elsewhere (constructible polygons and large primes, respectively). Wieferich used to have some importance in connection with Fermat's last theorem but has become less relevant, the Euclid numbers are again mentioned in the large prime section. That leaves the Fibonacci prime and super-primes which I agree are unimportant and are really only mentioned here as an excuse to link to some related articles. As for where these expectations arise, as far as I know there are two factors behind those conjectures: (1) if we pretend primes are random numbers with the right density, then sparse sequences have O(1) expected elements and denser sequences have infinitely many (this already explains the difference between Fermat and Mersenne), and (2) sequences whose elements' factors must have a special form are likely to have more primes than the random-number hypothesis would suggest (this is true for both Mersenne and Fermat, but apparently doesn't make enough of a difference to make the expected number of Fermat primes become non-constant). But this reasoning belongs in the articles on those sequences, I think, not so much here. —David Eppstein (talk) 08:26, 7 February 2018 (UTC)
OK, thanks for explaining. The next paragraph starts with "A third group", this should be massaged. Jakob.scholbach (talk) 18:17, 7 February 2018 (UTC)
I think XOR'easter fixed this at some point. —David Eppstein (talk) 22:49, 17 February 2018 (UTC)

Applications

All comments adressed Jakob.scholbach (talk) 14:46, 23 February 2018 (UTC)
  • "including abstract algebra and elementary geometry." -- what applications in elementary geometry are these? If this is about Gauss' theorem concerning constructibility of n-gons, I would rather call this a place where primes occur, but not so much an application.
  • There is a break of text flow: 1) primes have no application outside maths, 2) they have applications in abstract algebra 3) they do have applications.
Thanks, but not good yet: as a first sentence, "Prime numbers have many applications to other areas within mathematics" should be rounded off (what are "other" areas if "the one" area is not specified?); also the following sentence does not blend in well. Jakob.scholbach (talk) 18:56, 7 February 2018 (UTC)
As stated above, this first sentence is gone now. —David Eppstein (talk) 08:17, 22 February 2018 (UTC)
  • Do you think it makes sense to explain Diffie-Hellmann or RSA in a bit more detail? E.g. the point that the arithmetic is happening in Z/p or Z/p^x would be notable in connection to this article.
    • The images I've seen trying to explain D-H simply (e.g. [4] do not look so simple to me, especially when one factors in trying to explain what it means to be a cryptographic protocol, who the participants are, what they know and don't know, etc. And RSA does its arithmetic modulo a composite; the primes show up only more subtly in being able to compute its totient. —David Eppstein (talk) 08:20, 12 February 2018 (UTC)
I wasn't necessarily thinking of a complete explanation of Alice and Bob etc., but of explaining in a bit more detail (2, 3 lines) what modular exponentiation is and the discrete log. The point of contact with this article is of course that all this happens in Z/p (or Z/p^x). Conveying the bit of information that computations in Z/p have a practical impact would be a reasonable goal of this snippet, IMO. Jakob.scholbach (talk) 11:59, 14 February 2018 (UTC)
But the computations in question (modular exponentiation) don't depend in any way on the modulus being prime. Primality goes into the security of the algorithm (the fact that it generates the entire key space and is harder to attack than modular exponentiation mod a composite). —David Eppstein (talk) 08:36, 22 February 2018 (UTC)
  • The part about illegal primes strikes me as a bit funny: this "application" consists of avoiding legal hassle because you can say "hey, this is a prime"? In my mind it makes more sense to say a little more on the real applications, such as the cryptography protocols.
    • Yeah, that's mostly there for entertainment value; there's not much deep there other than that the primes are reasonably dense and you can test primality for big enough numbers. It can go if you think it would be better removed. —David Eppstein (talk) 08:46, 11 February 2018 (UTC)
I believe its relevance is epsilon compared to, say, the cryptographic protocols. Spending these 3 lines on Diffie-Hellman or RSA or more generally on emphasizing the practical relevance of modular arithmetic modulo p strikes me as a better plan. Jakob.scholbach (talk) 11:59, 14 February 2018 (UTC)
Ok, I'm still not convinced about how to expand the cryptography but that should be irrelevant to the cost-benefit of keeping the illegal prime material. Removed as having too big a cost (in increased article length) for its benefit. —David Eppstein (talk) 20:59, 22 February 2018 (UTC)

Generalizations

All comments adressed Jakob.scholbach (talk) 14:55, 23 February 2018 (UTC)
  • Again, I'd love some pictures! Maybe a non-prime knot?

 

  • Can we offer an illustration for the Gaussian primes? Including the splitting of 2 = (1+i)(1-i)? And maybe also relate this discussion to the decomposition of primes into sums of squares? (We have it somewhere else, I don't find it right now).
    • I added an illustration but it doesn't particularly show the splitting. Nothing like that seems to exist in Commons:Category:Gaussian integers, which is where I would expect to find it. I found a few other images of the Gaussian primes and added them to the category, but maybe I missed something. Unless you mean File:Spec Zi.png, which is probably not understandable by people who haven't seen such diagrams before without some explanation. —David Eppstein (talk) 06:31, 9 February 2018 (UTC)
Why not File:Gauss_prime_numbers.svg? It lists the primes in a way which is closer to the text (the a+ib is completely missing in the black-dots-picture we have right now). In the image caption we could briefly allude to the splitting of 2 and relate it to the question of writing p = x^2 + y^2. Jakob.scholbach (talk) 12:41, 9 February 2018 (UTC)
Because it's illegible at any reasonable size? —David Eppstein (talk) 16:37, 9 February 2018 (UTC)
That's right, I take suggestion back.
The current one is not so much better, though: the points are clearly discernible, but their meaning is unclear without a longer explanation of the image content. Jakob.scholbach (talk) 23:36, 10 February 2018 (UTC)
  • I enjoy reading the section on Prime ideals, but I believe only since I already know its content. To simplify the transition to the more advanced topics, I suggest to begin with Z[sqrt[-5]] or the like, briefly explain its non-UFD-ness (again, maybe with a picture?) and state that prime ideals are the way out.
  • "may be viewed as geometric points" -- maybe "The spectrum of a ring R is a geometric object whose points are the prime ideals in R"?
  • To give the reader a little bit of a feeling, Cebotarev might be linked to Dirichlet's theorem above. The current text is correct etc., but will only mean something to people fluent in algebraic number theory.
  • I feel the § on valuations should precede prime ideals: the former are easier, and also less general.
  • The § on valuations is not very welcoming: I suggest beginning with the definition of |-|_p or v_p(-), give a mini-example. Then the product formula, briefly link it to local-global principle. Then state the existence of Q_p, Ostrowski. Finally talk about places etc. (I am not sure places are actually a must in this article.)
  • The § on valuations could be renamed "p-adic numbers", to make the connection to primes more apparent from the title already.

In games ...

References

Conclusion

I am happy to pass this good article nomination. Kudos and thanks to David Eppstein for his tireless work! If this article is going to be an FA nominee in the future, I think a fresh look, in particular with regard to the recent massive reorganization, would be helpful. Also, in certain spots I think the article could be made yet more welcoming / entertaining to non-specialists, but this is well beyond the GA criteria. Jakob.scholbach (talk) 14:55, 23 February 2018 (UTC)

How to deal with "primorial"?

Latest comment: 6 years ago4 comments2 people in discussion

Recently I encountered for the first time in my life the term "primorial prime". It is contained as table entry in a table about largest primes of several types, and links to the homonymous article, which itself links to the article about the primorial function. A (the?) notation for this function, a postfixed hashtag, is also employed in this table.

Assuming a negligible importance of these terms and the denotation, especially compared to the eponymous "factorial", I still feel a certain need, as a service to the expected readership, to explain them locally, perhaps in a footnote to the table entry, e.g., like: primorial prime[1]. Purgy (talk) 11:45, 31 January 2018 (UTC)

References

  1. ^ the primorial function of n, denoted by n#, yields the product of all prime numbers up to n, and a primorial prime is a prime of one of the forms n# ± 1
Actually it's the product of the first n primes, not the primes up to n. But anyway I added the footnote. —David Eppstein (talk) 18:16, 31 January 2018 (UTC)
Just for WP's sake, the notation n# (as used in the table) yields the product of all prime numbers up to n, and pn# yields the product of the first n primes. May I ask you to check your source? Purgy (talk) 18:38, 31 January 2018 (UTC)
You're right, primorial says there are two conflicting definitions, and the book source I used also uses the same definition you gave, not the one in my comment above. Will fix. —David Eppstein (talk) 18:48, 31 January 2018 (UTC)

On "Computation"

Latest comment: 6 years ago3 comments2 people in discussion

Computation → Localizing primes - Concrete primes - Individual primes - Computing primes
Wish I were inspiring. Purgy (talk) 14:32, 3 February 2018 (UTC)

Could also be "Algorithms". —David Eppstein (talk) 16:13, 3 February 2018 (UTC)
Your button is bigger than mine. ;] Purgy (talk) 09:03, 4 February 2018 (UTC)

Efforts to help with clerical details

Latest comment: 6 years ago1 comment1 person in discussion

Recently I tried to deal with some details, either mentioned in the GAR, or on my own estimation. I certainly do not want to disturb the reviewing process, but I missed the reasons for reverting edits in these examples:
Sieves: My effort to describe -independently of the animation- the object the sieve is operating on and its product by "a list of subsequent numbers, starting with 2, and generating all the primes in this list" is completely removed as "unintelligible" and the caption I wrote, qualified as "nicely summarizing" by the reviewer, is replaced with a wrong description. My correcting variant in an other style was also reverted. Now it is hopefully correct.
History: I tried to emphasize that the first archeological find spectacularly dates back to the paleolithic —removed, together with an attempt to construct the timely flow from there via the Rhind papyrus to the ancient Greeks. It may well be that this flow is beside the top mathematical facts, but I would at least spend these few words to make this section more interesting to an encyclopedically minded readership.
Trial Division: Triggered by the reviewer, asking for detail on "grows too rapidly", I added from the given source the growth of the number of prime divisors, relevant to the considered algorithm and treated in this article. —reverted, and later on related -far more vaguely- to exponential growth of numbers with respect to the number of their digits: exponential. Why? BTW, for precision sake I put the word "maximally" next to the upper bound sqrt(n) of divisors. This is certainly not perfect. It was intended to hint that the full range of divisors is not necessarily to be exhausted, one lucky guess on a factual divisor might suffice. Simply removing the word "each" would probably do the job better. I do not mind being reverted for preferring "not greater" to "less or equal".

Since, as I repeatedly said already, my prime target is not to interfere with making this article a good one, I suspend any activities of mine until some distinct clarifications. Purgy (talk) 12:17, 5 February 2018 (UTC)

Resource check script

Latest comment: 6 years ago2 comments2 people in discussion
  • Script being tested/under development.
  • Inconsistent use of Location parameter (23 with; 62 without);
  • Adler, Irving (1960). Missing Identifier/control number, e.g. OCLC;
  • Beiler, Albert H. (1966). Pub. too early for ISBN, perhaps needs |orig-year=; Missing Identifier/control number, e.g. OCLC;
  • Deutsch, P. Missing Year/Date;
  • Euclid's Elements, Book IX, Proposition 20. See David Joyce's English translation of Euclid's proof or Williamson, James (1782). The Elements of Euclid, With Dissertations. Oxford: Clarendon Press. p. 63. Missing Identifier/control number, e.g. OCLC;
  • Hua, L. K. (1965). Pub. too early for ISBN, perhaps needs |orig-year=;
  • Hardy, Godfrey Harold (1940). Pub. too early for ISBN, perhaps needs |orig-year=; Missing Identifier/control number, e.g. OCLC;
  • Goodrich, Michael T.; Tamassia, Roberto (2006). Missing ISBN;
  • Knuth, Donald E. (1998). Missing ISBN; Lingzhi ♦ (talk) 00:04, 9 February 2018 (UTC)
OK, I think I've gotten everything except the location parameters. XOR'easter (talk) 19:36, 10 February 2018 (UTC)

Group theory

Latest comment: 6 years ago3 comments3 people in discussion

In the account of the Burnside theorem, it is not said if the two primes are required to be distinct or not. — Preceding unsigned comment added by 2A00:23C0:7C80:8401:41F9:319F:21B2:8E74 (talk) 16:00, 14 February 2018 (UTC)

Luckily, the words "Burnside theorem" in the article are a link, and anyone who is confused by this can click the link and see the extremely clear statement in the first paragraph there. --JBL (talk) 16:37, 14 February 2018 (UTC)
There is some ambiguity in whether "only two primes" in this article means at most two primes or exactly two primes. But fortunately, it doesn't matter much because the one-prime case gives cyclic groups, the zero-prime case gives the trivial group, and all are solvable. I think the current wording doesn't need to be made more technical and difficult to read by trying for more precision in a case where that precision is irrelevant. —David Eppstein (talk) 19:01, 14 February 2018 (UTC)

Fundamental theorem of arithmetic

Latest comment: 6 years ago17 comments4 people in discussion

Joel_B._Lewis Since you and me discussued the inclusion of al-Farisi's work in the article and the correction of Euclid's contribution, i would welcome your opinion about my edits on the mainspace of this article. David Eppstein, your opinion is also welcome. Since i'm a new user, your insight is important for me. Thanks for your valuable time. Best regards.---Wikaviani (talk) 16:01, 4 May 2018 (UTC)

My opinion is that the fundamental theorem clearly appears in the work of Euclid. He formulated it in an awkward way that makes the unique factorization part apply only to squarefree numbers, but it's there too. Modern authors have rewritten the theorem in modern terminology without that flaw. I don't know the history of who first corrected it and wrote out the theorem in what we would recognize as its modern form, but your sources (because they don't count Euclid at all) aren't informative with respect to that question. —David Eppstein (talk) 16:06, 4 May 2018 (UTC)
David Eppstein Thanks for your answer. the problem is that i've looked on the internet but i was not able to find a reliable source stating that Euclid CLEARLY stated the fundamental theorem, but all sources state that this theorem is easy to deduce from his work. More, R. Rashed who is a prominent expert on that matter states that al-Farisi stated the theorem for the first time ([6] page 385). If we consider this theorem with modern expression, Gauss was the first to state it. I think that the article is misleading by making no mention of al-Farisi's contribution while reliable sources support his contribution. Here another source stating that the theorem is easy to deduce from Euclid's work (but the theorem is not in his work) : [7] page 4. Best regards.---Wikaviani (talk) 16:18, 4 May 2018 (UTC)
The sources provided by Wikaviani do not state which version of the fundamental theorem of arithmetic has been proved by al-Farisi (existence and/or uniqueness?). A fortiori, they do not give any indication of which result of al-Farisi is not in Euclid's elements. Thus the assertion that al-Farisi was the first to prove the theorem is not verifiable from the given sources. Therefore these sources are not reliable for supporting the assertions added by Wikaviani. al-Farisi's results may be cited in the article only if some sources are provided that describe accurately these results. This is not yet the case. D.Lazard (talk) 16:46, 4 May 2018 (UTC)
Hi D. Lazrad, thanks for your comment. The article on prime number and the article on the fundamental theorem of arithmetic do not contain any sources supporting the Euclid claim, but this does not seem to bother you , could you please explain me why ? I would appreciate a mathematician's opinion on this matter. I'm not a specialist of number theory, but maybe David J Wilson, who nicely worked with me and others on the Sharaf al-Din al-Tusi's article, can help us here. Please note that my concerns are not driven by any nationalistic view, i just try to improve the article and make it the most complete possible. But if the community does not want to recocgnise al-Farisi's contribution on this topic, that's fine, let's keep Euclid, but we need reliable sources for any claim included in the articles, i think that our personal opinions are not requested in them, right ?---Wikaviani (talk) 17:23, 4 May 2018 (UTC)
We have Euclid's Elements to look at ourselves. It is not difficult to read in translation. —David Eppstein (talk) 17:30, 4 May 2018 (UTC)
Here is a source for existence only (the authors wrote an earlier paper dedicated to al-Farsi, see References,2). "The first known proof of existence is due to al-Farisi (died c. 1320), but he did not go on to prove uniqueness, mainly because his interest was in the divisors of a number rather than the factorisation itself." ("The fundamental theorem of arithmetic dissected", A Agargün and CR Fletcher, Mathematical Gazette, 1997)[8] Wiqi(55) 17:32, 4 May 2018 (UTC)
If just reading the Elements was enough, there would not be so much confusing history about this theorem. Check the sources i posted above, Andrew Granville says the history of this theorem is confused [9] page 4. He also states that "The oldest surviving text WITH A CLEAR STATEMENT that every positive integer can be written as a finite product of prime numbers is given by al-Farisi", page 4. This is a very clear statement and contradicts the fact that Euclid CLEARLY stated the theorem.---Wikaviani (talk) 17:45, 4 May 2018 (UTC)
Hi Wiqi55, nice to see you again ! in fact al-Farisi "gave all that is needed to prove the uniqueness", see [10], introduction. This reference also states that the theorem dies not appear in its modern form in Euclid's work and that the history of the FTA is strangely obscure. So this is not that simple to read the Elements and draw conclusions.---Wikaviani (talk) 17:52, 4 May 2018 (UTC)

Wikaviani, you appear to have removed one of my comments from this discussion. Do not do this. Here it is again.

Ok, so (e.g. [11]): Euclid (IX.14) proved uniqueness, but only for squarefree numbers. Many sources agree that existence is a corollary of Euclid VII.30-31, but is not explicitly stated by Euclid. According to this source, al-Farisi took the additional step of stating existence and deriving it as a corollary. This still doesn't tell us who first stated it in the full existence-and-uniqueness-for-all-numbers form. (Certainly at least Gauss did so but that seems very late for this.) —David Eppstein (talk) 17:38, 4 May 2018 (UTC)

To this I would add: if you are going to fault Euclid for providing all the ingredients for existence but not explicitly stating it, it seems very unfair to credit al-Farisi for providing the ingredients for uniqueness but not explicitly stating it. Especially since a form of uniqueness is already in Euclid. —David Eppstein (talk) 18:07, 4 May 2018 (UTC)

The quotation does not give any indication on what is in al-Farisi's work and is not in Euclid's elements. And I have not access to the source without paying. Thus, without further information, the only thing that can be added to the article is Some authors assert that the first known proof of existence is due to al-Farisi (died c. 1320). Another acceptable formulation, would be The theorem has been essentially proved by Euclid, but the first known explicit statement that every natural number greater than one is either a prime or a product of primes is due to al-Farisi. Also, all proofs of uniqueness that I know are corollaries of Euclid's lemma (Elements Book VII, Proposition 30). So, what is "needed to prove the uniqueness" and is not in Elements? Without answer to this question, the sentence is nothing else than an opinion. D.Lazard (talk) 18:10, 4 May 2018 (UTC)

David Eppstein Sorry, which comment have i removed ? if so, it's because the computer i use for this thread is short of RAM and often freeze, that makes my typing slow and makes me do some mistakes. Sorry again. I understand your point of view about Euclid and al-Farisi, but the current version is unfair with al-Farisi because there is not a single mention of him in the article while he seems to have made significant contributions to this topic. Euclid is presented as the one who discovered the theorem. I think D. Lazard's compromise is quite well balanced. D.Lazard, which source do you need to access ? i can help you for that if you want. Also, you're right about the proofs of uniqueness, they are corollaries of Euclid's lemma.---Wikaviani (talk) 18:41, 4 May 2018 (UTC)

It's important to note that the place where this material would go (the history section) is really telegraphic; there isn't really room in there to go into a lot of details. The separate fundamental theorem article is where details should go. So what would be needed here is, first, how to clearly and concisely state Euclid's contribution to this theorem (currently "Euclid's Elements proves ... the fundamental theorem of arithmetic") and second, again concisely, state al-Farisi's contribution (maybe something like "In YYYY, al-Farisi provided the first explicit statement of the existence of prime factorizations", but that only makes sense if the earlier sentence about Euclid makes clear that Euclid provided the main ideas of the proof but never stated the fundamental theorem explicitly. —David Eppstein (talk) 20:55, 4 May 2018 (UTC)
First, i would like to thank all you guys for the valuable time you have devoted to this discussion. Second i completely agree with you now, David, when you say that this article is not the right place for details about the history of the theorem. Third, i need some time (probably several days) to make accurate researchs before editing the Fundamental theorem of arithmetic's article. With your permission, i would like to ping you before on the talk page to show you what i would like to write in the article before editing the mainspace article (perhaps something close to D. Lazard's proposal), in order to avoid any disruption of Wikipedia. Would this be ok for you ? Thanks again.---Wikaviani (talk) 21:55, 4 May 2018 (UTC)
Thinking about it some more, I think Euclid VII.30 and VII.31 really are the uniqueness and existence conditions (respectively) of the fundamental theorem; just written in the language of individual prime factors instead of the whole factorization at once. 31 says there is a prime factor and 30 says that whenever you divide by anything else it will still be there. What's missing from them, compared to the modern formulation, is looking at the whole factorization at once as a single mathematical object. The whole factorization at once is present in IX.14, but only for squarefree numbers and (because it doesn't work for all numbers) only the uniqueness part and not existence. And why is it in book IX instead of next to the other two propositions? It's almost like Euclid took parts of two number theory texts and glommed them together in a not-completely-consistent way (not the only instance of this kind of inconsistency). —David Eppstein (talk) 07:51, 5 May 2018 (UTC)
So do you think it's worth including some other mathematicians contributions (i think of Gauss and al-Farisi) or Euclid's work is enough ? As far as i know al-Farisi proved the uniqueness in the general case and Gauss can be credited of stating the theorem in its most modern form and with modern algebraic notations, but maybe i'm wrong, i need more time to make some researchs. But if you think that mentioning Euclid alone is enough, then it's ok for me and i will self revert on the al-Farisi's article to keep some logic between the different articles about this topic. By the way i found the whole paragraph from you that i removed yesterday and again, sorry for that, i was trying to cut/paste a part of the comment i was typing then the keyboard freezed and i made that mistake, stupid machine. Best regards.---Wikaviani (talk) 15:56, 5 May 2018 (UTC)

Semi-protected edit request on 18 June 2018

Latest comment: 6 years ago4 comments3 people in discussion

the math is done wrong 21 is not a prime number as 7x3= 21 Milatarymarshmallow (talk) 06:05, 18 June 2018 (UTC)

  Question: And where does it say that 21 is a prime number? ChamithN (talk) 06:11, 18 June 2018 (UTC)
Possibly this is referring to "As of October 2012 the largest number that has been factored by a quantum computer running Shor's algorithm is 21." Also the gears diagram says that 21 is relatively prime to 13.--♦IanMacM♦ (talk to me) 07:09, 18 June 2018 (UTC)
@Milatarymarshmallow: In which case, there's nothing to fix, as both statements are correct. Regarding Shor's algorithm, it says "the largest number", not "the largest prime number". Also, 21 and 13 are relatively prime since they only have 1 as a common factor. -- ChamithN (talk) 08:07, 18 June 2018 (UTC)

Pokémon

Latest comment: 6 years ago4 comments4 people in discussion

Would it be worth adding, under the Arts and Literature section, that the category of Pokémon known as "Ultra Beasts" has prime numbers as a motif? In the Pokémon video games, Ultra Beasts can only learn moves at levels equal to prime numbers, all of their base stats are prime numbers (with the exception of Naganadel's 121 base Speed), and the quantity of confirmed Ultra Beast species is always a prime number (7 in Pokémon Sun and Moon and 11 in Pokémon UltraSun and UltraMoon). Ron Stoppable (talk) 01:36, 2 August 2018 (UTC)

No. –Deacon Vorbis (carbon • videos) 01:41, 2 August 2018 (UTC)
WP:POPCULTURE is the guideline here. A person can live without knowing this. It is more on topic at List of Pokémon characters. There is also a problem with sourcing, because I couldn't find much beyond fan sites which mention this.--♦IanMacM♦ (talk to me) 05:22, 2 August 2018 (UTC)
Absolutely not. Someone interested in Pokémon may be interested in learning that, but someone interested in the mathematics of primes is not likely to, so it doesn't belong in this article. The editor who uses the pseudonym "JamesBWatson" (talk) 11:01, 2 August 2018 (UTC)


set of potential primes > 7

Latest comment: 6 months ago9 comments5 people in discussion
WP:NOTFORUM. The Math Ref Desk is thataway.
The following discussion has been closed. Please do not modify it.

Here is the set of all potential primes greater than 7 (30k + r), r = {1,7,11,13,17,19,23,29}, k is any integer 0 to infinity. the only ones that are not prime are divisible by (30x + r). (30(0) + 1)(30k + r) = 30k + r, so the first prime with r = 1 will be at k = 1. This also means it is not worth checking (30(0) + 1) as a factor of a composite.

If you take all r, (r1 x r2) mod 30 it will give you the valid pairs of composites. Example (11 x 11) mod 30 = 1. So if you take a number n/30 remainder 1 it has potential divisors of (30x + 11)(30y + 11).

(11,11) is a valid pair for remainder 1. 1 and 19 have 6 valid pairs all other r have 4. This is because we have 8 numbers and a • b = b • a. 1 and 19 have 2 more pairs because or the squares of r’s exist there.

So if you take any number n/30 if it does not have a remainder in the set r it is not prime. If it does have a remainder in set r it is prime if it cannot be divided by a number from one of the found valid pairs. 4087 = (30(1) + 7)(30(1) + 1) LandonL (talk) 12:04, 8 June 2024 (UTC)

This is essentially the sieve of Erastothenes stopped after having marked the multiples of 2, 3 and 5. D.Lazard (talk) 13:47, 8 June 2024 (UTC)
You can use the extend form of composites to tell you all non-primes in order. N - r3 = 900xy + 30(x)(r2) + 30(y)(r1) + (r1)(r2)
All potential primes > 5 are 30(z) + r3. You can now print out all primes in order in O(1) time. LandonL (talk) 13:57, 8 June 2024 (UTC)
I want to also note the set of all potential primes could be written as 15o + w where w = {-14,-8,-4,-2,2,4,8,14} and o is any positive odd integer.
Separate note:
Since N = 900xy + 30(x)(r2) + 30(y)(r1) + (r1)(r2), the range, to find a factor on N, for x is 0 to sqrt(n/900) or sqrt(n)/30.
So long as r1 <= r2 LandonL (talk) 16:53, 9 June 2024 (UTC)

This is not the place to write original research. Unless you can find a reliably published reference for this material it is off-topic here. —David Eppstein (talk) 17:04, 9 June 2024 (UTC)

This isn't original, and this article already has a relevant section § Sieves describing the idea at a high level and wikilinking to more detailed articles covering the details. –jacobolus (t) 19:26, 9 June 2024 (UTC)
I have just corrected the sieve because 2,3,5 should not be in the sieve if you want to see the set of potential primes larger than 5. Which if you subtract the set created by 900xy + 30(x)(r2) + 30(y)(r1) + (r1)(r2) you will have all your prime numbers greater than 5. It is easier to see, if in the composite set you change 1 in r to 31. I know I have never seen the set of potential primes, composites, or primes written out like this. But if it helps others explain things related to prime numbers that’s fine. If I am just an idiot wasting time, that seems fine as well. LandonL (talk) 20:27, 9 June 2024 (UTC)
This is essentially just saying that if you are looking for prime numbers you don't have to consider any numbers which are multiples of the first few primes. Not a particularly significant observation. JBW (talk) 21:24, 9 June 2024 (UTC)
What I am saying is you can print out all potential primes in order without missing any, and at the same time you could print out all the numbers that are not prime in the set of potential primes in order. You can do a loop within a loop to print out prime numbers in 0(1) time, which seems much faster than what everyone is doing now. LandonL (talk) 21:35, 9 June 2024 (UTC)

Move discussion in progress

Latest comment: 1 year ago1 comment1 person in discussion

There is a move discussion in progress on Talk:Prime (disambiguation) which affects this page. Please participate on that page and not in this talk page section. Thank you. —RMCD bot 18:32, 14 February 2023 (UTC)

Retrieved from "https://en.wiki.x.io/w/index.php?title=Talk:Prime_number/Archive_9&oldid=1254523642"