This problem is very difficult for Python users. I needed to use every hack I could think of to pass this challenge without using a table of known amicable numbers (which is basically cheating).

• Create the list of amicable numbers according to the largest test case and then refer to that list. Don't generate the amicable numbers again and again (up to 1000 times) for each test case.

• Of course, memoize/cache the d function

• Minimum ratio of pair (m, n): m/n > .6978... So don't bother to compute d(d(i)) if d(i) is greater than N and 1.4*i. http://mathworld.wolfram.com/AmicablePair.html

• There is a nice forumla to get the sum of the proper divisors given the prime factorization of a number. https://en.wikipedia.org/wiki/Divisor_function

• Generate a list of primes once before getting prime factorizations instead of generating list of primes numerous times. Listing the primes will be the biggest bottle neck in the code. (Edit: this turned out to not be true. My sum_of_proper_divisors function was slow. See the responding comments for details.)

• You don't need to compute every prime below n. Numbers below n will not have any divisors above n/2. Continue with this reasoning to minimize the number of primes you compute. (This part is essential)

• I used a naive Sieve of Eratosthenes but if you have a faster implementation then use it.

• Combine the prime factoization funtion with the divisor summation function for speed. Here is the example of my function:

primes = Sieve_of_Eratosthenes(something_less_than_100000)

def sum_of_proper_divisors(n, primes):
    """
    input n and a list of primes
    returns the sum of the proper divisors
    """
    n_copy = n
    product = 1
    for p in primes:
        if p > n:
            break
        i = 0
        while n % p == 0:
            n //= p
            i += 1
        if i != 0:
            product *= (p**(i + 1) - 1)//(p - 1)
    return product - n_copy

I completed test case 3 in 7 seconds (out of 10).