Friendly rooms
I am struggling with optimizing these functions, which I used to calculate the sum of friendly pairs under 10000. A friendly pair is a pair (a, b), where the sum of the divisors of "a" excluding "a" is b, and the sum of the divisors "b" excluding "b" is equal to "a".
those. the divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110: the sum of which is 284. And the sum of the divisors of 284 (1, 2, 4, 71, and 142) is 220.
My code:
import math
def Divisorsbaritself(x):
divList = [1]
y = 2
while y <= math.sqrt(x):
if x % y == 0:
divList.append(y)
divList.append(int(x / y))
y += 1
return sum(divList)
def amicable():
solution = []
for i in range(10000):
if Divisorsbaritself(Divisorsbaritself(i)) == i:
solution.append(i)
return sum(solution)
print amicable()
I need help understanding why the friendly function is not working. It makes sense for me to understand that the condition if Divisorsbaritself(Divisorsbaritself(i)) == i:
is the correct condition for being included i
in the list, but it gives me 40285 and not the answer 31626.
If Divisorsbaritself(i)==i
, you shouldn't count i
.
def amicable():
solution = []
for i in range(10000):
if Divisorsbaritself(i)!=i and Divisorsbaritself(Divisorsbaritself(i)) == i:
solution.append(i)
return sum(solution)
But you also have to correct the mistake, which would be a problem if I am a perfect square and in a friendly couple.
You can improve this with a list.
def amicable():
solution = [i for i in xrange(10000) if Divisorsbaritself(i)!=i and Divisorsbaritself(Divisorsbaritself(i)) == i]
return sum(solution)
source to share
They are friendly rooms only if they are different. Therefore, if divsum(i)
equal i
, then it is not included, although it is divsum(divsum(i))
also equal i
.
Also, your current check calculates the square root of a perfect square twice, even though that's only one factor.
And besides, I would not use a list and then sum it up at the end when you can just use an accumulator. And it's usually faster to do multiplication than square roots, so you can change the loop while
to take that into account.
Finally, for the love of those gods you believe in, please comment your code! It will be much easier to understand what is happening, both for others and for you in six months.
Enabling these changes gives you the following function DivisorsBarItself
:
def DivisorsBarItself(num):
# Maintain sum of factors.
divSum = 1
# Go through every integer up to but excluding sqrt(num).
testnum = 2
while testnum * testnum < num:
# If factor, add it and the complement (guaranteed integer).
if num % testnum == 0:
divSum += testnum + num/testnum
testnum += 1
# If perfect square, add the square root once.
if testnum * testnum == num:
divSum += testnum
# Return the sum.
return divSum
Fixing the logic to detect friendly numbers and using a sum rather than a list gives you:
def AmicableSum():
# Set sum to zero and process all numbers below 10,000.
solution = 0
for num in range(10000):
# Get the "friend", add only if different and f(f(x)) = x.
numFriend = DivisorsBarItself(num)
if numFriend != num and DivisorsBarItself(numFriend) == num:
solution += num
return solution
print AmicableSum()
which gives the correct result 31626
.
source to share
I wrote everything you said as a function
def devisor(a):
listOfFactors=[]
for possibleFactor in range(1,a):
if a%x==0:
listOfFactors.append(possibleFactor)
sumOfFactors=0
for item in z:
sumOfFactors+=item
factorsOfNewSumAddedUp=0
for x in range(1,sumOfFactors):
if temp%x==0:
factorsOfNewSumAddedUp+=x
if a==factorsOfNewSumAddedUp:
print("this is a divisor")
source to share