Draft:Ripple Sieve: Difference between revisions

Efficient prime sieve algorithm focusing on odd integers using quadratic increments

This may take 2–3 weeks or more, since drafts are reviewed in no specific order. There are 1,489 pending submissions waiting for review. If the submission is accepted, then this page will be moved into the article space. If the submission is declined, then the reason will be posted here. In the meantime, you can continue to improve this submission by editing normally. Where to get help If you need help editing or submitting your draft, please ask us a question at the AfC Help Desk or get live help from experienced editors. These venues are only for help with editing and the submission process, not to get reviews. If you need feedback on your draft, or if the review is taking a lot of time, you can try asking for help on the talk page of a relevant WikiProject. Some WikiProjects are more active than others so a speedy reply is not guaranteed. Improving your odds of a speedy review To improve your odds of a faster review, tag your draft with relevant WikiProject tags using the button below. This will let reviewers know a new draft has been submitted in their area of interest. For instance, if you wrote about a female astronomer, you would want to add the Biography, Astronomy, and Women scientists tags.

This is a draft article. It is a work in progress open to editing by anyone. Please ensure core content policies are met before publishing it as a live Wikipedia article. This draft has been submitted and is currently awaiting review.

The Ripple Sieve is a prime sieve algorithm that generates all odd prime numbers up to a given limit n. Developed by Rayan Ivaturi, the algorithm is a variant of the Sieve of Eratosthenes that optimises the sieving process by focusing exclusively on odd integers and utilising a dynamic quadratic increment, referred to as a “ripple,” to identify composite numbers.

The mathematical properties of the Ripple Sieve were formally recognised in 2017 with the acceptance of sequence (sequence A281813 in the OEIS) in the Online Encyclopedia of Integer Sequences (OEIS). The sequence defines the number of “ripple” operations required for the first n odd numbers, providing a basis for analysing the algorithm’s efficiency and computational density.

The Ripple Sieve utilises a “seed” value to initialise a “ripple” that grows linearly, creating a second-order arithmetic progression.
The seed values start at 1 incremented by 2 to produce odd number seeds up till the seed value reaches (n – 6) / 3.

For seed s, starting from 1 incremented by 2, the algorithm initialises:

• A starting index: sum = seed + base ripple
• An initial base ripple: ripple = 2 * seed + 6

In each step of the inner loop, the ripple is incremented by 8, and the next composite is found by adding this new ripple to the current sum. This ensures that the algorithm only marks odd composite numbers, effectively skipping even integers.

While both the Sieve of Sundaram and the Ripple Sieve aim to exclude even numbers, their implementations are mathematically distinct:

• Sieve of Sundaram: Relies on the algebraic identity $i + j + 2ij$ to mark indices in a reduced array.
• Ripple Sieve: Operates on the values themselves using a second-order difference of 8 to skip even multiples.

The following is the original implementation in Python:

def ripple_sieve(n):
    primes = [False] * n
    seed_limit = (n - 6) // 3    
    
    for seed in range(1, seed_limit, 2):        
        ripple = 2 * seed + 6
        sum_val = seed + ripple        
        
        while sum_val < n:
            primes[sum_val] = True
            ripple += 8
            sum_val += ripple

    return [i for i in range(3, n, 2) if not primes[i]]

• Ivaturi, Rayan. Sequence A281813, The Online Encyclopedia of Integer Sequences (2017).