1
$\begingroup$

Apologies for this edit (8.13). I encourage those interested in the math side of this variant to view the MathOverflow post mentioned below, and contact me at that forum. This version is an attempt to find a CS reference.

I am researching mathematical properties of a variant of the sieve of Eratosthenes. Has anyone seen this particular variant before in the computer science literature? If so, can I have a reference please?

The mathematical version of this question for those interested has been asked at https://mathoverflow.net/q/243490 with some further followup questions. Some time has passed without an answer containing a reference, so I post here.

Below is the algorithm for the variant implemented in an AWK fragment:

for (n=1;  (n++) < Search_Limit;  S[m]=p ) {
       if ( (m=n) in S) { for (p=S[m]; (m+=p) in S ; ) { } }
       else m+=(p=n) }. #### n is prime

This uses an associative array S, with keys which turn out to be composite numbers and values which turn out to be a prime dividing the numerical value represented by the key. When you run it, S[15] gets the value 3 and S[35] gets the value 5, for example.

I have looked at O'Neill's 2009 paper about a Haskell variant, a blog post from January 2011 of van Emden which refers to a 1972 paper of Dijkstra which has a version that anticipates this variant but does not implement it, and a 2015 paper of Sorenson which mentions a hopping sieve of Bennion from the 1970's, which is close to this variant but not quite. (Bennion's version has p "push" a value q out of S[m], so S[m] gets p and the prime q ends up in S[m+q]; this version has p jump over filled slots in S and finds an empty slot to land in.). None of these quite fit this variant.

Even finding this somewhere on the web (by someone other than me) would be useful. Do you know where?

To respond to a comment (as I can't comment on my own post yet): I am willing to provide a different implementation or explanation if needed. The code above is similar to C syntax, with the exception of "in". 'expr in S' returns true if there is a key with value of expr and that key is in the array. Once the assignment statement S[m]=p is executed, (m in S) returns true. The MathOverflow post linked above contains a pseudocode version of the variant.

Here is another implementation which depends on the operation "k in A" returning true if the associative array has an entry with key k, and returns false otherwise. As above, if A[35]=5 occurs, then k=35 occurs, then (as no delete operation is used) (k in A) is an expression that will evaluate to true. A feature of this variant is that no key is used in an assignment more than once, and is used for reference less than log(Search limit) times when Search limit is not small.

For n = 2 to Search limit  step 1
      m = n
      p = n
      If (n in S) 
            p = S[n]
            while (m in S) m = m + p
      else m = m + p
      S[m] = p

I hope readers understand the "for ... step ..." construct.

Also here are some references:

O'Neill, Melissa E., "The Genuine Sieve of Eratosthenes", Journal of Functional Programming, Published online by Cambridge University Press 09 Oct 2008 doi:10.1017/S0956796808007004 https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

A blog post by Van Emden entitled "Another Scoop By Dijkstra?" at

https://vanemden.wordpress.com/2011/01/15/another-scoop-by-dijkstra/

An ArXiv posting by Jonathan Sorenson on two compact incremental sieves, which mentions Bennion's sieve:

https://arxiv.org/abs/1503.02592

I hope these links help others in considering this question.

$\endgroup$
  • 1
    $\begingroup$ Perhaps you could rephrase your algorithm in pseudocode, for the benefit of those of us not familiar with AWK? $\endgroup$ – Yuval Filmus Aug 12 '17 at 8:16
  • $\begingroup$ That would indeed be helpful. For instance, I'm not sure what (m = n) in S does, or m+=(p=n). Are you being clever with side effects? I suspect it would be better to express this in pedagogical pseudocode in a way designed for understanding. Also, can you give a full reference to each of the references you cite? For papers, I suggest the authors, title, where published, and a link to a freely available PDF if possible. For a blog post, it would help to provide a link to the blog post. You should be able to comment on your post if you've registered your account. $\endgroup$ – D.W. Aug 12 '17 at 17:34
  • $\begingroup$ I have been trying to understand the sieve you mentioned primarily because I had already tried to make a more efficient sieve of primes some 8 months ago.Though I could not understand your implementation(because I don't know AWK) I was able to get an Idea from the blog post by Van Emden.I have discovered that it is something similar to what I had been doing then.I was not able to get the complexity of my sieve any better than the complexity of sieve of atkins because of heap management operations.What kind of mathematical properties you are looking for? $\endgroup$ – Romantic Electron Aug 13 '17 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.