Project Euler on Python(3) #002 (021~030)

e021.py

"""n의 약수들 중에서 자신을 제외한 것의 합을 d(n)으로 정의했을 때,
서로 다른 두 정수 a, b에 대하여 d(a) = b 이고 d(b) = a 이면
a, b는 친화쌍이라 하고 a와 b를 각각 친화수(우애수)라고 합니다.

예를 들어 220의 약수는 자신을 제외하면 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 이므로 그 합은 d(220) = 284 입니다.
또 284의 약수는 자신을 제외하면 1, 2, 4, 71, 142 이므로 d(284) = 220 입니다.
따라서 220과 284는 친화쌍이 됩니다.

10000 이하의 친화수들을 모두 찾아서 그 합을 구하세요."""


def memoize(f):
    cache = {}
    def wrapper(a):
        if a in cache:
            return cache[a]
        r = f(a)
        cache[a] = r
        return r
    return wrapper

@memoize
def sum_of_divisors(n):
    s = n + 1
    k = 2
    l = n ** .5
    while k <= l:
        if n % k == 0:
            s += k + (n//k)
        k += 1
    if int(l) == l:
        s -= int(l)
    return s

def find_friend(n):
    x = sum_of_divisors(n) - n
    if sum_of_divisors(x) - x == n:
        return x
    return None



def e21():
    s = set()
    limit = 10000

    for i in range(2, limit+1):
        x = find_friend(i)
        if x and x != i and x <= limit:
            s.add(x)
            s.add(i)

    print(sum(s))

%time e21()
#31626
#Wall time: 297 ms

e022.py

from urllib.request import urlopen

def getNamePoint(name):
    return sum([ord(c) - 64 for c in list(name)])
"""

여기 5천개 이상의 영문 이름들이 들어있는 46KB짜리 텍스트 파일 names.txt 이 있습니다 (우클릭해서 다운로드 받으세요).
이제 각 이름에 대해서 아래와 같은 방법으로 점수를 매기고자 합니다.

    먼저 모든 이름을 알파벳 순으로 정렬합니다.
    각 이름에 대해서, 그 이름을 이루는 알파벳에 해당하는 숫자(A=1, B=2, ..., Z=26)를 모두 더합니다.
    여기에 이 이름의 순번을 곱합니다.

예를 들어 "COLIN"의 경우, 알파벳에 해당하는 숫자는 3, 15, 12, 9, 14이므로 합이 53, 그리고 정렬했을 때 938번째에 오므로 최종 점수는 938 × 53 = 49714가 됩니다.

names.txt에 들어있는 모든 이름의 점수를 계산해서 더하면 얼마입니까?"""




def e22():
    s = urlopen('http://euler.synap.co.kr/files/names.txt').read().decode('utf-8')
    names = sorted(list(map(lambda x:x.strip('"'), s.split(','))))

    p = 0
    for i, name in enumerate(names):
        p += (i+1) * getNamePoint(name)

    print(p)
    
%time e22()

# 871198282
# Wall time: 72 ms

e023.py

"""

자신을 제외한 약수(진약수)를 모두 더하면 자기 자신이 되는 수를 완전수라고 합니다.
예를 들어 28은 1 + 2 + 4 + 7 + 14 = 28 이므로 완전수입니다.
또, 진약수의 합이 자신보다 작으면 부족수, 자신보다 클 때는 초과수라고 합니다.

12는 1 + 2 + 3 + 4 + 6 = 16 > 12 로서 초과수 중에서는 가장 작습니다.
따라서 초과수 두 개의 합으로 나타낼 수 있는 수 중 가장 작은 수는 24 (= 12 + 12) 입니다.

해석학적인 방법을 사용하면, 28123을 넘는 모든 정수는 두 초과수의 합으로 표현 가능함을 보일 수가 있습니다.
두 초과수의 합으로 나타낼 수 없는 가장 큰 수는 실제로는 이 한계값보다 작지만, 해석학적인 방법으로는 더 이상 이 한계값을 낮출 수 없다고 합니다.

그렇다면, 초과수 두 개의 합으로 나타낼 수 없는 모든 양의 정수의 합은 얼마입니까?"""


def sumOfDivisors(n):
    k = 1
    s = 0
    l = int(n ** 0.5)
    while k <= l:
        if n % k == 0:
            s += k + n // k
        k += 1
    if l*l == n:
        return s - l
    return s

def isOverNum(n):
    return sumOfDivisors(n) > n * 2

overnums = set([x for x in range(12, 28123) if isOverNum(x)])

def test(n):
    for i in overnums:
        if (n - i) in overnums:
            return True
    return False

def main():
    result = []
    for i in range(12, 28123):
        if not test(i):
            result.append(i)
    ans = sum(list(range(1, 12)) + result)
    print(ans)
    
%time main()

4179871
Wall time: 1.76 s

e024.py

"""

어떤 대상을 순서에 따라 배열한 것을 순열이라고 합니다. 예를 들어 3124는 숫자 1, 2, 3, 4로 만들 수 있는 순열 중 하나입니다.

이렇게 만들 수 있는 모든 순열을 숫자나 문자 순으로 늘어놓은 것을 사전식(lexicographic) 순서라고 합니다.
0, 1, 2로 만들 수 있는 사전식 순열은 다음과 같습니다.

    012   021   102   120   201   210

0, 1, 2, 3, 4, 5, 6, 7, 8, 9로 만들 수 있는 사전식 순열에서 1,000,000번째는 무엇입니까?"""


from functools import reduce


def factorial(n):
    if n < 2:
        return 1
    return reduce(lambda x,y:x*y, range(1, n+1))

def perms(n, ls):
    if n == 0:
        return ls
    l = len(ls)
    n = n % factorial(l)
    q, r = divmod(n, factorial(l-1))
    return [ls[q]] + perms(r, ls[:q]+ls[q+1:])

def e24():
    print("".join(perms(999999, list('0123456789'))))
    
%time e24()

#2783915460
#Wall time: 0 ns

e025.py

"""

피보나치 수열은 아래와 같은 점화식으로 정의됩니다.

    Fn = Fn-1 + Fn-2  (단, F1 = 1, F2 = 1).

이에 따라 수열을 12번째 항까지 차례대로 계산하면 다음과 같습니다.

    F1 = 1
    F2 = 1
    F3 = 2
    F4 = 3
    F5 = 5
    F6 = 8
    F7 = 13
    F8 = 21
    F9 = 34
    F10 = 55
    F11 = 89
    F12 = 144 

수열의 값은 F12에서 처음으로 3자리가 됩니다.

피보나치 수열에서 값이 처음으로 1000자리가 되는 것은 몇번째 항입니까?"""


from math import log10

def e25():
    a, b = 0, 1
    n = 1
    while 1:
        if log10(b) >= 999:
            print(n)
            return
        a, b = b, (a+b)
        n += 1

%time e25()

#4782
#Wall time: 6 ms

e026.py

def circ(num):
    d = 1
    divideds = []
    while 1:
        (q, r) = (d // num, d % num)
        #print q, r
        if d in divideds:
            return len(divideds[divideds.index(d):])
        else:
            divideds.append(d)
        d = r * 10


def e26():
    max = 0
    maxLength = 0
    for i in range(1, 1001):
        l = circ(i)
        if maxLength < l:
            max = i
            maxLength = l
    print(max)
    
%time e26()

#983
#Wall time: 495 ms

e027.py

def is_prime(n):
    if n < 2:
        return False
    if n is 2 or n is 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    if n < 9:
        return False
    k = 5
    l = n ** 0.5
    while k <= l:
        if n % k == 0 or n % (k+2) == 0:
            return False
        k += 6
    return True

def make_eqation(a, b):
    def f(x):
        return x*x + a*x + b
    return f

def test(a, b):
    fx = make_eqation(a, b)
    c = 0
    i = 0
    while True:
        d = fx(i)
        if is_prime(d):
            c += 1
            i += 1
        else:
            break
    return i-1

from functools import reduce
def main():
    d = []
    for a in range(-1000,1):
        for b in range(-a * 2, 1001):
            d.append((a, b, test(a, b)))
    result = reduce(lambda x,y : x if x[2] > y[2] else y, d, d[0])
    print(result[0] * result[1])

%time main()
#-59231
#Wall time: 998 ms

e028.py

"""

숫자 1부터 시작해서 우측으로부터 시계방향으로 감아 5×5 행렬을 만들면 아래와 같이 됩니다.

21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

여기서 대각선상의 숫자를 모두 더한 값은 101 입니다.

같은 방식으로 1001×1001 행렬을 만들었을 때, 대각선상의 숫자를 더하면 얼마가 됩니까?"""


"""
1. 4번 시행후 늘어나는 간격이 2씩 커진다.
2. 1001까지 가려면 500바퀴를 돌면 된다
"""
def e028():
    a, s, k = 1, 1, 2

    for _ in range(1, 501):
        for _ in range(4):
            a += k
            s += a
        k += 2

    print(s)
%time e028()

e029.py

"""

2 ≤ a ≤ 5 이고 2 ≤ b ≤ 5인 두 정수 a, b로 만들 수 있는 ab의 모든 조합을 구하면 다음과 같습니다.

    22=4,  23=8,  24=16,  25=32
    32=9,  33=27,  34=81,  35=243
    42=16,  43=64,  44=256,  45=1024
    52=25,  53=125,  54=625,  55=3125

여기서 중복된 것을 빼고 크기 순으로 나열하면 아래와 같은 15개의 숫자가 됩니다.

4,  8,  9,  16,  25,  27,  32,  64,  81,  125,  243,  256,  625,  1024,  3125

그러면, 2 ≤ a ≤ 100 이고 2 ≤ b ≤ 100인 a, b를 가지고 만들 수 있는 ab는 중복을 제외하면 모두 몇 개입니까?"""


def e029():
    a = set()
    for x in range(2, 101):
        for y in range(2, 101):
            a.add(x**y)

    print(len(a))

%time e029()

e030.py

"""

각 자리의 숫자를 4제곱해서 더했을 때 자기 자신이 되는 수는 놀랍게도 단 세 개밖에 없습니다.

    1634 = 14 + 64 + 34 + 44
    8208 = 84 + 24 + 04 + 84
    9474 = 94 + 44 + 74 + 44 

(1 = 14의 경우는 엄밀히 말해 합이 아니므로 제외합니다)

위의 세 숫자를 모두 더하면 1634 + 8208 + 9474 = 19316 입니다.

그렇다면, 각 자리 숫자를 5제곱해서 더했을 때 자기 자신이 되는 수들의 합은 얼마입니까?"""

def transform(num, n):
    return sum((int(x) ** n for x in str(num)))

def e030():
    result = sum((x for x in range(2, 999999+1) if x == transform(x, 5)))
    print(result)
%time e030()

#443839
#Wall time: 7.61 s