Talk:Sieve of Sundaram

Comments

This article has a number of problems. I have left the following note on the original author's talk page:

I see that you recently created a new article, Sieve of Sundaram. I think the article needs a bit more work. Problems with the current version are:

1. The Sundaram that you link to is a volleyball player. Is he really the inventor of the algorithm ?
2. The date "in 40th of XX century" needs to be completed and clarified.
3. The description of the algorithm is not clear. What does "Derived sequence consist of primary numbers p" mean ?
4. The article needs to include references to show that (i) the algorithm is not original research and (ii) the algorithm is notable.

Unless you (or someone else) can fix these problems in the article, it will fall short of Wikipedia's standards, and may be deleted. Gandalf61 11:14, 3 December 2007 (UTC)

Thanks for response Basicall article just translated from rusiian Wikipedia.

1. Changed. I don't really know who Sundaram is, half an houre googling don't help me to figure out it.
2. Date is all I got for now, I have not any paper sources so it's all I got.
3. will try to clarify, with this rough description I've made up a programm.
4. Algorithm just one of this type, it faster than Eratosphenes & easier than Atkins sieves, notably enough IMO. I'll try to figuire out sources/referencies and add them.

I'll appreciate any suggestions about improoving it more Any_Key 19:35, 3 December 2007 (UTC)

Speed

I don't think that this is any faster than the Sieve of Eratosthenes, though, I think just about anything is easier to understand than Atkin's. I did some simple tests in C and Haskell, my C version of this ran about 75% as fast as the unoptimized SOE. The haskell version ran half as fast, though I think my implementation of the latter is probably lacking.

A informal analysis tells me that this algorithm runs in linear time, since you have to generate a list of Z values, then generate a list of values that are no Z values, then map over that list the 2x + 1 function. I think that SOE runs in O(n), Atkin in O(n/log log n). So, it is my impression that this is no better than the SOE, except for possibly conciseness. Even in that regard, SOE is smaller than Sundaram in Haskell (at least in my implemenation) by about 25 characters (not including whitespace). Jfredett (talk) 09:12, 17 December 2007 (UTC)

There are about n/4 rows to check, each of which has n/6 down to 1 column to check. A tedious calculation shows that the number of elements (and thus the time complexity) is

$^{1}/_{4}\ n\ln n+\Theta (n)$

so in fact for large bounds it becomes slower than the (optimized version of the) SoE. It's even possible, thanks to the Chen-Qi bounds on harmonic numbers, to give an explicit lower bound.

For the primes up to 1000, only 1269 numbers are checked; for the primes up to a million about 3 million are checked (2992491); for the primes up to a billion, almost 5 billion need to be checked (4719424383). This compares reasonably with the asymptotic formula, within about 10%.

CRGreathouse (t | c) 20:23, 31 October 2008 (UTC)

This algorithm is asymptotically slower even compared to a classical SOE. Unoptimized version of SOE runs at O(n log log n) whereas this algorithm is O(n log n). The latter can be computed from the following sum (and can be easily formalized):

sum_{j = 1}^{n/3} \frac{n - j}{1 + 2j} — Preceding unsigned comment added by 31.175.84.145 (talk) 23:06, 3 October 2011 (UTC)

These two sieves are not equivalent and that should be fixed. What they have in common is that they both sieve primes. — Preceding unsigned comment added by 31.175.84.145 (talk) 23:08, 3 October 2011 (UTC)

Odd vs. Even Primes

I think the statement that 2 is "the only even prime" (== "the only prime divisible by 2") is a bit of a joke. After all, that's equivalent to stating "17 is the only prime divisible by 17." —Preceding unsigned comment added by 77.176.69.185 (talk) 07:58, 1 March 2009 (UTC)

recent online article

FYI this just came out: Sundaram's Sieve--Billymac00 (talk) 02:43, 16 March 2009 (UTC)

Equivalent to Eratosthenes?

The sieve of Eratosthenes crosses out multiples of remaining primes. Such as stated here multiples of all odd numbers are crossed out. So either the description is incorrect, or the statement of equivalence is. [This has some bearing on the complexity issue too.] A straightforward optimisation of the SoE is to have the sieve only contain odd numbers. That would be an "easy exercise for the reader", not notable or worth a patent. It would be notable if found in the 8th century by a Chinese scolar. 1934 and India, I doubt, but apparently it is present in the literature and must be included in Wikipedia on that account.

Albert van der Horst 80.100.243.19 (talk) 02:06, 4 November 2010 (UTC)

I don't think it's equivalent to the sieve of eratosthenes (even when the optimization of using only odds is used). Here is what Sieve of Sundaram looks like (where we loop at a = 2i + 1 and b = 2j + 1 instead of i and j):

n ← 1000000 // limit

// initialize the sieve
is_prime(2) ← true
is_prime(i) ← [i is odd], ∀ i ∈ [3, n]

for all odd a such that 3 ≤ a and a² ≤ n:
    for all odd b such that a ≤ b and ab ≤ n:
        is_prime(ab) ← false

while Sieve of Eratosthenes (using only odd integers) roughly looks like this (only one line is added):

n ← 1000000 // limit

// initialize the sieve
is_prime(2) ← true
is_prime(i) ← [i is odd], ∀ i ∈ [3, n]

for all odd a such that 3 ≤ a and a² ≤ n:
    if not is_prime(a): continue      // only this has changed
    for all odd b such that a ≤ b and ab ≤ n:
        is_prime(ab) ← false

This also shows that the Sieve of Sundaram is less efficient than the Sieve of Eratosthenes, and that its complexity is Θ(n log n) (since 1/2 + 1/3 + 1/4 + ... + 1/n grows asymptotically as log n) compared to sieve of eratosthenes' Θ(n log log n) (since 1/2 + 1/3 + 1/5 + 1/7 + ... + 1/p grows asymptotically as log log n). — Preceding unsigned comment added by 27.108.41.75 (talk) 19:36, 13 June 2012 (UTC)

Pseudocode of the algorithm

I've written some pseudocode for the algorithm, based on Sieve of Atkin#Pseudocode, and submit it to the public domain here:

// arbitrary search limit
limit ← (999999-1)÷2

// initialize the sieve
is_2np1_prime(n) ← true, ∀ n ∈ [1, limit]

// eliminate numbers of the form (i+j+2ij)
for i in [1, limit]
    for j in [1, i]    // should this be; [i, limit]?
        n ← i+j+2ij
        if (n ≤ limit):
            is_2np1_prime(n) ← false // 2n+1 is composite

// output the list of primes up to (limit×2+1)
print 2
for n in [1, limit]:
    if is_2np1_prime(n): print 2n+1

Personally I think it is easier to follow in this form than the textual description.

I'd like to recommend it be included in the article, subject to any corrections/clarifications anyone wants to make. (Feel free to make changes inline.) - CountingPine (talk) 02:16, 28 August 2012 (UTC)

Suggested improvements

1. It would be better if this article followed the presentation in Honsberger's book more closely. The idea is explained more clearly there, almost without formulas.

2. There seems to be a lot of original research in the later parts of this article, with all the homemade computer code and so on.

3. Sundaram's algorithm effectively sieves using all odd numbers, not just the primes, so it is definitely slower asymptotically than the odds-only variant of the sieve of Eratosthenes (which dates back to the original, as explained at its Wikipedia page).

Ebony Jackson (talk) 06:14, 6 August 2021 (UTC)