Clean Prime Chains

clean-prime-chains.py

import math


def eratosthenes(n):
    """
    Sieve of Eratosthenes

    >>> eratosthenes(19)
    [1, 2, 3, 5, 7, 11, 13, 17, 19]

    >>> eratosthenes(5)
    [1, 2, 3, 5]

    >>> eratosthenes(0)
    []
    """
    # Add one to account for zero index
    numbers = [True] * (n+1)

    for i in xrange(2, int(math.ceil(n**0.5))):
        if numbers[i]:
            for j in xrange(i**2, n, i):
                numbers[j] = False

    # Start from one to ignore zero
    return [i for (i, n) in enumerate(numbers) if n][1:]


def clean_prime_chains(primes):
    """
    >>> clean_prime_chains(eratosthenes(pow(2, 16)))
    clean prime chain of length 1 ending with 2
    [2]
    clean prime chain of length 3 ending with 5
    [2, 3, 5]
    clean prime chain of length 20 ending with 71
    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]
    """

    chain = []
    chain_sum = 0
    chain_length = 0

    for prime in primes:

        if prime == 1:  # Sum starts from 2
            continue

        clean_chain = (chain_sum % prime == 0)

        chain.append(prime)
        chain_sum += prime
        chain_length += 1

        if clean_chain:
            print 'clean prime chain of length {0} ending with {1}'.format(
                chain_length, prime)
            print chain[-20:]


def main():
    clean_prime_chains(eratosthenes(pow(2, 19)))


if __name__ == '__main__':
    import doctest
    doctest.testmod()

    main()