Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- '''
- You know what divisors of a number are. The divisors of a positive integer n are said to be proper when you consider only the divisors other than n itself.
- In the following description, divisors will mean proper divisors. For example for 100 they are 1, 2, 4, 5, 10, 20, 25, and 50.
- Let s(n) be the sum of these proper divisors of n. Call buddy two positive integers such that the sum of the proper divisors of each number
- is one more than the other number:
- (n, m) are a pair of buddy if s(m) = n + 1 and s(n) = m + 1
- For example 48 & 75 is such a pair:
- Divisors of 48 are: 1, 2, 3, 4, 6, 8, 12, 16, 24 --> sum: 76 = 75 + 1
- Divisors of 75 are: 1, 3, 5, 15, 25 --> sum: 49 = 48 + 1
- Task
- Given two positive integers start and limit, the function buddy(start, limit) should return the first pair (n m) of buddy pairs
- such that n (positive integer) is between start (inclusive) and limit (inclusive); m can be greater than limit and has to be greater than n
- '''
- # FUNCTION 1
- def findBuddyOf(n):
- divisors = list()
- divisors.append(1)
- for i in range(2, int(n/2)+1):
- if n % i == 0:
- divisors.append(i)
- # print(divisors)
- sum1 = sum(divisors)
- otherN = sum1 - 1
- divisors2 = list()
- divisors2.append(1)
- for i in range(2, int(otherN/2)+1):
- if otherN % i == 0:
- divisors2.append(i)
- # print(divisors2)
- sum2 = sum(divisors2)
- if n == sum2 - 1:
- return otherN
- else:
- return None
- # FINCTION 2
- def buddy(start, limit):
- for n in range(start, limit+1):
- m = findBuddyOf(n)
- if m is not None:
- # The pair (n, m) is a buddy pair. I also have to check the conditions of m
- if m > n:
- return n, m
- return "Nothing"
- # MAIN FUNCTION
- start1, end1 = 10, 50
- start2, end2 = 2177, 4357
- start3, end3 = 57345, 90061
- print()
- print("***********************************************************")
- print("******** This process will last less than 1 minute ********")
- print()
- from timeit import default_timer as timer
- start = timer()
- buddy1 = buddy(start1, end1)
- buddy2 = buddy(start2, end2)
- buddy3 = buddy(start3, end3)
- end = timer()
- timeInMillis = 1000 * (end - start)
- timeInSeconds = timeInMillis / 1000
- print("buddy(" + str(start1) + ", " + str(end1) + ") = " + str(buddy1))
- print("buddy(" + str(start2) + ", " + str(end2) + ") = " + str(buddy2))
- print("buddy(" + str(start3) + ", " + str(end3) + ") = " + str(buddy3))
- print()
- print("Execution time = " + str(timeInSeconds) + " seconds.")
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement