Talk:Sieve of Eratosthenes/Archive 2

Archive 1

Archive 2

Archive 3

Comments

Some ideas to improve the quality of the sieve of Eratosthenes article

1. "Algorithm complexity and implementation" section

• Too much information about functional programming one simple pseudocode example with description is enough
  • I will go ahead and remove all the extra stuff then, after few days, if there's no objections. Maybe Python code should stay, it's fairly readable as a substitute to pseudo-code. WillNess (talk) 21:39, 5 May 2011 (UTC)

2. The "Mnemonic" section should be removed in my opinion it is misplaced

• but it is nice. let it stay. :) WillNess (talk) 21:39, 5 May 2011 (UTC)

3. "External links" section, remove some of the links especially those of bad quality e.g.:

• Analyze the Sieve of Eratosthenes in an online Javascript IDE
• Sieve of Eratosthenes in C (http://www.dreamincode.net/code/snippet3315.htm)

4. "External links" section: add a link to a site that offers the sieve of Eratosthenes in many programming languages e.g.:

• http://www.scriptol.com/programming/sieve.php or http://c2.com/cgi/wiki?SieveOfEratosthenesInManyProgrammingLanguages

April 23, 2011

Apparently:

KOΣKINON EPATOΣΘENOϒΣ. or, The Sieve of Eratosthenes. Being an Account of His Method of Finding All the Prime Numbers, by the Rev. Samuel Horsley, F. R. S. Samuel Horsley Philosophical Transactions (1683-1775), Vol. 62. (1772), pp. 327-347.

Is the paper that popularized this algorithm, if anyone wants to fill in historical details.

--Imran 21:15 13 Jun 2003 (UTC)

If a person wants fully working code, they can check code repositories. If a person wants performance hacks, they can check programmer's journals. Wikipedia is neither a code repository nor a programmer's journal.

Pseudocode is used on Wikipedia as a last resort to explain an algorithm, because most programming languages are not readable by common encyclopedia readers. There is also no excuse for repeating the fairly understandable explanation of the algorithm with pseudocode. Feel free, however, to insert external links to either. For an example, see Sieve of Atkin, which, while it does not have a good explanation yet, does have an external link to working, optimized code. — 131.230.74.194 21:28, 11 July 2005 (UTC)

I added a more simplified pseudocode -- ba 24.57.157.81 06:52, 5 March 2007 (UTC)

For classroom demonstrations, it's really much easier to perform the algorithm if there are 6 columns, that way the second, third, fourth and sixth columns can be entirely crossed out/erased except for the numbers 2 and 3. All other primes will be in the first and fifth column. —Preceding unsigned comment added by Tony Hammitt (talk • contribs) 17:19, 29 March 2010 (UTC)

Python algorithm

I looked at the Python algorithm, and it doesn't seem to exactly match the description of the algorithm nor the animated illustration. (but then, i'm not sure the haskell one does either.) also i'm not sure if people not well-versed in python would understand filter or pop(0).

I wrote an alternative Python implementation, for your inclusion if you feel like it:

def primesieve(upperbound):
  numbers = range(upperbound)
  for n in xrange(2, upperbound**.5+1):
    if numbers[n] is not False:
      for m in xrange(n+n, upperbound, n):
        numbers[m] = False
  return [q for q in numbers if q is not False and q >= 2]

Inhahe (talk) 10:36, 4 April 2009 (UTC)

I agree. The algorithm currently shown on the page is a variation on the brute force approach. As each prime is discovered, it checks if all of the remaining numbers are divisible by the prime. The whole idea of the sieve is to only check the multiples of the number. Thomasrdean (talk) 15:22, 26 May 2009 (UTC)

The Haskell algorithm matches exactly David Turner's algorithm, as stated. It does not match any of the imperative algorithms mentioned above, nor is it meant to. That is the whole point. Turner used the seive of Eratosthenes to demonstrate the expressiveness of functional languages, but his version of the sieve algorithm is different and less efficient. Read the referenced paper of O'Neil for more information, and to see how she corrects that.

The Python algorithm matches neither Turner's nor the other imperative ones. Nor is it more "lucid". I don't really see that it serves any purpose here. If it's meant to illustrate the imperative algorithms, it should be moved up a few paragraphs, and corrected to match them; but the truth is, I don't think it really adds anything. If it's meant to illustrate Turner's version, it is not only wrong, it's just not appropriate; Python is not a functional language.

You could use Python's functional features, like this:

 import itertools
 def sieve(numbers):
   p = next(numbers)
   yield p
   for q in sieve(n for n in numbers if n % p != 0):
     yield q
 primes = sieve(itertools.count(2))

You would then get, say, the first 100 primes by writing:

 [next(primes) for i in range(100)]

But again, I don't see what that adds. I'm removing the Python stuff.

StormWillLaugh (talk) 12:44, 1 June 2009 (UTC)

It was good to remove the Python code; what with xrange functions and list comprehensions it was not helpful to anyone not knowing Python. Similarly, the Haskell code is not a good illustration of the algorithm; it might serve as an example of what you can do with functional programing in a couple lines, but only confuses someone trying to grasp the algorithm. I suggest the Haskell stuff be taken out and referred to in an external link.

What the article needs is a simple, straightforward example of implementing the algorithm in some mainstream language (c, Java, JavaScript, Pascal) or pseduocode.

--Mastadonz (talk) 23:33, 28 June 2009 (UTC)

Haskel code is very clean and pure, but Python is more famous and installed on more machines :

def erat(l):
    if not l or l[0]**2>l[-1]:
        return l
    else:
        return [l[0]]+erat([i for i in l[1:] if i%l[0]])

erat(range(2, 100))

--79.95.143.238 (talk) 21:40, 10 March 2010 (UTC)

which is, of course, a trial division algorithm, not the sieve of E. Just sayin'. WillNess (talk) 15:43, 17 June 2011 (UTC)

Python Code in Article is Inefficient

The python code shown in the article makes a fundamental mistake - it ramps up the variable k one step at a time and then redefines the specific index of candidates one at a time. This can be modified to sweep through candidates directly, rather than calling it separately in each instance.

By switching the current code:

       for k in range(2*i, n+1, i):
           candidates[k] = None

directly with the line:

       candidates[2*i::i] = [None] * (n//i - 1)

the run time of the algorithm goes from 6.93 to 2.95 seconds for n = 10^7 and 0.61 to 0.26 for n = 10^6.

This makes no modification to the concept of eratosthenes - it just improves memory access times. This should be changed. —Preceding unsigned comment added by 68.181.223.72 (talk) 02:21, 18 November 2010 (UTC)

• I suppose the question is whether the efficiency of the code is more important than the understanding of the code by amateurs/laymen. While Python programmers specifically and programmers generally may not find it needlessly opaque, it doesn't necessarily serve to clarify the algorithm to other readers. NihilistDandy (talk) 22:45, 7 June 2011 (UTC)
  • i agree. I'd prefer a simple for-loop instead of current version with little-known syntax, even if it is slower. If you care about speed then don't use Python. -- X7q (talk) 18:26, 22 June 2011 (UTC)

Simplicity!

The brilliance of this algorithm is its simplicity. It can easily be understood by a 10 year-old if expressed simply in its original form. Any optimizations or "enhancements" obscure this.

In your edits, please keep it simple, please express it clearly and simply so that even an elementary school student can understand it and carry it out with paper and pencil. To do otherwise detracts from Eratosthenes's discovery and, in large part, actually changes his algorithm.

Remember, programming examples should describe the algorithm, not demonstrate cleverness, language features, or even efficiencies. The simplest expression of the sieve is very efficient.

If you feel the need, please note an speed ups or space savings separately. — Preceding unsigned comment added by Mastadonz (talk • contribs) 15:30, 27 June 2011 (UTC)

• OK, I'm going to change the example to use steps of p, instead of steps of 2p, for simplicity. WillNess (talk) 16:04, 29 June 2011 (UTC)

Example with Odds Only

... but if to follow the original, we should work on odds only. Here's how it'd look like:

To find all the prime numbers less than or equal to 60, proceed as follows.

First generate a list of odd integers from 3 to 60 (2 is the first prime, and no other even number is a prime):

 3  5  7  9  11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59

First number in the list is 3; cross out every 3-rd number in the list after it (by counting up in steps of 6), i.e. all the multiples of 3:

 3  5  7  9  11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59

Next number not yet crossed out in the list after 3 is 5; cross out every 5-th number in the list after it (by counting up in steps of 10), i.e. all the multiples of 5:

 3  5  7  9  11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59

Repeat the same process for 7:

 3  5  7  9  11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59

All the multiples of 11 in the list are already crossed out at this point as they are also multiples of smaller primes (33,55). That is because 11*11 is greater than 60. The numbers left not crossed out in the list at this point are all the prime numbers below 60:

 3  5  7     11 13    17 19    23       29 31       37    41 43    47       53       59

Well, what should it be? The original table in the book in Greek contains only odd numbers! Should this be put into the article? WillNess (talk) 16:44, 29 June 2011 (UTC)

Top image

I have changed the top image from Image:New Animation Sieve of Eratosthenes.gif to File:Animation_Sieve_of_Eratosth-2.gif because in the 1st image some numbers are removed (Striked) multiple times. and the algorithm clearly states:
3. Strike from the list all multiples of p less than or equal to n.
4. Find the first number remaining on the list greater than p (this number is the next prime); replace p with this number.
.

Example

To find all the prime numbers less than or equal to 30, proceed as follows:

First generate a list of integers from 2 to 30:

  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Strike (sift out) the multiples of 2 resulting in:

  2  3     5     7     9    11    13    15    17    19    21    23    25    27    29

The first number in the list after 2 is 3; strike the multiples of 3 from the list to get:

  2  3     5     7          11    13          17    19          23    25          29

The first number in the list after 3 is 5; strike the remaining multiples of 5 from the list:

  2  3     5     7          11    13          17    19          23                29

The first number in the list after 5 is 7, but 7 squared is 49 which is greater than 30 so the
process is finished. The final list consists of all the prime numbers less than or equal to 30.

Requesting discussion and communality review.--IngerAlHaosului (talk) 21:20, 6 September 2009 (UTC)

This is very much a red herring. These two algorithms produce exactly the same results, always. It does not matter if you cross something out once or ten times; it's been removed and isn't a prime. Moreover, using an array-based approach, removing something "multiple" times is very cheap. There are algorithms, such as David Turner's unfaithful sieve, to avoid this duplicated effort, but this particular one turns out to be much worse (i.e. slower) than trial division, which in turn is much slower than a genuine Sieve of Eratosthenes.

David Turner's sieve is not "unfaithful" anything, it just is David Turner's sieve. It is a sieve, as it removes the multiples, gradually, and it does produce prime numbers. This whole "unfaithful" vogue was started by the unfortunately vague and confusing explanations from Melissa O'Neill's article. Turner's sieve is an instance of trial division as it tests each candidate number for divisibility; it is an instance of Euler's sieve as it sequentially culls the initial candidates stream from the multiples of one prime after another, it just uses the stock list comprehensions with rem testing to achieve the same effect. It is a great one-liner which is easily reformulated as an optimal trial division, by postponing the filtering until the right moment (i.e. after the square of a prime is seen). This is all that sieve is. As for the attempts to avoid "needless removals", it just is the distinction between Euler's sieve and that of Eratosthenes, nothing else. WillNess (talk) 15:03, 17 June 2011 (UTC)

There are some efficient algorithms, such as the Sieve of Atkin, that works to eliminate some of this duplicated effort. However it doesn't eliminate all of it, and while the Sieve of Atkin has slightly better asymptotic performance, but unless you are *very* careful and know what you are doing, in practice it suffers from high constant factors. Thus an inexpertly implemented Sieve of Atkin will be slower than the Sieve of Eratosthenes unless you pick an impractically large upper limit.

Ultimately, an animation with X's and O's is much clearer with respect to what is going on than a strictly color-coded animation, and crossing out things multiple times is more representative of real implementations. Thus the original gif undoubtedly deserves to be the animation for this article.

There are several problems with the article itself, but this does not make the replacement animation better than the original. Obscuranym (talk) 03:08, 8 September 2009 (UTC)

I also support the version File:New Animation Sieve of Eratosthenes.gif with X's and multiple strikes. I and many others (probably the large majority) make implementations where multiple strikes are used. The sieve can be represented by an array with 1's and 0's where you can just set sieve[x]=0 every time. If you want to avoid multiple strikes then you have to test first: if sieve[x]==1 then sieve[x]=0. PrimeHunter (talk) 11:17, 8 September 2009 (UTC)

I will abide by the decision of the community, and i apologize for not bringing the matter into discussion sooner.

--IngerAlHaosului (talk) 19:08, 8 September 2009 (UTC)

Just a note, File:Animation_Sieve_of_Eratosth-2.gif is a featured picture which means that it was chosen by the community at one of the best representations of its particular subject. I'm not going to get in an edit war over this, but I find it a bit ridiculous that, of the two, the one that is not WP:FP is currently used. Daniel J Simanek (talk) 19:18, 8 January 2010 (UTC)

File:Animation_Sieve_of_Eratosth-2.gif may or may not be more aesthetically pleasing, but in terms of clarity and accuracy, File:New_Animation_Sieve_of_Eratosthenes.gif wins hands down. With regards to the featured picture status, if you compare timelines at Talk:Sieve_of_Eratosthenes#Possible_improvement_on_picture and Wikipedia:Featured_picture_candidates/Sieve_of_Eratosthenes, you'll see that this was offered as an alternative a few months after the featured candidate was well on it's way through the process, and that the original creator of the revised animation (which is not myself) did not do a good enough job (in my opinion) in promoting his alternative. So maybe somebody should nominate this revised animation as a featured animation? Obscuranym (talk) 11:20, 9 January 2010 (UTC)

It's not FP though, and in fact, it is quite bad in terms of readability and clarity (for example, the circles look "drawn"). I am voting for going back to the shading model with the caveat it meets your accuracy requirements. Does that sound like a reasonable compromise? Daniel J Simanek (talk) 17:07, 11 January 2010 (UTC)

The issue with the circles is that they aren't anti-aliased. I'm actually somewhat less insistent on the final colorings (whether they reflect the smallest or the largest prime divisor) as I am on X's and O's. However, I do think that the featured picture is rather confusing in that regard: if you go back to color determined by the smallest prime divisor, I really think there should be some kind of visual "pulse" at each multiple, whether or not it ends up getting colored. I really don't think the current animation is "quite bad in terms of readability and clarity", but there is almost always room for improvement, of course. Obscuranym (talk) 15:29, 13 January 2010 (UTC)

On clarity: I mean it looks drawn (as you said, it lacks anti-aliasing). How does colored background shading with black X's over the non-primes sound? Also, what are you looking in this "pulse." I guess I'm a bit confused in that regard. Daniel J Simanek (talk) 21:10, 18 January 2010 (UTC)

Black X's on colored backgrounds would certainly be worth considering, although I would need to see an end result before I could give you an informed opinion and I think we should get other people's opinion on the overall visual effect as well. I still don't know what you mean by "drawn" other than anti-aliasing, although I do think that anti-aliasing would certainly improve the visual appeal of the image. As for "pulse", the colored X's give a sense of motion to the image, with the motion occurring at each multiple of a some prime: if one were to color each number by the smallest prime factor, as the featured picture does, this sense of motion is lost. So a "pulse" would be anything that restores this sense of motion: maybe by temporarily making the multiples a bit larger.

Out of curiousity, how do you plan on putting this together? I started to investigate options, very briefly; using some Python library to generate a series of bitmaps and then using ImageMagick to stitch them together into an animated gif might work... Obscuranym (talk) 04:39, 19 January 2010 (UTC)

By drawn I mean it looks like it was colored in with a crayon. I get what you mean by the pulse now, and I'll try to work it in. As for how I am going to do this ... to be honest, I was just going to brute force it with Photoshop. Daniel J Simanek (talk) 22:00, 19 January 2010 (UTC)

Regarding the anti-aliasing, let me add that its absence has its advantages: I just made a change to the image to fix a small bug (some of the multiples weren't being marked multiple times, while most were), and if it had anti-aliasing applied, it would have taken a whole lot more work to edit. And I don't think it looks that bad anyway. Now, maybe if we can have animated SVG sometime in the future... --Waldir ^talk 19:47, 30 April 2011 (UTC)

The original picture isn't as inconsistent as you think it is. With the sieve you can start crossing out multiples of $p$ at $p^{2}$, which is a minor optimization that also takes care of the terminating condition in a rather pleasing way. You could argue that your modified animation is less consistent, because you aren't crossing out all the multiples of 11, 13, 17, etc.

That said, I don't think your modification made the animation significantly worse in the context it serves. It might have even made it better from a pedagogical point of view. Hard to say for sure. Obscuranym (talk) 21:26, 21 July 2011 (UTC)

Reasons to keep Haskell code

In reverting the total removal of all and any material using Haskell code from the article by Justin W Smith (at 14:41, 8 July 2011) my reasons are:

• The first Haskell code gives, in a very succinct manner, the three main forms of sieving: Eratosthenes, Euler's, and (Turner's) trial division. Comparative exposition adds much to understanding IMO. If you can write it in shorter and clearer pseudocode, you're welcome to it (this is not about promoting Haskell).

Plus, with that code removed, we'd have to add some implementation code to the Euler's sieve section.

• The second Haskell code shows an altogether new variety of the sieve: an unbounded one. It serves as conceptual basis for the segmented sieve, mentioned in the article but otherwise not expounded upon. Again, you're welcome to include any shorter and more clear pseudo-code formulation there.

WillNess (talk) 11:54, 9 July 2011 (UTC)

You claim "Haskell code shows an altogether new variety of the sieve", which itself shows this content to be inappropriate. The Haskell code does not provide any clarity to the topic of the article. It demonstrates features of Haskell that are foreign to most other programming languages. See Wikipedia:Algorithms on Wikipedia#Code samples which says

avoid writing sample code unless it contributes significantly to a fundamental understanding of the encyclopedic content.

I think it fails to meet this criterion. Justin W Smith ^talk/_stalk 13:52, 9 July 2011 (UTC)

I might have used not the best formulation; but please notice that article itself speaks of "segmented sieve" for which this code is precisely, the executable pseudo-code. Furthermore, A. the first code IMO does contribute significantly (in my own personal experience) to the understanding of what the sieve is and what is not the sieve, i.e. comparing Eratos' and Euler's and Turner's all in one place (and I think "minus" is very intuitive when read as pseudocode); and B. the second one does contribute to fundamental insight into what the segmented - unbounded - sieve is. Please see the referenced sites, esp. for the optimized C++ sieve which gets to 4 billion-th prime in about 30 seconds ... i.e. is unbounded, i.e. without pre-set upper limit. Same issue referenced in Complexity section, speaking of "segmented sieve". Putting a C++ code fragment, I would expect to be ... impractical. WillNess (talk) 14:44, 9 July 2011 (UTC)

What I'm trying to say, can't you read this code as pseudocode? Is it really that foreign for you? I for instance didn't know Python and its list splicing syntax; I went to its page and read some; I then could discern the intent. Isn't names like "minus" suggestive enough to enable the intent of the code to be readily discerned? Or is it the list pattern-matching that's causing trouble? (i.e. (x:xs) stuff) ? The list comprehension syntax? Maybe it needs to be mentioned somewhere explicitly, to provide a link to its page?

Lastly, what about Euler's sieve implementation that would have to be included were the one at Eratosthenes' be removed? Do you have one in Python readily available? And Turner's code is famous in itself and source of much confusion; mentioning it's not the S. of E. is important, too, IMO. WillNess (talk) 14:52, 9 July 2011 (UTC)

I just wanted to point out that the Haskell code listed in the current version (correctly) points out that Turner's Sieve is in fact hugely inefficient trial division is itself in fact hugely inefficient trial comparisons. The fact that it avoids division doesn't matter so much. So why choose against a well-known piece of code when the alternative presented doesn't really offer any algorithmic insight? I liked the discussion of Turner's Sieve and Melissa O'Neill's Geniune Sieve of Eratosthenes as it existed some time ago. Obscuranym (talk) 17:18, 9 July 2011 (UTC)

• if I parse it correctly (u got some mixup it seems), what you intend to say is that the "eratos" code is just as hugely inefficient as Turner's. This is not the case, by far. It has complexity about the same as optimal trial division, just about $O(n^{1.45})$ empirically, and runs faster. The Turner's sieve has it much above $O(n^{2})$ (both in terms of number of primes produced, not the upper limit -- EDIT: tested when GHC compiled). If that was your impression from that article, then it succeeded in confusing you.

The reason to have it, is precisely because it offers an algorithmic insight IMO. It is an executable pseudocode correctly describing the algorithm (getting rid of multiples of primes as they are found, generating the multiples by counting up). Its actual complexity as Haskell code (while acceptable) does not matter here. "Minus" and the lists could have been just as easily compiled as arrays operations (for the bounded version), behind the scenes, achieving the genuine sieve complexity of O(|b|) for (a `minus` b) operation instead of current O(|a|) for plain lists. Or the lists could've been represented as trees, for O(|b|*log |a|) step complexity. The drawbacks of Haskell compilation current state of the art are of no interest here, only that when read as pseudocode, that code correctly describes the S. of E. algorithm. But it is faster than trial division nevertheless.

The reason the discussion is now gone that was once there, is that some felt it was too Haskell-specific. But the ref into the article was preserved, as the bare minimum, although IMO that article is very confusing. To wit, the unbounded code runs at about same complexities, speed- and memory-wise, as her PQ-based code (the real version, with Wheel, is on "haskellwiki Prime numbers" page) - i.e., empirical complexities of about $\Theta (n^{1.2})$ for speed and nearly constant space (probably $\Theta ((n/\log(n))^{1/2})$ ), to get to the n-th prime (and you'd never guessed it's at all possible, from that article). WillNess (talk) 22:07, 9 July 2011 (UTC)

Well, after trying the code it does _appear_ as though your variant is asymptotically faster than Turner's sieve. However, it isn't clear to me why; eyeballing it I would think that they should be the same, as every number $n$ should get "touched" by every prime number from 3 to $n-1$.

Still, I'd stand by my overall argument; this algorithm's performance appears to be on par with reasonably implemented trial division, but it is much less well known than trial division or Turner's Sieve. So I still doubt there is enough algorithmic insight to really justify its inclusion in the article over Turner's Sieve. Obscuranym (talk) 08:34, 22 July 2011 (UTC)

Firstly, this is the article about SoE, not Turner's sieve. Turner's is the example of what *isn't* SoE. The key to SoE is its enumeration of x's multiples in jumps, steps of x (or 2x): [x*x, x*x+2*x..m]. It's not that it eliminates the primes' multiples (the wrong and misleading line that was here for years in the algo descrption), but *how* does it do it. Answer: in jumps (steps). By direct generation of multiples, and O(1) removal of each. That is the algorithmic insight that the eratos code provides, and although Haskell's minus does not perform well, algorithmically it is exactly what the sieve does. If xs were mutable random access array, and minus were defined for it and performing adequately, we'd see the true sieve's complexity with the same code. Hence its value as pseudocode.

If you're indeed talking about the "eratos" code, the key to its efficiency is having it formulated as bounded - then this is seen in it: [x*x, x*x+2*x..m]. So when x*x reaches over and above m, the list is born empty, and minus a [] = a by definition, so it goes puff into the thin air. Vanishes. So, there are no extraneous filters, doing nothing, here. That's the key. To break it, re-write it with minus (x:xs) [] = x:minus xs []. The problem will re-appear.

To explicate this we can write:

primesTo m = 2 : eratos [3,5..m] where
 eratos (x:xs) | x*x > m = x:xs
               | True = x:eratos(xs `minus` [x*x, x*x+2*x..m])

If you add this explicit guard into Turner's code, it suddenly too becomes a good citizen with cpxty of optimal trial division. That is so because with guard, no extraneous filters are created at all:

primesTo m = 2 : turners [3,5..m] where
 turners(x:xs) | x*x > m = x:xs
               | True = x:turners(filter ((/=0).(`rem`x)) xs)

The problem with M O'Neill article is that it never deals with this simple issue. WillNess (talk) 19:53, 22 July 2011 (UTC)

Code removals

Now that the article has no Euler's sieve implementation; no comparative exposition nor even a mention of Trial division; no one-liner for unbounded sieve (how's a one-liner a "code repository"?); HOW EXACTLY does it make the article better?

Removing code is one thing; carelessly removing all the discussions that went along with it, all references and links, is an altogether different thing entirely. This removal looks to me like a licensed vandalism under pretense of WP policy. WillNess (talk) 20:25, 18 July 2011 (UTC)

Euler's sieve has a section already; it might be appropriate to have a pseudocode implementation for it in that section. As for "Turner's sieve" or "unbounded sieve", I'm not sure there's sufficient reason to even mention them. Concerning the use of Haskell code: except for articles about Haskell, I see no reason to use Haskell code in a Wikipedia article. Wikipedia articles should be accessible to as wide of an audience as possible. Haskell code is readable by a only small subset of computer programmers. Discussions about the use of "code" on Wikipedia have been going on for years. There seems to be consensus formed on Wikipedia around the use of pseudocode, sparingly, specifically for the purposes for clarifying an article. Justin W Smith ^talk/_stalk 00:28, 19 July 2011 (UTC)

I agree on the removal of the code, and with the changing of the other code to pseudocode. On the other hand (see my section below) I do think that Turner's sieve should be mentioned as it is often (incorrectly) used as an example of the Sieve of Eratosthenes. CRGreathouse (t | c) 02:35, 19 July 2011 (UTC)

you agree with yourself on the removal of the code? It is you who removed it. Wait, you've also removed all the discussion that accompanied those code snippets. It was you that left an article in incomprehensible state with broken references. Do you agree with yourself on that too? WillNess (talk) 07:58, 19 July 2011 (UTC)

I agree with Justin W Smith's removal of the source code [1] and with your [2] change of the existing code to pseudocode. I appreciate your getting the ref from history; I didn't realize the article was (incorrectly) using "ibid". CRGreathouse (t | c) 13:10, 19 July 2011 (UTC)

He removed much more than just source code. The only code in violation of No-Repository was CLojure code (and it was wrong anyway). I tried to delete that one before; someone has re-inserted it apparently. Sure it had to be deleted, it was just another code with no discussion, nothing.

But the Haskell code snippets served as base for much discussion and references (much more of it, in the past). They were practically pseudocode themselves. Them being a basis for discussion etc., surely they should NOT have been just removed - but REPLACED if need be. Yet it all been removed, vandalized, valuable insights eliminated, comparative exposition gone, article flow disrupted, butchered. By him, then, and by you, now. I've given plenty reasons above why that should NOT be done. Valid still. WillNess (talk) 19:18, 19 July 2011 (UTC)

Hey, let's also remove all mention of segmented (unbound) sieve from the Complexity section. Hey, let's find what else can we remove from the article. There really is no point in providing any points for an interested reader to explore further any related context, now is there. Hey, let's remove all the external links too, especially that one ultra-fast and efficient C++ that implements segmented (unbounded) sieve that finds billions of primes in half a minute. No reason to mention that, according to your logic.

But if you suppose Euler's sieve could benefit from pseudocode, why wouldn't you add it there, instead of rampant removals? If Haskell is so inaccessible (I disagree) please write a clearer pseudocode and replace the Haskell pseudo-code with it. Don't just remove, replace. WillNess (talk) 07:58, 19 July 2011 (UTC)

I'm not sure what or who this is in response to. Presumably not me, since I'm the one advocating re-adding the explanation of the sieve.

In any case material on the Euler sieve belongs on that article and not here.

CRGreathouse (t | c) 13:10, 19 July 2011 (UTC)

Good grief, you don't even realize that Euler' sieve is a part of this article. WillNess (talk) 18:48, 19 July 2011 (UTC)

Efficient Haskell list-based code

Just for the reference, it is

 {-# OPTIONS_GHC -O2 -fno-cse #-}
 primes = 2 : ([3,5..] `minus` join [[p*p,p*p+2*p..] | p <- primes']) 
    where 
      primes' = 3 : ([5,7..] `minus` join [[p*p,p*p+2*p..] | p <- primes'])
      join  ((x:xs):t)    = x : union xs (join (pairs t))
      pairs ((x:xs):ys:t) = (x : union xs ys) : pairs t

Looks like it's a good candidate for parallelization, and it is unbounded. It runs at about the same complexity as Melissa O'Neill's code ( $O(n^{1.24})$ vs. $O(n^{1.2})$ in number of primes produced), and about 1.2x slower overall. It is OR though; original idea of tree-like folding is due to Dave Bayer, on haskell-cafe mailing list, and double-feed for primes with no common sub-expression sharing is due to Melissa O'Neill, in her article (in order to minimize space consumption). I've come up with this particularly short and clear formulation as part of discussions on haskell-cafe. More at Haskellwiki's prime numbers page, including further improvement (more than twice speedup) to the above with wheel factorization optimization.

join can be treated as an abstraction, in need of concrete implementation, to thus arrive at the following one-liner which arguably captures the essence of the sieve (forgoing the double feed for the sake of brevity - though space complexity will worsen - and using the unionAll name instead which actually is implemented in Data.List.Ordered package along with union and minus),

 primes = 2 : 3 : ([5,7..] `minus` 
                     unionAll [[p*p, p*p+2*p..] | p <- tail primes])

although it is certainly an unorthodox one. I wonder if it has a place in the article itself. Is it? WillNess (talk) 19:53, 19 June 2011 (UTC)

• of the course the original idea itself of primes as difference between numbers and composites is due to Richard Bird, as discussed in M. O'Neill's JFP article, although he used linear folding (I've added the reference to it in our article's body). WillNess (talk) 16:03, 29 June 2011 (UTC)

• • BTW the one-liner formulation of Euler's sieve use in the article is due to Daniel Fischer, on haskell-cafe mailing list. WillNess (talk) 10:48, 30 June 2011 (UTC)

It appears that you came up with these algorithmic "bounds" via empirical observation. This is not how to calculate $O(f(n))$. Obscuranym (talk) 17:23, 9 July 2011 (UTC)

• • I should've used the word "empirical" explicitly. I did not claim this to be a result of any calculation. Nor did O'Neill in fact provided any claims or derivations thereof about her Priority Queue-based code's complexity. I said "it runs at" and gave the link to the running code. The observed facts remain as stated above. The code remains a faithful rendition of the algo, when read as pseudocode, IMO. WillNess (talk) 08:09, 10 July 2011 (UTC)

Melissa O'Neill did in fact explicitly claim an asymptotic complexity for her algorithm, see page 6 of her paper. Obscuranym (talk) 08:18, 22 July 2011 (UTC)

Thanks, no, that's about her Map based variant. She gives no complexity guarantees about her PQ implementation. WillNess (talk) 15:23, 25 July 2011 (UTC)

Article issues

Here are some thoughts on improving the article, in no particular order.

• The article often uses informal/unencyclopedic/pedantic phrasing: "it's OK to stop", "This actually appears", "proceed as follows", etc.
• The article uses ibid in citations.
• Overuse of italics
• Problematic implementations. It may be best to link to several high-quality implementations and use the text to describe them. This could give a wider variety of details while addressing the verifiability concerns raised by RDBury and others.
• The mnemonic should not have a section, though I don't object to its use as a pullquote.
• The Euler sieve needs to be spun off into an article, though it may be better to simple write an article from scratch.
• It would be nice to have a section comparing different forms of this sieve as well as contrasting it with different sieves.
• The external links should probably be vetted carefully. I'm not sure what standard should be used to decide which to keep; WP:EL has general guidelines.

Comments or other thoughts on improving the article would be welcome. I'd especially like suggestions on expanding the article (new sections to add or material to add to existing sections).

CRGreathouse (t | c) 15:14, 22 July 2011 (UTC)

This article was fine before your second coming. A recommendation on improving the article would be for you to leave it alone, unthreatened by your removals and OR. WillNess (talk) 18:29, 22 July 2011 (UTC)

Funny, I might have said the same to you. CRGreathouse (t | c) 18:59, 22 July 2011 (UTC)

You might but that would have been without merit. I always engaged other editors, always incorporated their suggestions, accepted others' opinions when well founded and based in sound argument, as is evident on the page history. You OTOH in the short period of a few days have demonstrated absolute dismissiveness, arrogance, disregard of others opinion not even providing any meaningful argumentation to your wholesale removals. Anything you dont seem to like must go; anything you like must go in however badly sourced if at all. WillNess (talk) 11:41, 23 July 2011 (UTC)

You certainly seem to think so. CRGreathouse (t | c) 15:58, 24 July 2011 (UTC)

Segmented sieve

The statement as it is written now, says "is usually chosen so that" etc. So it may or may not relate to cache size; but it usually does. Simply saying "when it doesn't fit, it's segmented" is confusing and wrong. It could be a run-time error just as well when it doesn't fit. It is not by accident that it doesn't fit; it is by design. Segmented sieve may be chosen even if the whole array could fit in a given memory. WillNess (talk) 11:54, 21 July 2011 (UTC)

That's why I chose "doesn't fit" rather than "is too large for". Feel free to improve phrasing. But don't define it in terms of cache size; that's an implementation detail. We can mention it, if you like -- though it would probably need a citation. (I think TOeS has a page that would work.) But changing it from 'segmented = out-of-memory' to 'segmented = cache-size' is as silly as changing 'car = motorized vehicle' to 'car = made of metal': yes, cars are usually made of metal (though not always!), but that's not their defining trait.

CRGreathouse (t | c) 18:43, 21 July 2011 (UTC)

Have I defined it in terms of cache size? Certainly not. Where did you get that idea? Are you paying enough attention? Am I speaking English? Are you? What I wrote is exactly right. AND I gave you a citation - a reference. Why you keep ignoring that reference? Actually, your edit is unsourced; mine is. So until you can provide us with sources, please refrain from eliminating valid sourced content from the article, especially when you eliminate references to its source, with it (eliminating the evidence so to speak).

Your wording makes no sence. THe array does not "fit" or "not fit" all by itself. It it the programmer that chooses the array to be of whatever size, and USUALLY he chooses it to be small enough to fit into cache. That is what the referenced source is saying. Look into it. I gave a page number. "Usually" in English means, "not necessarily", so your critique is uncalled for.

Plus, there is NO "array of potential primes". No such thing. The abstract formulation refers to sequences which are generated one by one, without bound. THis is simulated by a fixed-sized arrray, can not be otherwise (with arrays that is). This is what segmented means. THis is what my wording is saying. Please cease; if you're unsatisfied with my reasons here, please start up a dispute somehwere, call some expert to arbiter it etc. But please do not put unsourced material which is worded incomprehensibly into the article.

I've removed any mention of cache size from article body; it's there in the reference text, though it is way down and in small script. I think it makes it harder for a reader to get this relevant detail; you are the reason for it.

Lastly, what is TOeS, please? WillNess (talk) 11:45, 22 July 2011 (UTC)

TOeS is Tomás Oliveira e Silva, a major researcher in the field.

CRGreathouse (t | c) 14:31, 22 July 2011 (UTC)

Well I can only treat you like an arrogant ignorant vandal at this point. U certainly act like one. What long slumber have you awakened from, and why? The article was in so much better shape before you've returned here, except an occasional misused definite article. WillNess (talk) 18:19, 22 July 2011 (UTC)

Please try to hold your tongue the above is clear breach of WP:CIVIL and WP:AGF. You might consider retracting the above.--Salix (talk): 12:13, 23 July 2011 (UTC)

So to do actual harm is ok if you're civil and cold about it? And to protest the harmful actions is uncivil? WillNess (talk) 14:12, 23 July 2011 (UTC)

Thank you for the pointers. I've read up on those now (and no, I don't like to be forced to become wikilegalist instead of just relying on good will of others); WP:CIVIL has "deliberately pushing others to the point of breaching civility even if not seeming to commit such a breach themselves" under "2. Other uncivil behaviors". I feel very much it was that way, when the other editor proceeded with unilateral edits, absolutely ignoring any my attempts at discussion on talk page (one clear example is right above this point in the discussion thread). And that in itself is in breach of WP:CONSENSUS and falls under WP:DISRUPTIVE. WillNess (talk) 13:09, 24 July 2011 (UTC)

So far you seem to be the only one who feels that way. CRGreathouse (t | c) 19:00, 22 July 2011 (UTC)

And what does that prove? WillNess (talk) 19:55, 22 July 2011 (UTC)

That you don't have WP:CONSENSUS, I suppose. CRGreathouse (t | c) 20:06, 22 July 2011 (UTC)

And do you have concensus for your edits and removals and non-sensical non-sourced OR re-writes? I engage in discussion with you, you give me no response - ZERO - to any of my arguments here on talk page - and just act out as you feel pleased. WillNess (talk) 20:20, 22 July 2011 (UTC)

I guess we'll find out. I asked WikiProject Mathematics earlier to send some editors over to look at the article. CRGreathouse (t | c) 05:50, 23 July 2011 (UTC)

Here's to sum up the end result of that discussion on WPM talk page: referring to your original removal of the parts of article with Haskell code: your removal is upheld. There shall be no Haskell code in the article. It is in violation of WP:TECHNICAL.

To which, as is plain in article's history, I did not take any action to revert it in the first place. What I've objected to, and still am, is the careless and dismissive way in which you did it, without any discussion. And judging from your talk page, I'm not the first person to raise this concern towards you. Maybe you'd take notice. WillNess (talk) 08:26, 26 July 2011 (UTC)

The sourcing given to a description of segmented sieve as it appears now inside Implementation section, appears to refer to a blog. The "about" section on the page referenced says, "This blog is Copyright © 2009 by Programming Praxis of Saint Louis, Missouri, USA." It appears that blogs can not be used as sources; furthermore, there are copyright issues here it seems. I'm reinstating the tag. If no proper sourcing will be provided for said paragraph it will probably have to be removed after some period (say two weeks?). Or is it immediately that the copyright material should be removed? Im no Wikilegalist, so someone please chime in. WillNess (talk) 10:52, 23 July 2011 (UTC)

• And now becomes clear the source of the CRGreathouse's refusal to allow any reference to a cache memory: it is because his/her favorite blog source is ignorant of the matter. My phrasing in this regard was well sourced giving an exact page numer in the article ina peer reviewed journal; CRGreathouse just removed it wholesale without regard to the sourcing, and without ever engaging in any discussion about it, in completely dismissive and unilateral manner - based on their favorite blog as it now becomes clear. That's unhelpful, arrogant, careless. WillNess (talk) 11:30, 23 July 2011 (UTC)

I like online sources because they let readers follow along. (Contrary to your assertion, that's not a 'favorite blog' of mine in any way, just a convenient source.) But I've added the reference I told you I would add, to a high-quality text on computational number theory. CRGreathouse (t | c) 17:39, 24 July 2011 (UTC)

Segmented sieves

(addressing CRGreathouse)

Please engage in discussions on the article's talk page, not in comments of your edits. Thank you.

Are you saying using blogs as sources is OK? You continue to edit disruptively, without discussing it first on the talk page and building up a consensus. Could you please correct this. Thanks.

When you have a proper reference, please do add it into the article. Referencing blogs is not OK. WillNess (talk) 15:09, 23 July 2011 (UTC)

I've added a separate request for a source in that paragraph about segmented sieves. There are two separate claims there: that the (sole? main?) reason to use segmented sieve is because it won't fit as a whole; and the other sentence about in- and out-of-memory sieves. To your attention, please. WillNess (talk) 12:54, 24 July 2011 (UTC)

There's another problem with the first part of that paragraph: it is wrong. It says "In these cases it is necessary to use a segmented sieve" but that is patently not true. For example, Melissa O'Neill has demonstrated in her article a priority queue-based solution which uses no array at all (to sieve on, that is), and is purely incremental. And segmented sieve is specifically about using a smaller array, but arrays are not explicitly mentioned at all in that sentence. It will have to be rephrased, it seems. WillNess (talk) 13:43, 24 July 2011 (UTC)

I added a source which does actually say that it's necessary (page 121). Of course strictly there are ways around; a more inventive one than O'Neil's is Sorenson's which I have also added to the article. (I love the O'Neil article, but of course its purpose is different from Sorenson's.)

Segmenting a sieve is data-structure agnostic; it doesn't depend specifically on using an array rather than a queue.

CRGreathouse (t | c) 15:55, 24 July 2011 (UTC)

I don't like the ONeill article one bit, I think it's confused and confusing, making a straw-man argument with the focus on Turner's sieve as much as it does, when simply following the proper definition of the sieve (i.e. as being bounded) and then adding in the squares optimization (which she ridiculously claims to have no effect on complexity ... which is true of imperative sieves that is, but she is dealing with Haskell code implementation, isn't she) would bring its complexity down to that of an optimal trial division and take the punch out of her message. Moreover, the Bird's code, which she so easily dismisses, needs only be augmented slightly to get to the (empirical) complexity essentially the same as hers, and about 10 times shorter and more readily comprehensible at that. Plus, after all the innuendo, she never actually makes even one claim as per her code's complexity, nor analyzes it nor does attempt to prove it. She relies on someone else's PQ implementation without ever stating complexity guarantees for it. Is her PQ code really an O(1) PQ? She never even says it should be.

When you say it doesn't depend on using an array but rather a queue, what do you mean by that? I understood PQ-based sieve not being segmented, but rather incremental, producing primes not in segments, but one-by-one. WillNess (talk) 10:56, 25 July 2011 (UTC)

Rephrasing for your benefit: whether a sieve uses an array, a queue, or some other data structure is immaterial in determining whether it is segmented or not. CRGreathouse (t | c) 03:53, 26 July 2011 (UTC)

What is pseudocode?

I raised this question on Wikipedia_talk:WikiProject_Mathematics#What_is_pseudocode.3F. For simplicity, we should have this conversation there. Thanks, Justin W Smith ^talk/_stalk 19:14, 19 July 2011 (UTC)

FYI. I also raised the question on Wikipedia_talk:WikiProject_Computer_science#What_is_psuedocode.3F. Justin W Smith ^talk/_stalk 19:19, 19 July 2011 (UTC)

• Whatever it is, you just keep erasing instead of changing. By all means, change it into what you see as more fit, preserving the discussion. Don't keep erasing all the text that goes along with it.
• I intend on reinstating the comparative exposition of the matter. Translation: to add pseudocode into Euler sieve section along with pointers into trial division article, and maybe pseudocode for it here as well, for a reader to be able to compare and see - so the Turner code does have its place here, for more than one reason. And it is in Haskell, so what are we to do? Return the Haskell code after all? It should be discussed, but it can't be discussed because you keep bloody erasing everything. Your blatant careless removals of massive amounts of valid TEXT as well as code snippets, have not been much encouraging let me tell you. You are this close to breaking me; then the article will be left to your mercy, and responsibility. So far, I haven't seen much evidence for your acting in a responsible manner. WillNess (talk) 19:50, 19 July 2011 (UTC)

Neither of the pseudocode sections is referenced so I'd say the argument is over the wrong issue. Provide a source for the added material, if that source describes it as pseudocode then we can call it pseudocode. If you're adding material you've created yourself based on the text then it's OR and should be removed. The WP:VERIFY policy will prevent this kind of argument if followed.--RDBury (talk) 20:19, 19 July 2011 (UTC)

If we weren't allowed to interpret sources, Wikipedia would turn into Wikiquote. Which it is not. Both fragments restate what the sourced descriptions are saying. It is verifiable by anyone knowledgeable in the subject matter. WillNess (talk) 06:27, 20 July 2011 (UTC)

• Also, the links in the text are not only to "higher-order functions", but to other articles about general concepts as well; and they are there not to "explain" the pseudocode, but to provide context to it, and pointers for further exploration. "Set difference" operation or "mapEach" is self-explanatory. But if you don't like this, we can restore the previous one-liner. It is shorter, and clearer, IMO; aided understanding and was not executable code in itself; as such no violation of WP:NOTREPOSITORY. IMO. It had one drawack of being a Hskell code; but if you have anything just as short and clear in Basic, let's use it instead. I have no objections. WillNess (talk) 21:02, 19 July 2011 (UTC)

I'm on the fence on this one, but I'm tending to agree with Justin W Smith and RDBury here. Unfortunately neither of the WikiProjects seem to have taken up the discussion.

One nitpick: I don't find the set difference to be self-explanatory at all; I can think of four definitions off the top of my head ($A-B=\{a-b:a\in A,b\in B\}$, $A\setminus B=\{x:x\in A,x\not \in B\}$, $d((A_{i}))=(A_{i+1}-A_{i})$, $(A_{i})-(B_{i})=(A_{i}-B_{i})$) and I think a reasonable reader might be caught between two or more of them -- or worse, might think it's one of the others and not check the link.

CRGreathouse (t | c) 18:52, 21 July 2011 (UTC)

A reasonable reader need only click the link and learn about the issue he's ignorant about, before even attempting editing the article. Wait, you'd need also to be humble and careful-minded for that. WillNess (talk) 18:35, 22 July 2011 (UTC)

Interesting how you changed from third person to second person there, almost as though you were shifting blame. CRGreathouse (t | c) 03:56, 26 July 2011 (UTC)

Why shifting? I was replying to you, I couldn't imagine for the life of me that you were serious in objecting to the well known and basic notion of set difference. I still can't, but now I know that you're anything but ignorant in maths. WillNess (talk) 08:38, 26 July 2011 (UTC)

You changed from talking about a reasonable reader (who may and may not click on links—there are quite a few to click on in that section) to talking about me as an editor. That's inappropriate here; the focus should be on the article and its readers, not the editors.

As for set difference, I don't think it's clear because of the large number of alternate possibilities. Perhaps a different phrasing would help, like "relative complement" which doesn't have other meanings that I'm aware of (at least off the top of my head). What do you think?

CRGreathouse (t | c) 15:42, 26 July 2011 (UTC)

The set difference concept is elementary. The very words in that - long removed - sentence were linkified (just as they're now), so all you ever needed to do to see what is meant by it was just click. There was no possibility of confusion. I couldn't - and still can't - expect of any reasonable person to raise such an improbable claim, in that context. WillNess (talk) 18:04, 26 July 2011 (UTC)

As for using advanced (arcane?) terminology, it's appropriate in PhD dissertations, not in WP article that ought to be accessible to a bright 8 year old. WillNess (talk) 18:07, 26 July 2011 (UTC)

All of the concepts I mentioned are (1) elementary and (2) referred to by that name. Just because you're apparently not familiar with them doesn't mean they don't exist. CRGreathouse (t | c) 18:08, 26 July 2011 (UTC)

It's not me we're talking about, it's a bright 8 year-old who knows how to clink on links, remember? WillNess (talk) 22:03, 26 July 2011 (UTC)

You may have noticed that there are many links and that most people follow only a small percentage of links on a page. Wording clearly to avoid these ambiguities is important, n'est pas? CRGreathouse (t | c) 04:53, 27 July 2011 (UTC)

You've stated your worry about a reasonable reader being confused when seeing the words set difference. A reasonable reader would naturally click on the link if they felt confused; although if they did they'd found themselves right at the description of it - not at any kind of disambiguation page. So in the end there seems to not be any ambiguity there after all. And in case you haven't noticed, that paragraph is not in the article anymore, no need to cry over spilled water. WillNess (talk) 11:04, 27 July 2011 (UTC)

My concern, as previously stated, is for the reader who may think of another of the definitions and not realize that this is the intended one, rather than those who can't think of any definition at all. CRGreathouse (t | c) 13:59, 27 July 2011 (UTC)

The former will be much less numerous than the latter, and out of them most will have basic grasp of sets and set difference, as it is a well known concept amongs programmers for example.

Are you planning to bring that "pseudocode" back? The experts would readily realize it's about composites being taken out from odds, I'm sure, so I don't anticipate anyone to have problems with that. WillNess (talk) 14:10, 27 July 2011 (UTC)

Unbounded sieve

As it is written now, the sentence incorrectly transmits the contents of cited material, and has a redundant last part. "Incrementally" already means "creating output values one by one". That is not what it is about: the previous formulation, in less pretty English but more correctly IMO described the algorithm, as " [generating] primes incrementally by interleaving" (1) "the generation and removal of primes' multiples, and" (2) "the creation of the output values one by one." I.e. this is how the incrementality is achieved, by interleaving the two activities.

BTW the "removal" can be fused into "creation", so it could be phrased as "interleaving the generation of multiples and creation of output values one by one", although it is a refinement upon a code as present in the article (which is what the previous version describes).

I propose we go back to that previous formulation, or the second one. WillNess (talk) 18:20, 25 July 2011 (UTC)

I'm not sure what you're suggesting, exactly. You say you don't like the redundancy of "incrementally" with "creating output values one by one" but you seem to suggest replacing it with 'generating primes incrementally by interleaving the generation and removal of primes' multiples, and the creation of the output values one by one' which has the same feature. Do I misunderstand, or did you not paste/type what you intended to?

Maybe you can quote the exact text you'd like to replace and the exact text you're proposing (say, one paragraph each) so we can see them in context?

CRGreathouse (t | c) 03:42, 26 July 2011 (UTC)

"As it is written now, the sentence incorrectly transmits the contents of cited material," I wrote. That is the main objection to the current phrasing. The secondary objection to the current phrasing is that it is redundant. But it is invalid anyway, see 1st objection.

There are two options, as I see it.

1. revert to the previous wording. I do not see it having the same feature. I parse it as I indicated above.
2. use this instead: "An unbounded formulation of the sieve[6] generates primes incrementally by interleaving the generation of primes' multiples, and the creation of the output values one by one." WillNess (talk) 08:00, 26 July 2011 (UTC)

I certainly don't want incorrect material in the article, but you're still not saying just what you feel is incorrect about the current version. Your other objection, as I pointed out above, applies to the text you suggest. So what, precisely, is wrong with the current text? I'm sure we can come up with a version that avoids both problems but I want to make sure I properly understand what you're objecting to before I suggest anything. If it's sufficiently difficult I'll compare wordings in different sources to see what kind of consensus exists. CRGreathouse (t | c) 15:31, 26 July 2011 (UTC)

No, my phrasing has no problem. Incrementality is ability to generate output one-by-one, and one of operations of the algorithm is the generation of output values, one by one. It is interleaved with the other two. WillNess (talk) 21:55, 26 July 2011 (UTC)

I think we're going to need a WP:RS for that name, then. All the sources I have access to use "incremental" rather than "unbounded". CRGreathouse (t | c) 04:58, 27 July 2011 (UTC)

Was I ever objecting to the name change? Have you ever proposed one? If you have sources, go ahead and make edits with accordance with them, what could be the reason not to? WillNess (talk) 10:53, 27 July 2011 (UTC)

I have: "incremental sieve". CRGreathouse (t | c) 12:55, 27 July 2011 (UTC)

I trust you to find the best way to write this down, according to sources. I still think that that algorithm deserves mentioning; there's a thing though, that it appears there without much description, in that famous and well known, in some circles at least, article, so we'd be forced to describe it in our own words. WillNess (talk) 13:31, 27 July 2011 (UTC)

I agree. CRGreathouse (t | c) 13:53, 27 July 2011 (UTC)

Turner's sieve

This paragraph was removed from the article:

The famous 1975 David Turner's code is actually a hugely inefficient variant of trial division algorithm, doing much superfluous testing by many filters that it creates prematurely.

I think this is actually an important thing to mention in the article, because (contrary to the use of scare quotes on 'famous' on the description of the edit removing this) it *is* a famous piece of code that is often quoted. I would have re-inserted it but I wasn't sure where to put it -- originally it had been in a 'defining' section which doesn't seem quite right.

CRGreathouse (t | c) 02:34, 19 July 2011 (UTC)

you have only yourself to blame for this, because your wild and careless removal of all the code and discussion that went along with it left that paragraph totally without context. So go ahead and spend your time in fixing the article that you have butchered. WillNess (talk) 07:44, 19 July 2011 (UTC)

It was in the wrong place before. Had Justin W Smith not removed the material I would still have placed this request, but as a "where should this be moved" rather than a "where should this be restored". CRGreathouse (t | c) 13:11, 19 July 2011 (UTC)

That one out-of-context little paragraph was left hanging after YOUR careless deletion of all the discussions, based on code snippets, that were there. And it was exactly were it belonged, part of longer comparative exposition, forced to be drastically shortened because of ojections of others like yourself and that other happy content-eraser. Let's just delete the article altogether, yes?

You of course are in no position at all to judge whether it was in the right place. You are not even familiar with the article; you don't know Euler's sieve is a part of it. WillNess (talk) 18:54, 19 July 2011 (UTC)

I intentionally left the paragraph there for lack of a better place.

I'm quite familiar with the article, it's been on my watchlist for years. If you like you can go to the history to see which of us edited it first; I couldn't tell you offhand.

CRGreathouse (t | c) 20:25, 19 July 2011 (UTC)

I never claimed bad faith on your part btw, I said it was careless of you to remove all the text that you did, that was alongside the code. Plus, the Haskell one-liner for unbounded sieve was not an executable code by itself; could be read as pseudocode; was much shorter than pseudocode replacement which was one of the reasons to keep it, as I put above in the discussion. You could voice your disagreement, and have a discussion; you could edit it; instead you just threw it all away. In good faith no doubt. WillNess (talk) 20:36, 19 July 2011 (UTC)

The removal of source code is a pretty well-established policy here; it's not at all unusual or objectionable that I took it out. You would have been better served putting it on the Talk page before attempting to add it -- this would have sidestepped the whole issue. But you didn't, so that brings us to the question I raised following Justin's removal: where can we put this information in the article? If you don't think it belongs here then I suppose that's fine; I know you have an axe to grind against O'Neil or her article. But let's focus on productive things like what to do with the article now rather than what might have been. CRGreathouse (t | c) 04:01, 26 July 2011 (UTC)

Haskell code was in article for years. The code that I added to it, was for months on the article; no one has objected to it. For months - before Justin W Smith raised the issue. The well established policy for removing massive chunks of article that were on it for months and years - i.e. were in WP:CONSENSUS - is through first proposing the removal on talk page. You did nothing of the sorts.

There was already ongoing discussion about Haskell code removals by Justin W Smith. I've raised arguments in support to keeping the section with the code and accompanying discussion. You should've posted your objections there, before removing anything. You didn't, and acted contrary to the well established policy of consensus building. It is a fact plain for all to see, as clear as day. WillNess (talk) 08:58, 26 July 2011 (UTC)

I also take grave offense and very much resent your baseless accusation that I have anything personally against Melissa O'Neill.

To your question: IMO the proper place to put the information about Turner's sieve is in a separate section, with comparative exploration of it and Euler's sieve and the sieve of E. WillNess (talk) 09:30, 26 July 2011 (UTC)

On O'Neil: I used a disjunction, not a conjunction, so your offense is misplaced. But my apologies for the confusion (and any hurt it caused).

You think it deserves its own section? That seems a bit much to me. I was thinking more along the lines of a history section. What do other editors think?

CRGreathouse (t | c) 15:45, 26 July 2011 (UTC)

I've never said it deserves its own section. WillNess (talk) 17:54, 26 July 2011 (UTC)

Did I misunderstand "IMO the proper place to put the information about Turner's sieve is in a separate section"? CRGreathouse (t | c) 18:07, 26 July 2011 (UTC)

Apparently you don't understand that selective quotation might be misleading, and that comma does not usually end a sentence. WillNess (talk) 22:00, 26 July 2011 (UTC)

In that case I ask again: what do you think should become of this paragraph? CRGreathouse (t | c) 04:50, 27 July 2011 (UTC)

As I've aready said above, IMO it should be a part of a separate section, the one with comparative exploration of it, and Euler's sieve, and the sieve of E. Why do you make me repeat myself? WillNess (talk) 11:24, 27 July 2011 (UTC)

Because you wrote "I've never said it deserves its own section." I don't think this should be in its own section but I'd be willing to consider arguments for it if you'd give them instead of wavering. CRGreathouse (t | c) 15:03, 28 July 2011 (UTC)

Here's for the third time: IMO a separate section in the article would be beneficial, that would contain a comparative exposition of Turner's, Euler's and Eratosthenes' sieve (kinda like we had before). Turner's would necessarily be a part of it. That is not "its own" section now is it. The other two would feature in it as well, plus further pointers to wheel factorization etc. could also be added there. WillNess (talk) 15:53, 31 July 2011 (UTC)

Comments on edit to algo description by Gandalf61 followed by a long and unrelated argument about the use of the word "consecutive"

Hi, your edit is wrong. Sieve of E. does not "remove" anything from the list. This wording is highly suggestive in the wrong direction. The whole point to the SoE is that it only marks the composites, not removes them, to not disrupt the counting. With some elements removed, direct addressing is not possible, and actual values of items will have to be examined. The advertised algo complexity will be severely affected.

Moreover, to say "multiples will be removed" is wrong, as it does not preclude all numbers just being tested for divisibility and thus found multiples being deleted; but this is trial division and not the SoE. We do not remove multiples in SoE; we cross out numbers found in succession of increments, and these numbers are the multiples, by construction. That's where the gain in speed comes from.

Lastly, the integers from 2 to n must be consecutive. If not, it is impossible to count up on them. The actual values would have to be examined, with the same consequences as stated above. WillNess (talk) 14:57, 23 July 2011 (UTC)

Addressing only the last point: Actually there are versions that do not use consecutive numbers at all. Perhaps I will write a section when I have time. CRGreathouse (t | c) 15:57, 24 July 2011 (UTC)

What is it, could you please give us a hint, a pointer? Are you referring to wheels, or is there something else? Thanks. WillNess (talk) 11:11, 25 July 2011 (UTC)

No, I wasn't talking about wheel sieves (though I suppose those are a sort of trivial example). [3] would be one example of what I was referring to. There are of course a multitude of others. CRGreathouse (t | c) 03:55, 26 July 2011 (UTC)

Do you consider that sieve to be a sieve of Eratosthenes? The word "consecutive" to which you've objected, is used in the description of the Sieve of Eratosthenes. WillNess (talk) 08:09, 26 July 2011 (UTC)

It's usually considered such in the literature. (There are more extreme examples that would not be.) CRGreathouse (t | c) 15:32, 26 July 2011 (UTC)

Is it a basic sieve of E though? Please take note of #Simplicity! section above. It seems to be in WP:CONSENSUS. WillNess (talk) 18:11, 26 July 2011 (UTC)

Certainly we're not limiting ourselves only to the most basic version or we wouldn't discuss the various optimizations or the "unbounded" version (I think it's usually referred to as an incremental sieve). So in keeping with the wishes expressed above (with which I agree, FWIW) we shouldn't use that as our primary explanation or in whatever pseudocode we might include, but it may be worth mentioning in the text. But even if it's not -- and I'm not rushing to include it, I'd rather polish the rest before I go into this -- we shouldn't make false claims in the article. CRGreathouse (t | c) 19:16, 26 July 2011 (UTC)

Are you saying the basic version of SoE does not necessarily use consecutive numbers? Is that not what we describe in the "algorithm description"? Is that not the consensus of #Simplicity! section, to keep the description of a basic SoE as simple as possible, to be "easily understood by a 10 year old"? WillNess (talk) 22:18, 26 July 2011 (UTC)

I'm saying that the article should not make false claims. Is that difficult to understand? If we're talking about swans, and you think that a reader would be confused by the mention of black swans, I might acquiesce, or at least not mention the black swans in the introduction. But I would object to saying, "swans, which are always white," even in the introduction. CRGreathouse (t | c) 04:57, 27 July 2011 (UTC)

So why won't you make an edit along these lines then. Remember that the introduction describes the basic SoE, more or less like it was done by E himself. If he didn't use consecutive integers, remove that word then. If he did, don't remove it. If you feel compelled to add some more explanations into the lead, why not? What seems to be the problem? WillNess (talk) 10:58, 27 July 2011 (UTC)

Of course as far as we know he didn't use consecutive integers but rather started with the odds. I think I will make the change; I was just trying to discuss it here first since you've repeatedly complained when I make WP:BOLD changes. CRGreathouse (t | c) 12:56, 27 July 2011 (UTC)

Consecutive odds he used, didn't he? WillNess (talk) 13:35, 27 July 2011 (UTC)

So far you haven't discussed anything yet; you've only objected to one word, "consecutive". As it is written, erasing that word will make the description less understandable, IMO. The counting up in increments is the defining feature of the asic/original sieve of E, and it can only be readily understood on consecutive sequences of integers (#Simplicity!). Even using odds is a stretch (#Simplicity!). It's enough to mention it as an improvement. In fact, it already is so mentioned.

And we only know that Nicomachus used odds. WillNess (talk) 13:50, 27 July 2011 (UTC)

Lastly, I do not consider removing big chunks of article wholesale a "bold edit". Re-write, I would. But eliminating a valid discussion just to remove few lines of code that it was using as a prop, is something else entirely. WillNess (talk) 06:54, 28 July 2011 (UTC)

You're confusing me for someone else. Gandalf61 did the removal. CRGreathouse (t | c) 15:04, 28 July 2011 (UTC)

Leave me out of it. I am pretty sure WillNess was not talking about any of my edits on this article, but if he was then I am sure he will clarify his meaning. Gandalf61 (talk) 15:18, 28 July 2011 (UTC)

Not trying to drag you into it, but WillNess did title the section after you. CRGreathouse (t | c) 17:15, 28 July 2011 (UTC)

This thread hsn't been about my edits from its second post onwards. To avoid further confusion I have amended its title. Gandalf61 (talk) 18:39, 28 July 2011 (UTC)

It seemed to me that he criticized the fact that I responded only to the last point ("consecutive") and attempted to bring up the original issues, a response to your edits. (I don't imagine either of us want to be involved in that discussion.) CRGreathouse (t | c) 00:19, 29 July 2011 (UTC)

to Gandalf61: you are absolutely right. We had a fruitful discussion and cooperative editing, you and I (at least I had; I hope it was so for you too). Your contribution is much appreciated, you helped to change the wording there to sound much better. Then the objection was raised to the use of the word "consecutive" to which I had to provide counter arguments, and the ensuing discussion was needlessly long-winded, because that word is necessary in that context. IMO.

Of course the removal in question was done by the other editor in this thread, under "NOTREPOSITORY" heading on July 18th. Which in itself woudn't be a problem if they hadn't refused to engage in a fruitful and cooperative discussion afterwards, but hey, it doesn't matter, there's always an option of just giving up.

Their attempt to mislead is really... what's the word? Not conducive to the spirit of cooperation and mutual trust here. WillNess (talk) 15:34, 31 July 2011 (UTC)

Attempt to mislead? I'm trying hard to understand you and you're not being very clear. Don't criticize me for your decision to be unclear. CRGreathouse (t | c) 16:17, 31 July 2011 (UTC)

Trial division section

I'm not sure that this article needs a section on trial division. But if we're going to have one, I think we need to be more precise than "It has worse theoretical complexity than that of the sieve of Eratosthenes". Trial division has strictly worse complexity than the SoE if it's adapted, as O'Neil does, for finding primes in the interval 1..n. But if used to test an individual number it has the same worst-case complexity and better average-case complexity than the SoE. (Amortized analysis seems inappropriate here.)

Also, I'm not sure what to think of the impredicative set-builder definition given in the section. As written I believe it uniquely defines the empty set, but even if corrected I don't think it belongs in this article. This isn't an article about defining the primes (or formulas for primes) but rather to discuss a particular algorithm for their generation. (Well, an algorithm that can be used for that purpose, anyway.)

CRGreathouse (t | c) 04:14, 12 August 2011 (UTC)

It's here not to describe a trial division in full which has its own WP page. It is only to compare with it, to warn about it, because it is rather frequently confused with SoE, and to mention/warn about Turner's sieve which you yourself were in favor of doing, right? I was trying to be concise. SoE itself – in its basic configuration, which is the only one dealt with in the article at that point – is about producing total ranges of primes, not testing individual numbers, so I'd expect no confusion there. To do what SoE does, TD has worse complexity. But a clarification would help, sure.

No, ONeill did not "adapt it ... for finding primes in interval 1...n". Quite the contrary, she deals with non-bounded formulations exclusively, which is the root problem with that article IMO.

As for math "formulae" they are intended to give some visual cue to the reader about the algorithms. Removing multiples from naturals above 1 is what the Sieve does, is it not? If there's an error, please correct it. Could you please explain it more here, on this talk page? Why removing primes' multiples from natural numbers above 1 defines an empty set? Please clarify. WillNess (talk) 06:16, 12 August 2011 (UTC)

Here it is for ease of reference: $\mathbb {P} =\{n:n\in \mathbb {N} ,n>1\}\setminus multiples(\mathbb {P} )$. Do you mean it because "multiples" is not defined? It is only intended as a visual cue to complement the algorithm described above it in the article. WillNess (talk) 06:41, 12 August 2011 (UTC)

Would this be better, $\mathbb {P} =\{n:n\in \mathbb {N} ,n>1\}\setminus \cup _{p\in \mathbb {P} }\{p(p+n):n\in \mathbb {N} \}$ ? WillNess (talk) 07:15, 12 August 2011 (UTC)

Or this one: $\mathbb {P} =\{n:n\in \mathbb {N} ,n>1\}\setminus \cup _{p\in \mathbb {P} }\{np:n\in \mathbb {N} ,n>1\}$ (coincidentally I see what you mean now, as 1p would probably be considered a p's multiple).

So, can this be put back into the article? It would provide a visual counterpart for the one of TD. To have some visual cue is much easier for a new reader to "get the picture". Human intelligence is much visual-oriented. WillNess (talk) 07:39, 12 August 2011 (UTC)

O'Neil's claim about the complexity of trial division is for the case 1..n (or any o(n)..n I suppose). If it was for a single number it would be ${\tilde {O}}({\sqrt {n}})$ rather than ${\tilde {O}}(n{\sqrt {n}})$. That it can be applied continuously is not relevant to the complexity.

I would not call any of those formulas "intuitive" or "visual". On the contrary, almost no readers would understand the formula unless they already understood trial division. It adds nothing to the article.

But if you want to include it let's make it the best we can. Don't make up new function names on the spot (and if you had to, certainly format them upright like sin and not in italics as though they were variables $multiples=eil^{2}mpstu$). Don't define a symbol using that symbol in your definition if you can avoid it: since you're a programmer, maybe it will make more sense if I say the thing being defined should appear only as an lvalue. Calling your original formula (1), my correction of it (2), your formulas above (3), (4), and (5), and the formula you just added to the Incremental sieve section (6):

(1), (2), (3), (4), (5) and (6) are impredicative.

I haven't checked if the impredicativity can be used to make (3), (4), (5), or (6) ambiguous; I don't include this issue below when I check correctness. (1) and (2) are unambiguous.

(1) and (3) use word-functions (in both cases undefined and poorly typeset).

(1) and (2) are wrong.

(3) and (4) may be wrong, depending on exactly what you meaning you give to the symbols used. Assuming an appropriate separation of the lvalue and rvalue $\mathbb {P}$s, I can find a reasonable interpretation for either that makes the result correct or incorrect.

So in short the formulas are ugly, useless, and wrong. I can fix them so they're only useless, but I think that there's not much to be gained there, and that further this article is not the right place for either of your formulas.

CRGreathouse (t | c) 13:52, 12 August 2011 (UTC)

I'm searching for some visual aids beyond plain words. The text as it is right now is insufficiently descriptive IMO, the reader won't understand it without having to read the articles mentioned. Too much words would be needed to clarify it, and it would give too much details.

We can't have Haskell code; C-like pseudocode is too verbose and this is not the place to have TD pseudocode at all; yet I think it's illuminating to have the two (preferably three, with Euler sieve as well) compared here, in some succinct, visual way – like it was, IMO, with the old removed Haskell three-liner. I understand you protest the impredicativity of "my" formulas; yet it is exactly how the two algorithms operate. There is no vicious circle there, because they do not define sets but ordered sequences. I'm not seeking to give mathematical definition of what a prime is but rather a succinct description of what an algorithm does, even if somewhat abstracting over the specific details.

How about these two: (a later edit was made to tweak typography)

$\textstyle \mathbb {P} =\{n\in \mathbb {N} :n>1\}\setminus \bigcup _{p\in \mathbb {P} }\{np:n\in \mathbb {N} ,n\geq p\}$

$\textstyle \mathbb {P} =\{n\in \mathbb {N} :n>1,(\not \exists p\in \mathbb {P} )(p<n\land p\mid n)\}$

? The self-reference is by intent. Can this be treated as "pseudo-mathematical notation" or something? WillNess (talk) 17:06, 12 August 2011 (UTC)

I'm sure BTW that the text (in both Incremental sieve and Trial division) seems sufficiently explanatory to you, but don't forget that you know the subject matter very well, things that seem obvious to you might not be such for others. It usually helps to have more clues as to whats going on, to have the matter presented in more than one way when you try learning something new. WillNess (talk) 17:19, 12 August 2011 (UTC)

I agree that this is not the place for trial division pseudocode (or code, for that matter). I don't really think this article is the place for comparisons with other methods, but that makes me wonder: maybe we should write an article comparing methods for prime generation? There's plenty enough for an article, don't you think? Eratosthenes, the methods of Chartres and Singleton (precursors to your favored methods), Mairson's multiplicative sieve (and improvement by Dutton et. al.; I think Bengalloun's incremental sieve was of this type), Pritchard's sublinear sieve, Sorenson's pseudosquare sieve, Atkin-Bernstein, Galway's dissected sieve, etc.

What do you think?

CRGreathouse (t | c) 18:13, 12 August 2011 (UTC)

Back to the formulas: I don't think that they do a good job of describing the algorithms. I'm much more familiar with set-builder notation than just about anyone who might read this article but not know the Sieve of Eratosthenes and I can't even immediately prove that either of the above sets unambiguously define the primes.

$\textstyle \{n\in \mathbb {N} :n>1\}\setminus \bigcup _{p\in \mathbb {P} }\{np:n\in \mathbb {N} ,n\geq p\}$

is a set equal to the primes, but that does not mean that there is a unique set X such that

$\textstyle X=\{n\in \mathbb {N} :n>1\}\setminus \bigcup _{p\in X}\{np:n\in \mathbb {N} ,n\geq p\}$

so it's not clear that this is adequate to define the primes. By analogy,

$\{n:n\in \mathbb {P} \}$

is the primes but

$X=\{n:n\in X\}$

does not define the primes.

I certainly don't want whatever "pseudo-mathematical notation" is in this article, and I'm sure I'd get widespread agreement from other math editors on this point.

CRGreathouse (t | c) 18:25, 12 August 2011 (UTC)

I think, that grand expose' you have in mind would necessarily be in a separate article, but this one would certainly benefit from comparison of SoE specifically with TD, because of (wide-spread) confusion of the two. Have you heard a saying "the best is an enemy of the good-enough"?

Actually for both equations if we start to unravel them we end up with primes, whether we call them P or X, I don't see any other possibility. N₂ = {2} ∪ N₃ , right? We can proove things about the set X from that definition, starting with X ⊂ N₂. It's the set N we're talking about. Your analogy is not really a valid analogy at all. So it's not impredicative after all, even if formally self-referencing. There is no vicious cirlce because N is countable, and ordered, and because of the properties of arithmetic operations.

But if no Haskell, and no "math-notation" pseudocode, then what? For me, the two formulae succinctly reflect the two algorithms and let me see, at a glance, the similarities and the differences between the two. A great visual aid, to see the two equations one under the other. Why not show it?

Of course it is easy to correct the self-reference, but that's not what the two algorithms are doing (both are specifically self-referencing):

$\textstyle \mathbb {P} =\mathbb {N} _{2}\setminus \bigcup _{p\in \mathbb {N} _{2}}\{np:n\in \mathbb {N} _{p}\}$   where   $\mathbb {N} _{k}=\{n\in \mathbb {N} :n\geq k\}$   (a later edit was made to add 2nd definition)

$\textstyle \mathbb {P} =\{n\in \mathbb {N} _{2}:(\not \exists p\in \mathbb {N} _{2})(p<n\land p\mid n)\}$

Are you saying formally self-referencing definitions aren't allowed at all, ever, even if well-defined? WillNess (talk) 04:28, 13 August 2011 (UTC)

Just for ease of reference, this is what I'd like included in the article:

$\textstyle \mathbb {P} =\mathbb {N} _{2}\setminus \bigcup _{p\in \mathbb {P} }\{np:n\in \mathbb {N} _{p}\}$

$\textstyle \mathbb {P} =\{n\in \mathbb {N} _{2}:(\not \exists p\in \mathbb {P} )(p\leq {\sqrt {n}}\land p\mid n)\}$

WillNess (talk) 04:47, 13 August 2011 (UTC)

Can you prove that your formulas are well-defined? As far as I'm concerned they're less good at explaining their concepts than alternate methods, they discourage readers without experience reading symbolic expressions ("I can't read this article, it has all kinds of funny symbols"), they're not obviously correct (and may be incorrect, as several of your previous versions were), and they're WP:OR.

"For the record" I think it's worth noting that the four formulas above are different from the two that I just removed from the article.

As far as well-definedness is concerned: a predicative formula in set-builder notation is automatically defined (in naive set theory; there are other conditions in ZF but they're not relevant here). By contrast, an impredicative set-builder 'definition' is rather a unary relation on sets which may apply to zero, one, or more sets. To prove that it's well-defined, one must show that it holds for exactly one set. To prove that it's correct one must show that it's well-defined and that the unique set for which it holds is the desired set, in this case the set of prime numbers.

CRGreathouse (t | c) 15:48, 17 August 2011 (UTC)

Right, they are exactly the last two formulas of the four above, where I only changed one letter, P, into S for SoE, and T for trial division sieve, to prevent any confusion with the predefined set of primes P, and omitted the sqrt.

As for discouragement, I disagree. They aren't featured at the prominent place in the article, at all, and are below a section explaining the algorithm in plain words. A detailed example follows immediately beneath them. It's easy to skip over for anyone uncomfortable with the notation, and adds a visual aid (IMO) to those who aren't.

As to the mythical "alternate methods", let's have them. Let's see them, clear and succinct, easy to grasp at one glance. So far you have been replacing the formulas with nothing at all. That's not replacement, that's deletion.

As to WP:OR, it's not. It is a direct translation of Bird's Haskell code in M. ONeill's article (p.10, "104"):

                primes = 2:([3..] `minus` composites)
                composites = union [multiples p | p <- primes]

This is self-evident for anyone who is Haskell-literate. As for ONeill's code, she says it's equivalent to Bird's (or vice versa). Same with the TD definition, equivalent to her code there (p.3, "97"):

                primes = 2 : [x | x <− [3..], isprime x]
                isprime x = all (\p −> x ‘mod‘ p > 0) (factorsToTry x)
                  where
                    factorsToTry x = takeWhile (\p −> p*p <= x) primes

Here she shows an optimal TD definition; that's why I omit the "sqrt" in the general one.

The rigorous proof is also simple, it relies on traits of the set N and that N \ M ⊂ N, without having to know anything about the set M. Because N is ordered, N₂'s minimal element is 2, by definition. The minimal element of M in the definition S = N₂ \ M is the square of the minimal element of S by its definition, i.e. it is at least 4. Thus both 2 and 3 are in the resulting set. Etc., etc. The validity of that formula is equivalent to the validity of the algorithm itself. But the proof would only be needed if the formulae were introduced as separate entities - and then it would be WP:OR. But they aren't - they are just translations of the published code. This is also clear from the way in which they were presented, in a sentence describing the algorithm. WillNess (talk) 17:46, 17 August 2011 (UTC)

I don't accept those translations. First, it's not clear that the resulting formulas are correct, as I have explained above. Enough of your formulas have been flawed that I'm hesitant to accept your claims that these are correct (you said the same about the others). Second, it's not at all clear that this conversion falls within WP:OR's guideline of "simple calculation" (though personally I favor a lenient interpretation of this clause as applied to math articles). Third, I don't think that set-builder notation represents an algorithm at all: assuming the translation are correct $\mathbb {S} =\mathbb {T}$ while the algorithms are not the same. (I'm reminded of Gowers' article [4] which addresses proofs rather than algorithms.) Fourth, even if I accepted a particular symbolic representation of a set as a description of an algorithm (the set obviously being unable to distinguish between different algorithms generating it) it's not clear that these would yield the algorithms they purport to represent; there are important points not apparent from the formulas. (For example, see [5] which addresses the issue of whether the array will ever be read beyond its bounds.) Fifth, the notation is idiosyncratic which adds to the problem of readability (and frankly I don't find these all that readable for the target audience in the first place). Sixth, the two formulas denote the same idea ("consider only numbers at least 2") differently: $\mathbb {N} _{2}\setminus S$ vs. $\{n\in \mathbb {N} _{2}:n\in S\}$, essentially. By making things that are the same look different you obscure the actual differences.

I could add to this list but I think that's enough for now.

CRGreathouse (t | c) 20:49, 17 August 2011 (UTC)

For the umpteenth time, the formulas are true symbolic representations of the two very different algorithms and are not intended as set definitions, and if you think testing for divisibility is the same as generating the multiples to be skipped over you don't understand what SoE is all about. The two formulae make the actual difference between the two processes apparent and clear. That some of my previous formulas had minor, easily fixable discrepancies (basically, only one, not including the p<n test in TD) is besides the point and all that your criticism amounted to was just denying the possibility of self-reference, which is not at all set in stone. So basically, you've said nothing new, you've just made it look different.

And your two formulas are wrong. You use same letter S for two very different things. One is "composites", the other is "primes". Even if you were to fix your second formula $\{n\in \mathbb {N} _{2}:n\not \in S\}$, it would still be a wrong transcription of TD definition. "Not in composites" and "there's no divisor" define same thing by two very different processes, and "my" formulae make this abundantly clear. WillNess (talk) 06:48, 18 August 2011 (UTC)

Specifically, (1) the two formulae are clear-cut transcriptions of published Haskell code, word-for-word (union, multiples, divides, etc.); (2) the transcription is self-evident; (3) is debunked by your own (4); (4) what "important points"? "array", what array? there's no array in the published code which the two formulae are transcribing; (5) "idiosyncratic" is your POV, must be specific; (6) I debunked above. So basically what you're saying, is you just "don't accept" them. I couldn't discern any specific reason "why" from your last post other than "I just don't". WillNess (talk) 08:55, 18 August 2011 (UTC)

Here's the two new verbatim translations of the Haskell code as published in ONeill article:

$\textstyle \mathbb {S} \,=\{2\}\bigcup \,(\mathbb {N} _{3}\setminus \bigcup _{p\in \mathbb {S} }\{np:n\in \mathbb {N} _{p}\})$   where   $\mathbb {N} _{m}=\{n\in \mathbb {N} :n\geq m\}$  

$\textstyle \mathbb {T} =\{2\}\bigcup \,\{n\in \mathbb {N} _{3}:(\not \exists p\in \mathbb {T} )(p<n\land p\mid n)\}$

(a later edit: ok, it's probably wrong to omit the sqrt in the second formula above;

 and it's actually $\textstyle \mathbb {T} =\{2\}\bigcup \,\{n\in \mathbb {N} _{3}:(\forall p\in \mathbb {T} )(p^{2}\leq n\Rightarrow p\nmid n)\}$ in the article)

being a verbatim translations of published code (except for the omitted "sqrt"), surely there can be no objections to them other than questions of taste. Opinions of anyone who reads this would be much appreciated. WillNess (talk) 09:14, 18 August 2011 (UTC)

OK I've read now the link you provided (thanks for the links btw) and I see you were talking about the (array of) primes generated so far; but that is a well known non-problem which was delt with in the past by many sources (SICP etc.). Again, the formulae are faithful translations of published code (as seen here in the thread above). WillNess (talk) 09:59, 18 August 2011 (UTC)

("debunked" probably a wrong word; replace with "provided counterarguments to"). WillNess (talk) 13:59, 18 August 2011 (UTC)

Yes, I used S as a variable; it's not intended to represent the same thing in the two cases. (Why would it? I'm trying to show the similarities between two formulas; the differences will of course be in the part not shown.)

None of my six criticisms immediately above related to impredicativity. I considered adding that as #8 (with something else as #7) but I thought it would be too hard to explain the importance of predicativity to someone not studying FOM.

You dismiss my points without addressing them, with a few exceptions. For #4, I use the term "array" as that is what was used in the link; I thought you would have no trouble understanding the connection with the Haskell code. To be more specific: if the "deep result of number theory" did not hold, the Haskell code would loop endlessly at some point without producing output: to produce the next prime it would first need to produce the next prime. It does hold, but the impredicativity of your notation conceals this important fact. #3 is a serious objection that seems to proscribe any (mis)use of set-builder notation to represent algorithms on this page; my fourth point in no way countermands it. (Why would you even think so?) For #5, following guidelines like MOS:MATH means that all editors must decide what standard notation is; that yours is not is by no means (what Wikipedia calls) POV. Further, while I'm on that page, I should mention its admonition to "be conservative in using symbols".

I quite disagree with you on #6, and you seem to have not quite understood my meaning (based on your comment on S). But I'm not going to defend this one; while 1-5 give reasons that the formulas should not be used in the article, #6 only seeks to show that your formulas as written do a poor job. If anything, having poor-quality formulas makes my position stronger.

CRGreathouse (t | c) 18:58, 18 August 2011 (UTC)

On the other hand, your most recent edit improves the clarity of the paragraph; I was trying to find a reasonable way of explaining that and I think you pretty much nailed that. Any chance of fixing the parenthetical "(to be skipped)"? It's a little awkward but I can't quite figure out the best way of rewriting the clause it's in. CRGreathouse (t | c) 19:01, 18 August 2011 (UTC)

So would you mind showing me what you mean by formulas "doing a good job"? If not for inclusion in the article then just for the sake of the argument? How can you say that the two formulas are "same" when one refers to eliminating the composites, and another clearly shows testing of each candidate? The end result is same, but the two processes clearly are very different. The first generates the multiples, the second tests each candidate one-by-one... exactly the difference between the two algos. How can you deny that? Yes, the set-builder notation is used there to describe the intention of the set if you will, not its extension (which of course is the same or else it'd be just wrong). If it was the extention I was after, I'd just use $\mathbb {P}$, wouldn't I?

As for overconsuming the own output, it is well known not to be a problem with sqrt n, and even with n/2. There is nothing to conceal so "my" notation does no concealment of anything. It was wrong to omit the "sqrt" entirely in that formulation, but it is easy to put it back (I was thinking of Turner sieve there which actually accomplishes the fit of testing each prime by all its preceding primes). Of course operational details are overlooked in that notation, it's used for an abstract formulation. The "timing issues" in e.g. generating multiples etc. are implicitly assumed taken care of "somehow". It is an operational detail; the core of the algo is, it skips over the multiples it generates. That's what's important - that's what's shown. WillNess (talk) 00:43, 19 August 2011 (UTC)