5
\$\begingroup\$

Given a limit \$n\$, find all the pairs of values less than, or equal to n, which have the the property:

pair(a,b)

where a = sum of divisors of b
  and b = sum of divisors of a

I need to speed up my double for-loop but I don't see how to do it in this case.

def diviseurs_propres(n):
    t = [1]
    for i in range(2,n):
        if n%i == 0:
            t.extend([i])
    return t 

def somme_diviseurs_propres(n):
    t = diviseurs_propres(n)
    S = sum(list(t))
    return S

def trouveur(n):
    t = []
    for i in range(0,n+1):
        for p in range(0,n+1):
            if p != i and somme_diviseurs_propres(i) == p and i == somme_diviseurs_propres(p):
             t.extend([p]) and t.extend([i]) 
    return t
\$\endgroup\$
  • \$\begingroup\$ In terms of other noteworthy items, i think your current code for the trouveur function will have duplicate values within the result t. Is this by design? Hence the questions on what you are trying to do, as different optimisations may be possible depending on desired results. \$\endgroup\$ – Mike Curry Feb 17 '15 at 10:11
16
\$\begingroup\$

Mike is correct that you are repeating the sum multiple times for each value. A simple array with the stored sum will make a huge difference.

On the other hand, you are also doing a huge amount of unnecessary work in here:

def diviseurs_propres(n):
    t = [1]
    for i in range(2,n):
        if n%i == 0:
            t.extend([i])
    return t 

def somme_diviseurs_propres(n):
    t = diviseurs_propres(n)
    S = sum(list(t))
    return S

There is no need to store the actual values in an array, it can be simplified to just:

def somme_diviseurs_propres(n):
    sum = 1
    for i in range(2, n):
        if n % i == 0:
            sum += i
    return sum

With a little bit of math, you can significantly reduce the number of iterations by iterating to the square-root of the value:

def somme_diviseurs_propres(n):
    sum = 1
    root = int(math.ceil(math.sqrt(n)))
    for i in range(2, root):
        if n % i == 0:
            sum += i + (n / i)
    if root > 1 and root * root == n:
        sum += root
    return sum

The way the above code works, is each time you have a value \$a\$ that is a factor of \$n\$, then there must be a value \$n / a\$ that is also an factor.

Thus, for large values of \$n\$, like 1000000, you only need to iterate from 2 to 1000 (exclusive) to sum the factors. Now, because 1000000 is an exact square, the root is an actual integer too, and the last if-statement above adds in the value 1000 to the sum.

In addition to the above, you can also rearrange the double-loops so that the inner loop is limited by the outer loop, and then add the pairs twice to the results. This changes the order of the results, but not the actual content.... Finally, your use of extend should be replaced with append...

def trouveur(n):
    t = []
    for i in range(0, n+1):
        for p in range(0, i):
            if somme_diviseurs_propres(i) == p and i == somme_diviseurs_propres(p):
                t.append(p) and t.append(i) 
                t.append(i) and t.append(p) 
    return t

Now, there's a bug in there, I believe. The code:

t.extend([p]) and t.extend([i])

does not add the second value i. You only add the i on the second time through, when i == p and p == i .... Your code above is equivalent to just:

t.extend([p])

Using a dictionary

As an update, I have considered a second soltuion, that should significantly reduce the amount of iteration in the inner loops, at the expense of lookups in a dictionary.

The dictionary maps the sum-of-factors to the values that have that sum. For example, the sum of factors for 6 and 25 are both 6. (sum of factors of 6 are 3 + 2 + 1, and for 25 it is 5 + 1). The mapping looks like:

6 -> [6, 25]

Using that mapping, we can look for sums that have cross-references... We can loop through just the sums of the factors, and for each sum, in their set of input values, see if those values exist as sums of other values. If they do, then see if the original sum is one of them.... This makes sense if you see an example:

220 -> [284]
284 -> [220]

the top value shows that the sum of factors for 284 is 220, and the sum of factors for 220, is 284.

Taking the first value, we know the sum of factors, and we take all the values that sum to that (in this case, just 284), and check whether 284 happens to be the sum of some other value's factors. Then we check to see whether one of those other values is 220.

def trouveur(n):
    sommeMap = {}
    for i in range(1, n + 1):
        s = somme_diviseurs_propres(i)
        if s in sommeMap:
            sommeMap[s].append(i)
        else:
            sommeMap[s] = [i]

    t = []
    for i,ps in sommeMap.items():
        for p in ps:
            if i < p and p in sommeMap and i in sommeMap[p]:
                t.append(i)
                t.append(p)
    return t

Performance results:

Your initial code, with a limit of 500

Result: [284, 220]

real    0m4.851s
user    0m4.840s
sys     0m0.012s

Using Mike's suggestion of saving away the sums:

def trouveur(n):
    somme = []
    t = []
    for i in range(0,n+1):
        somme.append(somme_diviseurs_propres(i))

    for i in range(0,n+1):
        for p in range(0,n+1):
            if p != i and somme[i] == p and i == somme[p]:
             t.extend([p]) and t.extend([i])
    return t

This produces the times:

Result: [284, 220]

real    0m0.064s
user    0m0.056s
sys     0m0.008s

Including the changes I suggest

  • no arrays for the sum of factors
  • change the loops
  • separate the i and p appends

Code:

import math


def somme_diviseurs_propres(n):
    sum = 1
    root = int(math.ceil(math.sqrt(n)))
    for i in range(2, root):
        if n % i == 0:
            sum += i + (n / i)
    if root > 1 and root * root == n:
        sum += root
    return sum



def trouveur(n):
    somme = []
    t = []
    for i in range(0, n + 1):
        somme.append(somme_diviseurs_propres(i))

    for i in range(0, n + 1):
        for p in range(0, i):
            if somme[i] == p and i == somme[p]:
                t.append(p)
                t.append(i)
    return t


print "Result: {}".format(trouveur(500))

and results:

Result: [220, 284]

real    0m0.028s
user    0m0.016s
sys     0m0.008s

Note that it is now possible to run the code up to 10000 as well....

Result: [220, 284, 1184, 1210, 2620, 2924, 5020, 5564, 6232, 6368]

real    0m2.453s
user    0m2.444s
sys     0m0.004s

Using dict (sommeMap)

Result: [220, 284]

real    0m0.024s
user    0m0.016s
sys     0m0.008s

and for 10,000 it runs in:

Result: [220, 284, 1184, 1210, 2620, 2924, 5020, 5564, 6232, 6368]

real    0m0.092s
user    0m0.088s
sys     0m0.000s

Which is significantly faster, and we can extend that even further now, to say 1,000,000 values:

Result: [[220, 284], [1184, 1210], [2620, 2924], [5020, 5564], [6232, 6368], 
    [10744, 10856], [12285, 14595], [17296, 18416], [63020, 76084], [66928, 66992],
    [67095, 71145], [69615, 87633], [79750, 88730], [100485, 124155], [122265, 139815],
    [122368, 123152], [141664, 153176], [142310, 168730], [171856, 176336],
    [176272, 180848], [185368, 203432], [196724, 202444], [280540, 365084],
    [308620, 389924], [319550, 430402], [356408, 399592], [437456, 455344],
    [469028, 486178], [503056, 514736], [522405, 525915], [600392, 669688],
    [609928, 686072], [624184, 691256], [635624, 712216], [643336, 652664],
    [667964, 783556], [726104, 796696], [802725, 863835], [879712, 901424],
    [898216, 980984]]

real    0m55.310s
user    0m55.135s
sys     0m0.164s

Code Drop

This is the final version of the code I have. The code above has gone through a number of iterations, and was inconsistent in places:

import math


def somme_diviseurs_propres(n):
    sum = 1
    root = int(math.ceil(math.sqrt(n)))
    for i in range(2, root):
        if n % i == 0:
            sum += i + (n / i)
    if root > 1 and root * root == n:
        sum += root
    return sum


def trouveur(n):
    sommeMap = {}
    t = []
    for i in range(1, n + 1):
        s = somme_diviseurs_propres(i)
        if s in sommeMap:
            sommeMap[s].append(i)
        else:
            sommeMap[s] = [i]

    for i, ps in sommeMap.items():
        for p in ps:
            if i < p and p in sommeMap and i in sommeMap[p]:
                t.append([i, p])
    return t


print "Result: {}".format(trouveur(100000))
\$\endgroup\$
  • 2
    \$\begingroup\$ This is an insanely detailed answer, I wish I had more than one upvote \$\endgroup\$ – Devon Parsons Feb 17 '15 at 17:25
  • \$\begingroup\$ Nice answer! I might be missing something but in each snippet of code, you have something like for p in range(0, i): if somme[i] == p and .... Do we need the p loop at all ? Can't we just do p = somme[i]; if 0 <= p < i ? Also (and before I suggest such an answer), have you considered generating an array with the sum of divisors using some kind of logic like the Eratosthene sieve to avoid successive divisions ? \$\endgroup\$ – SylvainD Feb 18 '15 at 9:28
  • \$\begingroup\$ Also, running somme_diviseurs_propres on [1..100], for instance, I'd expect the result to be 1 only for primes numbers (which is not the case of 15 nor 35 for example) \$\endgroup\$ – SylvainD Feb 18 '15 at 11:35
  • \$\begingroup\$ @Josay - your second comment first - There is an internal inconsistency in the answer. I updated the somme_diveseurs_propres in the description of that function, but not in the code block I added earlier in the performance section (ceil vs. floor). I have added a 'code drop' section to contain my current code. As for the p loop, I have not considered that. Seems interesting. Finally using the sieve would be a good option, I believe a lot of my time on large inputs (1000000) is "lost" to factoring large primes. Converting the prime-factors to all factors is interesting though... \$\endgroup\$ – rolfl Feb 18 '15 at 11:43
  • \$\begingroup\$ Thanks for your answer. I've added an answer reusing your code and somehow improving it. \$\endgroup\$ – SylvainD Feb 18 '15 at 14:12
10
\$\begingroup\$

Reusing rolfl's excellent answer, you can quickly build a cache containing all the sums you'll need. This is quite an easy and efficient way to do because we know an upper bound, we know that we'll want the sum of divisors for all divisors up to that bound.

Thus, we just need a function to compute a cache and one to go through it :

def somme_diviseurs_cache(lim):
    a = [1] * lim
    for i in range(2, (1+lim)/2):
        for j in range(2*i, lim, i):
            a[j] += i
    return a

def trouveur(n):
    sums = somme_diviseurs_cache(n+1)
    for i, s in enumerate(sums):
        if 0 <= s < i and sums[s] == i:
            yield (s,i)

For various max values, I find the same results as rolfl's code but it's much faster (and the bigger the value is, the bigger the difference is):

================
300 000 : 16 times faster
----------------
real    0m5.345s
user    0m5.324s
sys     0m0.016s
----------------
real    0m0.334s
user    0m0.328s
sys     0m0.004s
================
500 000 : 20 times faster
----------------
real    0m11.696s
user    0m11.680s
sys     0m0.012s
----------------
real    0m0.594s
user    0m0.584s
sys     0m0.008s
================
1 000 000 : 23 times faster
----------------
real    0m34.418s
user    0m34.384s
sys     0m0.040s
----------------
real    0m1.498s
user    0m1.484s
sys     0m0.012s

Actually, I've edited my code to take into account rolfl's comment about stopping the i loop at (1+lim)/2 instead of lim and it makes my code even (even it is very very subtle) faster.

\$\endgroup\$
  • \$\begingroup\$ Arghh... yes, I reduced it down a lot, but not far enough. The need for the dict is still overkill, and your solution makes it \$O(n)\$. Hopefully, at least, my answer helped to remove some of the levels of complexity ;-) Looks like your solution is about linear.... which is really nice to see. \$\endgroup\$ – rolfl Feb 18 '15 at 14:23
  • \$\begingroup\$ Additionally, I really like the trick you played to calculate the sum-of-factors.... that's smart. Have you considered terminating the i loop at lim/2 instead? \$\endgroup\$ – rolfl Feb 18 '15 at 14:25
  • \$\begingroup\$ I didn't think about it. Probably a good idea. I'll update the code and the benchmark asap. \$\endgroup\$ – SylvainD Feb 18 '15 at 14:39
4
\$\begingroup\$

Without having more detail on what the code does, it is difficult to be sure what to do, however, there are some optimisation options available.

One of the first ones to note is that somme_diviseurs_propres will be called multiple times for the same value of n.

If you cache the calculation for repeated uses of the same value of n you will get a performance increase at the cost of memory usage.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.