Here is the kata link: https://www.codewars.com/kata/59ccf051dcc4050f7800008f/shell

Buddy pairs 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

If there is no buddy pair satisfying the conditions, then return "Nothing" or (for Go lang) nil or (for Dart) null; (for Lua, Pascal, Perl) [-1, -1].

test.assert_equals(buddy(10, 50), [48, 75])

test.assert_equals(buddy(2177, 4357), "Nothing")

test.assert_equals(buddy(57345, 90061), [62744, 75495])

test.assert_equals(buddy(1071625, 1103735), [1081184, 1331967])

Here is my solution but it is taking too much time I'm getting Execution Timed Out error:

def sum_divisors(num):
    sum = 0
    for i in range(1, num):
        if num % i == 0:
            sum  = i

    return sum


def buddy(start, limit):
    for i in range(start, limit   1):
        sum = sum_divisors(i)
        sum_minus_one = sum_divisors(sum - 1)

        if start > sum - 1:
            continue

        if i == (sum_minus_one - 1):
            return [i, sum - 1]

    return "Nothing"

CodePudding user response：

Here's a fast way to find the sum of a number's divisors, based on its prime factorization:

from math import isqrt

def sum_of_divisors(n):
    result = 1
    div = 1
    while True:
        for div in range(div   1, isqrt(n)   1):
            if not n % div:
                mul = 1
                while not n % div:
                    n //= div
                    mul = 1   mul * div
                result *= mul
                break
        else:
            if n > 1:
                result *= 1   n
            return result

Consider for example n=100. Divisors are products of the prime factors, for example the divisor 50 is 2×5².

Initially known prime factors: None
Possible products of prime factors: Just the empty product, which has value 1.
Sum of those products: 1

After finding prime factor 2 (twice):
Possible products: The previous products multiplied by 2⁰, 2¹ or 2².
Sum of the products: The previous sum multiplied by (1 2 4), i.e., 1×7=7.

After finding prime factor 5 (twice):
Possible products: The previous products multiplied by 5⁰, 5¹ or 5².
Sum of the products: The previous sum multiplied by (1 5 25), i.e., 7×31=217.

If you subtract n itself, you get 117, which is also the sum of 1, 2, 4, 5, 10, 20, 25, and 50 (the list of proper divisors stated in the task description).

And my buddy function using the above:

def buddy(start, limit):
    def s(n):
        return sum_of_divisors(n) - n
    for n in range(start, limit   1):
        m = s(n) - 1
        if m > n and s(m) == n   1:
            return [n, m]
    return 'Nothing'

Comparing mine with gimix's on the largest case from Codewars, buddy(145_809_719, 145_812_719):

Kelly:  0.84 seconds
gimix: 10.57 seconds

Yours takes ~18 seconds for buddy(145_811_219, 145_811_219, which is only the median candidate of the 3001. If that's representative, then it would take ~15 hours for all 3001.

CodePudding user response：

Some optimizations:

To find the sum of divisors:

• 1 is always a divisor, so just count it and start looping from 2
• Just loop up to the square root of N, and count both the divisors you found (e.g., 4 is a divisor of 100, so 100//4 = 25 is a divisor too); but remember to avoid counting the square root twice

def divisors(n):
    divsum = 1
    for i in range(2,int(sqrt(n)) 1):
        d,m = divmod(n,i)
        if m == 0:
            divsum  = i
            if i != d:
                divsum  = n // i
    return divsum

To find the buddies:

• check if the sum of divisors of N is lower than start (and if so continue) before computing the second sum
• also check if the sum of divisors of N is lower than M (and if so continue as well)

def buddy(start,limit):
    for i in range(start, limit 1):
        sum1 = divisors(i)
        if start > sum1-1 or i > sum1:
            continue
        sum_minus1 = divisors(sum1 - 1)
        if i == (sum_minus1 - 1):
            return [i, sum1 - 1]
    else:
        return "Nothing"