Ripple Sieve

Ripple Sieve
Class	Prime sieve
Data structure	{{{data}}}
Worst-case performance	{{{time}}}
Worst-case space complexity	{{{space}}}

Overview

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.

Mathematical Recognition

The mathematical properties of the Ripple Sieve were formally recognised in 2017 with the acceptance of sequence (sequence A281813 in the OEIS) as ripple sequence (ripple numbers) 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.

Algorithm Description

For any given positive integer n, this Ripple Sieve algorithm produces all the odd primes below n. The Ripple Sieve utilises a "seed" value to initialise a "ripple" that grows linearly, creating a second-order arithmetic progression. The seed value starts at 1 and is incremented by 2 to produce odd number seeds up till the seed value reaches the limit (n - 6) / 3.

Iterative Logic

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

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

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.

Comparison with Sieve of Sundaram

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.

Implementation

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]]

References

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

This article "Ripple Sieve" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Ripple Sieve. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

Ripple Sieve

Contents