Find the nth lucky number generated by a sieve in Python
Question: I'm trying to make a program in Python which will generate the nth lucky
number according to the [lucky number
sieve](http://en.wikipedia.org/wiki/Lucky_number). I'm fairly new to Python so
I don't know how to do all that much yet. So far I've figured out how to make
a function which determines all lucky numbers below a specified number:

    
    
    def lucky(number):
        l = range(1, number + 1, 2)
        i = 1
        while i < len(l):
            del l[l[i] - 1::l[i]]
            i += 1
        return l
    

Is there a way to modify this so that I can instead find the nth lucky number?
I thought about increasing the specified number gradually until a list of the
appropriate length to find the required lucky number was created, but that
seems like a really inefficient way of doing it.

**Edit:** I came up with this, but is there a better way?

    
    
    def lucky(number):
        f = 2
        n = number * f
        while True:
            l = range(1, n + 1, 2)
            i = 1
            while i < len(l):
                del l[l[i] - 1::l[i]]
                i += 1
            if len(l) >= number:
                return l[number - 1]
            f += 1
            n = number * f
    


Answer: > I came up with this, but is there a better way?

Truth is, there will _always_ be a better way, the remaining question being:
is it _good enough_ for your need?

One possible improvement would be to turn all this into a generator function.
That way, you would only compute new values as they are consumed. I came up
with this version, which I only validated up to about 60 terms:

    
    
    import itertools
    
    
    def _idx_after_removal(removed_indices, value):
        for removed in removed_indices:
            value -= value / removed
        return value
    
    
    def _should_be_excluded(removed_indices, value):
        for j in range(len(removed_indices) - 1):
            value_idx = _idx_after_removal(removed_indices[:j + 1], value)
            if value_idx % removed_indices[j + 1] == 0:
                return True
        return False
    
    
    def lucky():
        yield 1
        removed_indices = [2]
        for i in itertools.count(3, 2):
            if not _should_be_excluded(removed_indices, i):
                yield i
                removed_indices.append(i)
                removed_indices = list(set(removed_indices))
                removed_indices.sort()
    

If you want to extract for example the 100th term from this generator, you can
use [itertools nth
recipe](http://docs.python.org/2/library/itertools.html#recipes):

    
    
    def nth(iterable, n, default=None):
        "Returns the nth item or a default value"
        return next(itertools.islice(iterable, n, None), default)
    
    print nth(lucky(), 100)
    

I hope this works, and there's without any doubt more room for code
improvement (but as stated previously, there's _always_ room for
improvement!).

