毎朝Codewars@2019.06.17(月): Buddy Pairs

毎朝ちびちびCodewars。

[5 kyu] Buddy Pairs www.codewars.com

今日のお題：

"""
自分自身を除く約数を proper な約数と言うらしい。
例えば 48の properな約数は、1, 2, 3, 4, 6, 8, 12, 16, 24 だ。  
nの properな約数の和を s(n) とする。 先の例なら 1 + 2 + .. + 24 = 76

2つの異なる正の整数nとmについて、自分のproperな約数の和 s(n)が、相手に1を足した値に等しい  
つまり s(m) = n + 1 　かつ  s(n) = m + 1 である n, m のペアを Buddy Pairs （※）と呼ぶ。

start <= n <= limit を満たす最小の Buddy Pairs (n, m)を求めよ。
なお n < m で、m は limit を超えてもOK。

def buddy(start, limit):
Args:  
    start, limit (int)
Returns:  
    [n, m]: Buddy Pairs
"""

※日本語では”婚約数”と呼ぶらしい。
婚約数 - Wikipedia

コード

最終コード （わーい解決 @2019.06.19）

タイムアウト解決バージョン。
get_sum_of_propers(n) に関して、コード2から次の2点を改良した。

1. 約数の一覧を求めてから sum()で足し算する代わりに、直接加算する。ここでは約数を一覧することは問われていない。合計がわかればいい。
2. 毎回 n // x, n % x の両方求めていたのを n % x だけに。
   n // x の値は 割り切れた時だけ必要になる値だから毎回計算する必要なし。

import math


def get_sum_of_propers(n):
    sum = 0
    for x in range(2, int(math.sqrt(n))+1):
        if n % x == 0:
            sum += x
            if x != n // x:
                sum += n // x
    return sum

def buddy(start, limit):
    for n in range(start, limit+1):
        m = get_sum_of_propers(n) 
        if n < m and n == get_sum_of_propers(m) :
            return [n, m]
    return "Nothing"

コード2 : 未完成＠タイムアウト

ロジック的には正しく解けてると思うんだけど タイムアウトで通過できてない (><) ひとまずブログに貼っておいて、明日考える。

import math


def get_sum_of_propers(n):
    propers = []
    dv = n
    for x in range(2, int(math.sqrt(n))+1):
        dv, md = n // x, n % x
        if md == 0:
            propers.append(x)
            if x != dv:
                propers.append(dv)
    return sum(propers)


def buddy(start, limit):
    for n in range(start, limit+1):
        m = get_sum_of_propers(n) 
        if n < m and n == get_sum_of_propers(m) :
            return [n, m]
    return "Nothing"

コード3: 一番最初に書いたコード（猛烈遅い）

以下は、一番最初に書いた get_sum_of_propers(n)部分。　buddy()本体は上と同じ。
get_sum_of_propers(n) は、こっちの方がスッキリ見えるが計算量が多くてnが大きくなると猛烈遅い。
前述のコードもまだタイムアウトするものの、このコードに比べれば 2桁スピードアップしてる。

def get_sum_of_propers(n):
    return sum(x for x in range(1, (n // 2) + 1) if n % x == 0)