why isn't len returning correct values?

Question

def dbl_linear(n):
    u=[1]
    i=0
    for a in u:
        u.append((2*a+1))
        u.append((3*a+1))
        u=set(u)
        u=list(u)          
        if len(u)>=n:
            print(len(u))  
            break
    return len(u)

i want this code to return n elements in list u.But that isn't happening.can someone help? i gave input n=20.the len(u) is coming as 15 or 7.different answers on every run

Answer 1

Modifying an object you're iterating over is basically undefined behaviour, you can't assume whether the iterations will or will not take the new items in account, especially in the face of resize (list is O(1) amortized append, because it's O(1) on reserved space but they regularly need to reallocate the entire thing to make more room for new elements). Not to mention here you're only modifying the initial list during the first iteration, afterwards you're updating a different unrelated list.

There's no reason to even use for a in u, just use an infinite loop (and probably remember the last element as your uniquification via set will scramble the list, alternatively just check before inserting if the element is already present, in is O(n) but so are set(a) and list(a)).