Prime number module

[Anton Vredegoor]

Lulu of the Lotus-Eaters <mertz at gnosis.cx> wrote:

>Anything that is left over after this filtering is--by definition--of
>unknown primality.  You need to encode that by putting a 1 or 0 in the
>bit position corresponding to the number remaining.  IOW:
>
>    toEncode = filter(lambda n: n%2 and n%3 and n%5 and n%7, range(10**8)))
>    for n in toEncode:
>        if isPrime(n):
>            bitfield.append(1)
>        else:
>            bitfield.append(0)
>
>You might want to run that first line on a fast machine with plenty of
>memory. :-)

I've been keeping some code to myself, because there seemed to be no
direct connection to this thread. However, now that you mention
needing a lot of resources there's a reason to post because my script
creates an infinite generator function that can produce the numbers
for your toEncode list more efficiently.

Anton

def period(L):
    """suppose we enumerate all integers >= 2 which are
        not a multiple of  any of the numbers in L (L is a list
        of  prime numbers) and take the first order differences.
        This list repeats itself after some time. The period length 
        is the product of [x-1 for x in L]."""
    return reduce(lambda i,j: i*(j-1),L,1)

def primedeltas(L):
    """return one full period of differences"""
    diffs,p =  [],period(L)
    prev = i = 1
    while len(diffs) < p:
        i += 2
        for j in L:
            if i%j == 0: break
        else:  
            diffs.append(i-prev)
            prev= i
    return diffs

def excludemultiples(L):
    """return each number in L and then return numbers
        that are not multiples of any number in L. L is a list
        of primes"""
    i,pp = 1,primedeltas(L)
    for p in L: yield p
    while 1:
        for p in pp:
            i += p
            yield i
    
def test():
    L= [2,3,5,7]
    em = excludemultiples(L)
    for i,m in enumerate(em):
        print m,
        if i==14:
            print
            break
    #print [x/2 for x in primedeltas(L)]
    
if __name__=='__main__':
    test()