infinite elves and infinite houses

approach

a house's presents depend on the divisors of its number, so multiples lists them by trial division up to the square root, adding both i and n / i. part 1 walks the house numbers until ten times the divisor sum reaches the input.

part 2 keeps a counter of how many houses each elf has visited and ignores an elf once it is over the limit, with eleven presents per visit. the python file only prints part 2 (the part 1 call is commented out); the rust version in rust-sol is the same algorithm and prints both.

the trick

collect divisors in pairs up to √n instead of trying every number below n.

def multiples(n):
    res = []
    for i in range(1, floor(sqrt(n)) + 1):
        d, m = divmod(n, i)
        #print(n, d, i)
        if m != 0:
            continue
        if d == i:
            res.append(d)
        else:
            res.append(d)
            res.append(i)
    return res