Advertisement
makispaiktis

Codewars - Buddy Pairs

Aug 10th, 2020 (edited)
1,632
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.53 KB | None | 0 0
  1. '''
  2.  
  3. 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.
  4. In the following description, divisors will mean proper divisors. For example for 100 they are 1, 2, 4, 5, 10, 20, 25, and 50.
  5. 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
  6. is one more than the other number:
  7.  
  8. (n, m) are a pair of buddy if s(m) = n + 1 and s(n) = m + 1
  9. For example 48 & 75 is such a pair:
  10.  
  11. Divisors of 48 are: 1, 2, 3, 4, 6, 8, 12, 16, 24 --> sum: 76 = 75 + 1
  12. Divisors of 75 are: 1, 3, 5, 15, 25 --> sum: 49 = 48 + 1
  13. Task
  14. Given two positive integers start and limit, the function buddy(start, limit) should return the first pair (n m) of buddy pairs
  15. 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
  16. '''
  17.  
  18. # FUNCTION 1
  19. def findBuddyOf(n):
  20.     divisors = list()
  21.     divisors.append(1)
  22.     for i in range(2, int(n/2)+1):
  23.         if n % i == 0:
  24.             divisors.append(i)
  25.     # print(divisors)
  26.     sum1 = sum(divisors)
  27.     otherN = sum1 - 1
  28.     divisors2 = list()
  29.     divisors2.append(1)
  30.     for i in range(2, int(otherN/2)+1):
  31.         if otherN % i == 0:
  32.             divisors2.append(i)
  33.     # print(divisors2)
  34.     sum2 = sum(divisors2)
  35.     if n == sum2 - 1:
  36.         return otherN
  37.     else:
  38.         return None
  39.  
  40. # FINCTION 2
  41. def buddy(start, limit):
  42.     for n in range(start, limit+1):
  43.         m = findBuddyOf(n)
  44.         if m is not None:
  45.             # The pair (n, m) is a buddy pair. I also have to check the conditions of m
  46.             if m  > n:
  47.                 return n, m
  48.     return "Nothing"
  49.  
  50. # MAIN FUNCTION
  51. start1, end1 = 10, 50
  52. start2, end2 = 2177, 4357
  53. start3, end3 = 57345, 90061
  54. print()
  55. print("***********************************************************")
  56. print("******** This process will last less than 1 minute ********")
  57. print()
  58.  
  59. from timeit import default_timer as timer
  60. start = timer()
  61. buddy1 = buddy(start1, end1)
  62. buddy2 = buddy(start2, end2)
  63. buddy3 = buddy(start3, end3)
  64. end = timer()
  65. timeInMillis = 1000 * (end - start)
  66. timeInSeconds = timeInMillis / 1000
  67. print("buddy(" + str(start1) + ", " + str(end1) + ") = " + str(buddy1))
  68. print("buddy(" + str(start2) + ", " + str(end2) + ") = " + str(buddy2))
  69. print("buddy(" + str(start3) + ", " + str(end3) + ") = " + str(buddy3))
  70. print()
  71. print("Execution time = " + str(timeInSeconds) + " seconds.")
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement