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. 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 1

n=input('enter n ')
a= list(xrange(1,n))
x=a[1]
for i in range(1,n):
    del a[x-1::x]
    x=a[i]
    l=len(a)

    if i==l-1:
        break

print "lucky numbers till %d" % n
print a  


lets do this with an example.lets print lucky numbers till 100
put n=100
firstly a=1,2,3,4,5....100
x=a[1]=2
del a[1::2] leaves 
a=1,3,5,7....99
now l=50
and now x=3
then del a[2::3] leaving a =1,3,7,9,13,15,.....
and loop continues till i==l-1

Answer 2

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:

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!).

Answer 3

With numpy arrays, you can make use of boolean indexing, which may help. For example:

>>> a = numpy.arange(10)
>>> print a
[0 1 2 3 4 5 6 7 8 9]

>>> print a[a > 3]
[4 5 6 7 8 9]

>>> mask = np.array([True, False, True, False, True, False, True, False, True, False])
>>> print a[mask]
[0 2 4 6 8]

Here is a lucky number function using numpy arrays:

import numpy as np

class Didnt_Findit(Exception):
    pass

def lucky(n):
    '''Return the nth lucky number.

    n --> int

    returns int
    '''

    # initial seed
    lucky_numbers = [1]
    # how many numbers do you need to get to n?
    candidates = np.arange(1, n*100, 2)
    # use numpy array boolean indexing
    next_lucky = candidates[candidates > lucky_numbers[-1]][0]

    # accumulate lucky numbers till you have n of them
    while next_lucky < candidates[-1]: 
        lucky_numbers.append(next_lucky)
        #print lucky_numbers
        if len(lucky_numbers) == n:
            return lucky_numbers[-1]
        mask_start = next_lucky - 1
        mask_step = next_lucky
        mask = np.array([True] * len(candidates))
        mask[mask_start::mask_step] = False
        #print mask
        candidates = candidates[mask]
        next_lucky = candidates[ candidates > lucky_numbers[-1]][0]
    raise Didnt_Findit('n = ', n)

>>> print lucky(10)
33

>>> print lucky(50)
261

>>> print lucky(500)
3975

Checked mine and @icecrime's output for 10, 50 and 500 - they matched.

Yours is much faster than mine and scales better with n.