Project Euler on Python(3) #007 (071~080)

e071.py

"""

n과 d가 양의 정수이고 n<d인 분수 n/d을 GCD(n, d) = 1일 때 기약 진분수라고 부르기로 합니다.
d ≤ 8 인 기약 진분수들을 커지는 순으로 늘어놓으면 아래와 같습니다.

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

위에서 보듯이 3/7의 바로 앞에는 2/5가 오게 됩니다.

d ≤ 1,000,000 인 기약 진분수들을 커지는 순으로 늘어놓았을 때, 3/7 바로 앞에 오는 수의 분자는 얼마입니까?"""



"""7의 배수가 아닌 분모 N에 대해서 N * 3 / 7 한 몫이 3/7보다 작은
분수의 분자가 된다. 이 때 약분이 일어날 수 있으니, 
약분한 결과가 최대가 되면 OK.
"""

def gcd(a, b):
    a, b = max(a, b), min(a, b)
    if a % b == 0:
        return b
    return gcd(b, a % b)


def p71():
    result = 0
    for y in range(1000000, 8, -1):
        if y % 7 == 0:
            continue
        x = y * 3 // 7
        g = gcd(x, y)
        x = x // g
        result = max(x, result)

    print(result)

%time p71()

e072.py

"""n과 d가 양의 정수이고 n<d인 분수 n/d을 GCD(n, d) = 1일 때 기약 진분수라고 부르기로 합니다.
d ≤ 8 인 기약 진분수들을 커지는 순으로 늘어놓으면 아래와 같고, 개수는 모두 21개입니다.

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

d ≤ 1,000,000 인 경우, 기약 진분수는 모두 몇 개나 있습니까?"""

""" 풀이
    ######################
    분모가 n 인 기약진분수의 개수는 phi(n)개 이다. 
    즉 백만 이하의 n에 대해 모든 phi(n)의 합을 구하는 문제이다. 
"""

from fractions import Fraction
from functools import reduce

# dict의 setdefault를 이용하여 메모아이즈 함수를 간단히 작성할 수 있다. 
def memoize(f):
    c = {}
    def w(a):
        return c.setdefault(a, f(a))
    return w

# phi 함수의 정의는 모든 소인수로부터 n * (1 - 1/p1) * (1 - 1/p2) .. 
# 곱을 사용하게 된다. 
def phi(n):
    s = {1-Fraction(1, p) for p in get_facotrs(n)}
    return reduce(lambda x,y:x*y, s, n).numerator


def get_facotrs(n):
    """ 소인수 집합을 구하는 함수 """
    s = set()
    while n > 1:
        d = divide_helper(n)
        while n % d is 0:
            s.add(d)
            n = n // d
    return s

@memoize
def divide_helper(n):
    if n % 2 is 0:
        return 2
    if n % 3 is 0:
        return 3
    k = 5
    l = n ** 0.5
    while k <= l:
        if n % k == 0:
            return k
        if n % (k+2) == 0:
            return k + 2
        k += 6
    return n

def p72():
    xs = [phi(n) for n in range(2, 1000000 + 1)]
    print(sum(xs))
    
%time p72()
# 303963552391
# Wall time: 4min 15s

"""
    n의 각 소인수 p에 대해서
    phi(n) = n * phi(p1) * phi(p2) * ....
    다음과 같이 동적 프로그래밍으로 구할 수 있다. 
    (동적 프로그래밍으로 계산시, 100만까지 계산하면 그 이하의 모든 값이 계산됨을 이용)
"""

def p72():
    limit = 10**6 + 1
    phi = list(range(limit))
    for p in phi[2:]:
        if phi[p] == p:
            for k in range(p, limit, p):
                phi[k] = phi[k] // p * (p - 1)
    print(sum(phi[2:]))
    
%time p72()
# 303963552391
# Wall time: 2.16 s

e073.py

"""n과 d가 양의 정수이고 n<d인 분수 n/d을 GCD(n, d) = 1일 때 기약 진분수라고 부르기로 합니다.
d ≤ 8 인 기약 진분수들을 커지는 순으로 늘어놓으면 아래와 같습니다.

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

위에서 보듯이, 1/3과 1/2 사이에는 기약 진분수가 세 개 있습니다.

그러면 d ≤ 12,000일 때 1/3과 1/2 사이의 기약 진분수는 몇 개나 있습니까?"""



"""
  단순하게 분자와 분모의 범위를 만들고 서로 소 인 케이스의 경우를 센다.
"""

from fractions import gcd

def p73():
    LIMIT = 12000
    c = 0
    # 분자의 범위
    for x in range(2, LIMIT//2):
        # 분모의 범위는 분자 * 2 ~ 분자*3
        for y in range(x*2+1, min(x*3+1, LIMIT+1)):
            if 2*x < y and gcd(x, y) == 1:
                c += 1
    print (c)
    
%time p73()
# 7295372
# Wall time: 18.9 s

############################

e074.py

"""145는 각 자릿수의 계승값을 모두 더했을 때 자기 자신이 되는 수로 잘 알려져 있습니다.

1! + 4! + 5! = 1 + 24 + 120 = 145

그보다 덜 유명하긴 하지만 169는 위와 같은 방법으로 계산해서 자기 자신으로 되돌아오는 데 가장 많은 단계를 거치는 숫자로, 그런 특성을 가진 숫자는 3개밖에 없다고 합니다.

169 → 363601 → 1454 → 169
871 → 45361 → 871
872 → 45362 → 872

어떤 숫자로 시작해도 결국 위와 같은 반복 루프에 들어간다는 사실은 어렵지 않게 증명이 가능한데, 몇 개 숫자의 예를 들면 다음과 같습니다.

69 → 363600 → 1454 → 169 → 363601 (→ 1454)
78 → 45360 → 871 → 45361 (→ 871)
540 → 145 (→ 145)

69로 시작하면, 반복이 일어나기 전에 다섯 번의 단계를 거친 다음에 루프에 들어갑니다. 1백만 이하의 숫자로 시작하는 경우는 최대 60번의 반복되지 않는 단계가 존재합니다.

1백만 이하의 숫자로 시작했을 때, 반복되지 않는 단계를 정확히 60번 거치는 경우는 모두 몇 번이나 됩니까?"""




def transform(n):
    ''' eg> 169 --> 1! + 6! + 9! 
    문자열로 처리하면 코드가 더 간단해지지만, 속도는 이쪽이 더빠르다.
    '''
    fs = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]

    s = 0
    while n > 0:
        s += fs[n%10]
        n = n // 10
    return s
    
times = [0] * 10000001
def step(n, stack):
    r = transform(n)
    if r == n :
        times[n] = 1
    elif times[r] != 0:
        times[n] = times[r] + 1
    elif r in stack:
        times[n] = 1
    else:
        stack.append(n)
        count, stack = step(r, stack)
        times[n] = count + 1
    if stack:
        stack.pop()
    return (times[n], stack)



def main():
    for i in range(1, 1000001):
        step(i,[])
    print(len(list(filter(lambda x: x==60, times))))

%time main()
# 402
# Wall time: 4.54 s

e075.py

"""

긴 철사를 구부려서 세 변이 정수인 직각삼각형을 만들 때, 그 방법이 한 가지 뿐인 경우는 12cm를 최소로 해서 아래와 같이 여러 개가 있습니다.

12 cm: (3,4,5)
24 cm: (6,8,10)
30 cm: (5,12,13)
36 cm: (9,12,15)
40 cm: (8,15,17)
48 cm: (12,16,20)

반면에 20cm의 경우처럼 세 변이 정수인 직각삼각형을 만들 수 없을 때도 있고, 여러 종류의 직각삼각형을 만들 수 있을 때도 있습니다. 예를 들어 120cm의 철사로는 세 가지의 서로 다른 직각삼각형이 만들어집니다.

120 cm: (30,40,50), (20,48,52), (24,45,51)

그러면 길이가 1,500,000 이하인 철사를 가지고 세 변이 정수인 직각삼각형을 만들 때, 그 길이로는 한 가지 방법으로만 만들 수 있게 되는 경우는 모두 얼마나 됩니까?"""



"""
    둘레의 합이 150만 이하인 원시 피타고라스 수의 집합을 구해놓고
    동적 프로그래밍으로 특정 둘레에서 만들 수 있는 직각삼각형의 수를 모두 구할 수 있다. 
    이를 통해서 직각삼각형이 1개만 만들어지는 둘레를 센다. 
"""


def gcd(a, b):
    a, b = (a, b) if a > b else (b, a)
    if b is 0:
        return 0
    if a % b == 0:
        return b
    return gcd(b, a % b)

limit = 1500000

def get_range():
    """원시피타고라스 수 집합을 구할 m, n의 한계치 계산"""
    for i in range(3, limit):
        if make_pythagorean((i, 1)) is not None and sum(make_pythagorean((i, 1))) > limit:
            return i
        

def make_pythagorean(t):
    """원시 피타고라스 수를 만든다. m > n이고 서로 소 인 두 홀수 m, n에 대해서
    아래 공식을 이용하여 원시 피타고라스 수를 만들 수 있다. 
        a = m * n
        b = (m*m - n*n) // 2
        c = (m*m + n*n) // 2
    """
    m, n = (max(t), min(t))
    if m % 2 == 0 or n % 2 == 0 or m == n:
        return None
    g = gcd(m, n)
    m, n = (m//g, n//g)
    a = m * n
    b = (m*m - n*n) // 2
    c = (m*m + n*n) // 2
    return tuple(sorted((a, b, c)))


def p75():
    r = get_range()
    
    # 원시 피타고라스 집합
    p_pys = set(filter(lambda x:x and sum(x) <= limit,
                        [make_pythagorean((a, b)) \
                         for a in range(1, r, 2) \
                         for b in range(a+2, r, 2)]
                       )
                )
    
    ways = [0] + [0]*limit
    for p in p_pys:
        s = sum(p)
        for i in range(s, limit, s):
            ways[i] += 1
    
    print(sum(1 for x in filter(lambda x: x == 1, ways)))
    
%time p75()
# 161667
# Wall time: 2.16 s

e076.py

"""숫자 5를 자연수의 합으로 나타내는 데는 모두 여섯 가지 방법이 있습니다.

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

그러면 숫자 100을 두 개 이상의 자연수의 합으로 나타내는 방법은 모두 몇 가지나 됩니까?"""


""" 숫자 100을 100보다 작은 종류의 동전으로 구성하는 방법과 동일하며, 
DP로 빨리 푸는 것이 가능하다."""



def get_ways(n):
    ways = [1] + [0] * n
    for i in range(1, n):
        for j in range(i, n + 1):
            ways[j] += ways[j-i]
    return ways[-1]

def p76():
    print(get_ways(100))
    
%time p76()

e077.py

"""

숫자 10을 소수의 합으로 나타내는 방법은 모두 다섯 가지가 있습니다.

7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2

소수의 합으로 나타내는 방법이 5000가지가 넘는 최초의 숫자는 얼마입니까?"""


"""
    흔한 동적 프로그래밍 문제.
    n 보다 작은 소수들 동전으로 n원을 만드는 방법과 같다고 이해하면 되고,
    이 방법이 5000을 넘는 최초의 금액을 찾는다.
"""

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 True
    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 get_ways(n):
    ways = [1] + [0] * n
    for i in [2]+[x for x in range(3, n, 2) if is_prime(x)]:
        for j in range(i, n + 1):
            ways[j] += ways[j-i]
    return ways[-1]


def p77():
    i = 10
    while True:
        b = get_ways(i)
        if b > 5000:
            print(i)
            break
        i += 1

%time p77()

# 71
# Wall time: 6 ms

e078.py

"""
<<<< 고난이도 주의 >>>>
n개의 동전을 여러 더미로 나누는 경우의 수를 p(n)이라고 나타내기로 합니다.
예를 들어 동전 다섯 개는 아래와 같이 일곱 가지 방법으로 나눌 수 있으므로 p(5) = 7이 됩니다.
OOOOO
OOOO   O
OOO   OO
OOO   O   O
OO   OO   O
OO   O   O   O
O   O   O   O   O

p(n)이 1백만으로 나누어 떨어지는 가장 작은 n의 값은 얼마입니까?
"""




"""
    동전을 나누는 경우의 수는 오일러의 분할수에 해당한다. 
    오일러의 분할수는 다음과 같은 식으로 계산되는데,
    
    p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + .....
    
    각 항의 부호는 +, +, -, - 이며
    (n - k) 는 순서대로 1, -1, 2, -2, 3, -3... 에 대해서 5각수를 구한
    값을 사용한다. 
    
    이 공식을 이용해서 아래와 같이 풀 수 있다. 
"""


def getPenta(k):
    """오일러 분할 수 계산을 위한 n - k의 k의 수열"""
    # n: 1, -1, 2, -2, 3, -3 ...
    n = (k // 2 + 1 if k % 2 == 0 else (k // 2)* -1 - 1)
    return n*(3*n - 1) // 2

def p78():
    signs = (1, 1, -1, -1)
    p = [1]
    k = 1
    while True:
        pk = 0 # p(k)의 항의 값이 될 값
        i = 0 # 점화식내의 수열의 인덱스
        penta = getPenta(i)

        while penta <= k:
            pk += p[k - penta] * signs[i%4]
            i += 1
            penta = getPenta(i)

        pk = pk % 1000000 # 100만 자리 이하 숫자는 무시
        if pk == 0:
            print(k)
            return
        p.append(pk)
        k += 1

%time p78()
# 55374
# Wall time: 20.1 s

e079.py

"""

온라인 뱅킹에서 흔히 쓰이는 보안 기법 중에는, 비밀번호에 포함된 숫자를 랜덤하게 세 개 입력하도록 하는 것이 있습니다.
예를 들어 531278이라는 비밀번호에 대해서 2번째, 3번째, 5번째 숫자를 입력하도록 하는 식입니다. 이 때 올바른 입력은 317이 됩니다.

첨부한 텍스트 파일 keylog.txt에는 로그인에 성공한 어떤 사용자의 입력 기록이 50건 담겨져 있습니다. (비밀번호의 길이는 알 수 없습니다)

3개의 숫자는 항상 앞쪽부터 순서대로 요청된다고 할 때, 위의 접속 기록에서 알아낼 수 있는 가장 짧은 길이의 비밀번호는 무엇입니까?"""


"""
    각 숫자에 대해 자신보다 앞에 오는 숫자들을 찾는다. 
    자신보다 앞에 오는 숫자가 1개만 있으면 그것이 두번째 숫자이고, 그 선행 숫자가 첫 숫자이다. 
    그 이후에는 선행숫자의 개수가 적은 순으로 붙이면 끗.
"""


from urllib.request import urlopen

f = urlopen('http://euler.synap.co.kr/files/keylog.txt').read().decode('utf-8')

def p79():
    
    lines = [x.strip() for x in f.split('\n') if x]


    orders = {}

    def process(line):
        a, b, c = [int(x) for x in line]
        orders.setdefault(b, set()).add(a)
        orders.setdefault(c, set()).add(b)
        orders.setdefault(c, set()).add(a)
        
        
    for l in lines:
        process(l)

    xs = sorted(orders.items(), key=lambda x:len(x[1]))
    ks = [str(x[0]) for x in xs]
    print("".join([str(xs[0][1].pop())] + ks))
    
%time p79()
73162890
Wall time: 0ns

e080.py

"""자연수의 제곱근이 정수가 아니라면 무리수가 되고, 이런 경우 소수점 밑으로 반복되는 패턴이 전혀 없는 숫자들이 무한히 전개됩니다.
2의 제곱근은 1.41421356237309504880... 인데, 처음 100개까지의 자릿수를 모두 더하면 475입니다.
1부터 100까지의 자연수 중에서 제곱근이 무리수인 경우에 대해, 처음 100개까지의 자릿수를 더한 값들의 총합은 얼마입니까?"""




"""
  손으로 제곱근을 구하는 방법을 그대로 사용한다.
"""



def get_square_root(n, count=20):
    I = int(n ** 0.5)
    LEFT = 0
    LAST = I
    result = []
    n = (n - (I * I)) * 100
    
    while n > 0:
        LEFT = LEFT * 10 + LAST + LAST
        for i in range(1, 12):
            if n < (LEFT*10 + i) * i:
                LAST = i - 1
                break
        n = (n - (LEFT * 10 + LAST) * LAST) * 100
        result.append(LAST)
        count -= 1
        if count is 0:
            break
    return [I] + result

def p80():
    xs = [get_square_root(n,100)[:100] for n in range(1, 101) if len(get_square_root(n)) > 1]
    print(sum(map(sum, xs)))
    
%time p80()
# 40886
# Wall time: 39 ms

Topological Sort

유사코드

L : 정렬된 원소들이 들어갈 리스트
S : 들어오는 엣지가 없는 종단 노드의 세트
while S is not empty :
    remove a node n from S
    add n to tail of L
    for each node m with an edge e from n to m:
         remove edge e from the graph
         if m has no other incoming edges then:
            insert m to S
if graph has edges then:
    return error
else:
    return L