CODEWITHSUNDEEP
python
user11433299
user11433299

Reputation:

Python seems to be slow solving Project Euler problem #21

I am trying to solve Problem 21 from Project Euler. I think that I've written everything correctly. However, I cannot get the final answer because the program does not get fully executed.

def d(num):
    SUM = 0
    for i in range(1,num):
        if num % i == 0:
            SUM += i
    return SUM


SUM = 0
for a in range(1,10000):
    for b in range(1,10000):
        if a != b:
            if d(a) == b and d(b) == a:
                SUM += a+b

print(SUM)

Upvotes: 2

Views: 385

Answers (5)

Alain T.
Alain T.

Reputation: 42143

You can use the same technique as the sieve of Eratosthenes to build a list of factor sums. Then match values at positions to find the amicable numbers.

# find amicable pairs (a,b) where a < b <= maxN
def findami(maxN):
    sumFact = [0]*(maxN+1)              # prepare factor sums list
    for n in range(1,maxN//2+1):        # propagate factors (up to half N)
        for f in range(2*n,maxN+1,n):   # add to multiples of n > 2n
            sumFact[f] += n
    return [(s,n) for n,s in enumerate(sumFact) if s<n and sumFact[s] == n]

Given that there is no amicable pair that crosses the 10,000 mark, you can use findami(10_000) directly to sum up the result.

print(findami(11_000),sep="\n")

(220, 284)
(1184, 1210)
(2620, 2924)
(5020, 5564)
(6232, 6368)
(10744, 10856)

print(sum(map(sum,findami(10_000))))  # takes 18 ms on my laptop

31626

Upvotes: 0

John Coleman
John Coleman

Reputation: 51998

Think of the problem from the perspective of the divisors rather than the perspective of the number being divided. A key insight is that if n < 10000 and d is a proper divisor of n then n must look like n = i*j where i < 100 and d is one of i or j. Thus -- you should be able to determine all of the values of d[n]in the range by a nested loop, where the outer loop executes just 100 times. The idea is to create a dictionary of all candidate n (with values initialized to 0), loop over all candidate i, and then add i (and j if appropriate) to the value d[n]. The following works (and solves the problem for numbers other than 100000):

import math

def divisor_sums(k):
    s = math.ceil(math.sqrt(k))
    d = {n:1 for n in range(2,k)}
    d[1] = 0 #special case
    for i in range(2,s):
        for j in range(2,k//i):
            n = i*j
            d[n] += i
            if s <= j: d[n] += j
    return d

def amicables(k):
    d = divisor_sums(k)
    pairs = []
    for a in range(2,k):
        b = d[a]
        if a != b and b < k and a == d[b] : pairs.append((a,b))
    return pairs

def amicable_sum(k):
    pairs = amicables(k)
    return sum(a+b for a,b in pairs if a < b)

For example:

>>> amicable_sum(10000)
31626
>>> amicable_sum(100000)
852810
>>> amicable_sum(1000000)
25275024

The first one was instantaneous, the second one took less than a second, and the third one about 5 seconds (on my machine).

Upvotes: 1

g_bor
g_bor

Reputation: 1092

There seems to be too much computation going on here. You have the second nested loop, with 10000*10000 execution, and each is calculating d twice, resulting in 10000 steps on average in the inner loop. This is 10^12 steps. I believe this will be slow even on quite potent machines. Can you think of a way to reduce the time complexity of your solution?

Upvotes: 0

Code-Apprentice
Code-Apprentice

Reputation: 83527

This isn't a python problem. Your algorithm will run slow no matter what language it is written in because you have three nested for loops when you can reduce it to only two. The problem is that you are calculating d(x) 100000000 times for each value of x in the range from 1 to 10000. You should only calculate it once for each x.

Upvotes: 0

Robert Price
Robert Price

Reputation: 641

The for b in range(1, 10000) loop is unnecessary, because you know that there is at most one appropriate b, and if it exists, it equals d(a).

Also, beware of counting each a and b twice in your final SUM.

SUM = 0
for a in range(1,10000):
    b = d(a)
    if a != b and d(b) == a:
        SUM += a+b

print(SUM//2)

Upvotes: 3

Related Questions