Home > python > Finding number pairs where the sum of their divisors are each other

# Finding number pairs where the sum of their divisors are each other

February 17Hits:1
Advertisement

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 `
```

## Answers

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))
```
```

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.

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.

## Related Articles

• ### Finding number pairs where the sum of their divisors are each otherFebruary 17

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

• ### List the first 20 friendly number pairsDecember 23

I just started reading about friendly numbers and I think they sound great. In number theory, friendly numbers are two or more natural numbers with a common abundancy, the ratio between the sum of divisors of a number and the number itself. Two numbe

• ### Algorithm to find pair with max sum from two arraysDecember 9

Algorithm to find pair with max sum from two arrays A[0 ... n] and B[0 ... n] A[i] + B[j] = max (A[i] + B[j], with i < j) i,j < 99999; n < 99999 My best result is this: int[] testArrayA = { 7, 1, 4, 5, 1}; int[] testArrayB = { 3, 2, 1, 5, 3}; Str

• ### Minimum number of numbers to sum to exactly nDecember 10

First question here, don't yell at me if this is a duplicate or a bad challenge. Introduction I thought of this challenge myself, and it seems to be a good basic puzzle for beginner code-golfers. It also might help me decide which code-golfing langua

• ### What is the smallest number that equals the sum of two cubes in two ways? January 16

How does one find the smallest number that equals the sum of two perfect cubes(positive) in two ways? --------------Solutions------------- I doubt if this question is on the correct forum, but... this can be accomplished using Minimize with constrain

• ### Given an array[] of positive integers and another integer k, find number of subset whose sum is multiple of k January 26

Given an array[] of positive integers and another integer k, I have to find number of subset whose sum is multiple of k(sum is evenly divisible by k). For example, array[] = {1, 2, 3, 4}, k = 3 Subset sums are, 1 = 1 1 + 2 = 3 1 + 2 + 3 = 6 1 + 2 + 3

• ### Next number with the same sum of digitsFebruary 11

I recently came across a email bot that would give you random problems to solve. Here is the problem. Please write a function in python which receives a natural decimal N-digit number (1 to 15 digits long) as an input and returns the minimal next N-d

• ### Find all integers between m and n whose sum of squared divisors is itself a squareJanuary 20

Divisors of 42 are : 1, 2, 3, 6, 7, 14, 21, 42. These divisors squared are: 1, 4, 9, 36, 49, 196, 441, 1764. The sum of the squared divisors is 2500 which is 50 * 50, a square! Given two integers \\$m\\$, \\$n\\$ (\\$1 \le m \le n\\$) we want to find all i

• ### Number of ways to sum [1..n] with [n+1..2n] such that each sum is primeMay 25

Let n > 0. Let X = [1..n] and Y = [n+1 .. 2n]. Define a(n) as the number of permutations p of Y such that every element of X + p(Y) is prime. For example: n = 2 X = [1,2] Y = [3,4] p0(Y) = [3,4] => X + p0(Y) = [4,6] => No p1(Y) = [4,3] => X +

• ### Given number which equals the sum of some of the 10 numbers. How to determine that given number contains one of 10 numbers?June 2

I have: ten numbers: +1, +2, +4, +8, +16, +32, +64, +128, +256, +512. flag == sum of some of this ten numbers. How to determine that sum contains 2 or 32? --------------Solutions------------- Let's convert those numbers to binary: 1₁₀ → 0001₂ 2₁₀ → 0

• ### Write a Number as a Fibonacci SumDecember 18

Let us define the Fibonacci sequence as F(1)=1 F(2)=2 F(n)=F(n-2)+F(n-1) So we have the infinite sequence 1,2,3,5,8,13,... It is well known that any positive integer can be written as a sum of some Fibonacci numbers. The only caveat is that this summ

• ### Create certain number of Clusters, equal sum of Z valueFebruary 6

Divide polygons into *n* number of groups of equal counts with ArcGIS 10.2 is very similar to my question. But instead of equal number of polygons, I have multiple points (schools) with a z value (students in a special program). I am in 10.2. I have

• ### Excel formula sum multiple rows/column once on cell has reached it's max number and continue to sumJune 5

I am trying to come up with a formula that will split three rows of numbers evenly until one cell reaches a max number and then continue to sum the same three rows but split all the new values in two and no longer give the cell that's reached it's nu

• ### Finding number of number pairs with given difference August 20

pairs() is a function which returns the total number of combinations whose difference is k. static int pairs(int[] a,int k) { int counter=0; for (int i : a.length ) { for(int j=i+1;j<a.length;j++){ if(a[i]-a[j]==k||a[i]-a[j]==-k){ counter++; } } } re

• ### Print unique words, total number of occurrences and sum using `awk`January 3

How can I print unique words, number of their occurrences and the sum of their values in the relevant column using a single array in awk? I'm using awk like: awk -F, '{sum[\$1]+=\$2} END{for (x in sum) print x, sum[x]}' inFile Can I modify the command

• ### How many ways to get a fixed number that is the sum of three numbers? [on hold]February 13

Let's say you want to find out how many ways there is to make the number 5 using three numbers, which are added together. These are some of the ways: 005 => 0 + 0 + 5 = 5 122 => 1 + 2 + 2 = 5 Brute force is not an acceptable answer - this function n

• ### Is there a limit on the number of rows a sum function can calculate in Excel 2007?April 27

I am trying to sum a column of 50938 values in Excel 2007 but keep receiving a "#VALUE!" error. The cells in the column do contain formulas. I also tried to sum the column after copying and pasting values but received the same error. -----------

• ### Find the number of cells to sum to reach a certain amountJanuary 22

I have a column of values (they are ordered if that matters): A:A. I have two values: a starting value B1 which is also present somewhere in A:A, and a goal value C1. Let's say the we can find the value of B1 at A24, I want to know, how many values I

• ### Number pair prefix to config filesDecember 11

I have noticed some config files having a prefix. E.g. Inside my /etc/php5/cli/conf.d: 05-opcache.ini 10-pdo.ini 20-curl.ini ... Could someone explain this? I am thinking something along the lines of file permissions or list order. Thanks! ----------

• ### Searching the number with the biggest amount of odd divisors in an intervalDecember 3

I wrote this program for school (first year in college) and it works, but it's too slow. I wondered if anyone could help me optimize this a bit, because I've been trying and trying, but it just won't get better. If I choose a lower limit of 5000 and

Copyright (C) 2017 ceus-now.com, All Rights Reserved. webmaster#ceus-now.com 14 q. 0.426 s.