Project Euler on Python(3) #006 (061~070)

e061.py

"""

삼각수, 사각수, 오각수 같은 다각수들은 아래의 공식으로 만들 수 있습니다.
삼각수 	P3,n = n(n+1)/2 	1, 3, 6, 10, 15, ...
사각수 	P4,n = n2 	1, 4, 9, 16, 25, ...
오각수 	P5,n = n(3n−1)/2 	1, 5, 12, 22, 35, ...
육각수 	P6,n = n(2n−1) 	1, 6, 15, 28, 45, ...
칠각수 	P7,n = n(5n−3)/2 	1, 7, 18, 34, 55, ...
팔각수 	P8,n = n(3n−2) 	1, 8, 21, 40, 65, ...

그런데 4자리 숫자 8128, 2882, 8281 (순서대로) 에는 세 가지의 재미있는 성질이 있습니다.

    각 숫자들은 서로 꼬리를 물고 순환됩니다. 각 숫자의 뒤쪽 두 자리는 다음 숫자의 앞쪽 두 자리가 되는 식입니다.
    각 숫자는 서로 다른 다각수인데, 여기서는 삼각수 (P3,127=8128), 사각수 (P4,91=8281), 오각수 (P5,44=2882)가 대응됩니다.
    이런 성질을 갖는 4자리의 숫자 세 개는 이 숫자들이 유일합니다.

위와 같이 순환되면서 서로 다른 다각수(삼각수 ~ 팔각수)이기도 한 4자리 숫자 여섯 개의 유일한 순서쌍을 찾고, 그 합을 구하세요."""




"""4자리수 N 각수를 모두 구해놓고, 재귀로 찾으면 된다."""

# p61

def get_numbers(family):
    pn = (lambda n: n*(n+1) // 2,
          lambda n: n*n,
          lambda n: n*(3*n - 1) // 2,
          lambda n: n*(2*n -1),
          lambda n: n*(5*n-3) // 2,
          lambda n: n*(3*n-2))
    t = (pn[family-3](x) for x in range(1, 200))
    return {x for x in t if x > 999 and x < 10000}

def p61():
    ps = [get_numbers(f) for f in range(3, 9)]
    def solve(ds, families):
        """ds: 찾은 수, families: 사용한 각수"""

        # 완료조건
        if len(ds) == 6:
            if ds[-1] % 100 == ds[0] // 100:
                return ds
            else:
                return None

        last = None if len(ds) is 0 else ds[-1] % 100

        # 사용할 수 있는 각수
        fs = {n for n in range(3, 9) if n not in families}


        for family in sorted(fs, reverse=True):
            families.add(family)
            # 2차 이하일 때
            if last is not None:
                targets = {n for n in ps[family-3] if n // 100 == last}
            else:
                # 1차일 때 다음 차수 대상은 전체로 시작한다.
                targets = {n for n in ps[family-3]}

            for n in targets:
                result = solve(ds+[n], families)
                if result is not None:
                    return result
            families.remove(family)
        return None


    print(sum(solve([], set())))



%time p61()
# 28684
# Wall time: 1e+03 µs

e062.py

"""세제곱수인 41063625 (=3453) 로 순열을 만들어보면, 그 중에서 56623104 (=3843)와 66430125 (=4053)가 또 세제곱수입니다.
실제 41063625은, 자릿수로 만든 순열 중에서 3개가 세제곱수인 가장 작은 수입니다.

그러면 자릿수로 만든 순열 중에서 5개가 세제곱수인 가장 작은 숫자는 무엇입니까?"""



def p62():
    
    def _find(n):
        cubs = [i**3 for i in range(33,10**n)]
        cache = {}
        for i in cubs:
            t = tuple(sorted(str(i)))
            cache.setdefault(t, set()).add(i)
        result = min((min(x) for x in cache.values() if len(x) == 5))
        return result
                    
    t = 5
    while True:
        r = _find(t)
        if r is None:
            t += 1
        else:
            print(r)
            break


%time p62()
# 127035954683
# Wall time: 114 ms

e063.py

"""다섯 자리 숫자인 16807은 7**5으로 5제곱수입니다. 또, 아홉 자리 숫자인 134217728은 8**9으로 9제곱수입니다.
n자리 숫자이면서 n제곱수도 되는 양의 정수는 모두 몇 개나 있습니까?"""


"""
    N자리수 X가 a^N이라고 할 때 밑인 a의 범위는 2~10 범위에 있다. 
    같은 식으로부터 N <= 1 / (1 - log a) 가 되므로 N : 0~ 1/(1-log(a)) 사이의 정수들을 해당 범위에서 찾으면 된다.
"""

from math import log10 as log

def p63():
    count = 0
    res = []
    for a in range(2,10):
        max_b = int(1 / (1 - log(a)))
        for b in range(0, max_b + 1):
            res.append(a**b)

    print(len(set(res)))
    
%time p63()
# 49
# Wall time: 0 ns

e064.py

"""

모든 제곱근은 아래와 같이 연분수로 나타낼 수 있는데, 이 때 반복되는 부분이 나타납니다.
√N = a0 + 	
1
  	a1 + 	
1
  	  	a2 + 	
1
  	  	  	a3 + ...

예를 들어서 √23을 풀어 보면,

같은 식으로 계속하면 아래와 같은 모양이 됩니다.
√23 = 4 + 	
1
  	1 + 	
1
  	  	3 + 	
1
  	  	  	1 + 	
1
  	  	  	  	8 + ...

이 과정을 상세히 보면 다음과 같습니다.

위에서 보듯이 4라는 정수부 다음에 1, 3, 1, 8 이라는 숫자가 무한히 반복되는데, 이것을 √23 = [4;(1,3,1,8)] 과 같이 표시하기로 합니다.

이런 식으로 해서 무리수인 제곱근들을 연분수로 나타내면 다음과 같이 됩니다.
√2 	= 	[1;(2)], 주기=1
√3 	= 	[1;(1,2)], 주기=2
√5 	= 	[2;(4)], 주기=1
√6 	= 	[2;(2,4)], 주기=2
√7 	= 	[2;(1,1,1,4)], 주기=4
√8 	= 	[2;(1,4)], 주기=2
√10 	= 	[3;(6)], 주기=1
√11 	= 	[3;(3,6)], 주기=2
√12 	= 	[3;(2,6)], 주기=2
√13 	= 	[3;(1,1,1,1,6)], 주기=5

반복 주기가 홀수인 경우는 N ≤ 13 일 때 모두 4번 있음을 볼 수 있습니다.

그러면 N ≤ 10000 일 때 반복 주기가 홀수인 경우는 모두 몇 번이나 있습니까?"""


"""연분수 전개의 점화식 구하는 과정은 https://gist.github.com/sooop/f10cf4558697eec8f3a
를 참고."""


def continued_fraction(n:int) -> [int]:
    NR = int(n **0.5)
    if NR * NR == n:
        return [NR]
    a = NR
    b = -NR
    c = 1
    cache = [(a, b, c)]
    result = [a]
    
    def get_next_fraction(b, c):
        cn = (n - b*b) // c
        an = (NR - b) // cn
        bn = -b - an * cn
        return (an, bn, cn)
    
    while True:
        p = get_next_fraction(b, c)
        if p in cache:
            return result
        cache.append(p)
        a, b, c = p
        result.append(a)
        
def p64():
    xs = [continued_fraction(i) for i in range(2, 10001)]
    print(sum((1 for x in xs if len(x) % 2 == 0)))
    
%time p64()
# 1322
# Wall time: 956 ms

e065.py

"""

제곱근 2는 아래와 같은 연분수의 꼴로 나타낼 수 있습니다.

연분수에서 이렇게 끝없이 반복되는 부분은 √2 = [1;(2)] 처럼 나타낼 수 있는데, 여기서 (2)는 숫자 2가 반복됨을 뜻합니다. 같은 방법으로 √23은 [4;(1,3,1,8)] 이 됩니다.

이 연분수의 부분 합을 구하면, 해당 제곱근의 훌륭한 근사값으로 쓸 수 있습니다. √2의 수렴 과정을 한번 보겠습니다.

이런 식으로 처음 10번에 해당하는 값은 다음과 같이 됩니다.

정말 놀라운 사실은, 가장 중요한 수학 상수 중 하나인 e가 다음과 같은 연분수 꼴로 나타내어진다는 것입니다.

    e = [2; 1,2,1, 1,4,1, 1,6,1 , ... , 1,2k,1, ...]

이 경우 수렴 과정의 처음 10번은 이렇습니다.

여기서 열번째 값의 분자 자릿수를 모두 더하면 1+4+5+7 = 17이 되는 것을 알 수 있습니다.

그러면 e의 100번째 연분수 확장 값의 분자 자릿수를 모두 더하면 얼마가 됩니까?
"""



"""
    e의 정수부들을 모아보면 n = 1, 2, 3, ... 일 때 
    n을 3으로 나눈 나머지가 2이면 ((n / 3) + 1) * 2 이고 그외의 경우에는 1이 된다. 
    연분수 전개를 계산하는 방법은 각 정수부분을 역순으로 하여 역수를 취하고 1을 더하는 과정을 반복한다. 
    
    문제에서는 연분수의 0차 계산을 1번항으로 두고 있으므로 99번까지 계산하면 된다. 
    
    
"""
from fractions import Fraction

def reverse(a):
    x, y = a.numerator, a.denominator
    return Fraction(y, x)

def egen(n):
    while n > 0:
        if n % 3 == 0 or n % 3 == 1:
            yield 1
        else:
            yield ((n // 3) + 1) * 2
        n -= 1

def p65():
    g = egen(99)
    x = Fraction(next(g), 1)
    for i in g:
        x = reverse(x + i)
    x += 2
    print(sum(int(i) for i in str(x.numerator)))

%time p65()
# 272
# Wall time: 9 ms

e067.py

"""
아래와 같은 삼각형의 꼭대기에서 인접한 숫자를 따라 내려가는 경로의 합을 계산해보면, 붉은 색으로 표시한 경우가 3 + 7 + 4 + 9 = 23으로 가장 큽니다.
3
7 4
2 4 6
8 5 9 3
텍스트 파일 triangle.txt (우클릭해서 다운로드)에는 100줄짜리 삼각형 숫자 데이터가 들어 있습니다. 꼭대기에서 바닥에 이르는 경로의 합 중 최대값은 얼마입니까?
참고: 이 문제는 18번 문제와 비슷하지만 훨씬 더 어려운 버전입니다. 이 문제를 풀려고 모든 경로를 계산하는 것은 가능하지 않은데, 경우의 수가 모두 299 이나 되기 때문입니다. 일 초에 1조 (1012)개의 경로를 계산할 수 있다고 해도, 모든 경우의 수를 계산하려면 200억년이 걸립니다. 이 문제를 해결할 수 있는 효율적인 알고리즘을 찾아보시기 바랍니다."""


from urllib.request import urlopen

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

def line2numbers(line):
    return [int(x) for x in line.split(' ') if x]

def p67():
    numbers = list(reversed(list(filter(lambda x:x, map(line2numbers, s.split('\n'))))))
    a = numbers[0]

    for i in range(1, len(numbers)):
        x = map(sum, zip(a, numbers[i]))
        y = map(sum, zip(a[1:], numbers[i]))
        a = list(map(max, zip(x, y)))

    print(a)

    
%time p67()
# [7273]
# Wall time: 6 ms

e068.py

"""아래와 같이 마방진과 유사한 성질을 가진 도형이 있습니다. 1부터 6까지의 숫자가 한번씩만 사용되었고, 선을 따라 합을 구하면 항상 9가 됩니다.

바깥으로 뻗친 가지 중에서 가장 숫자가 낮은 것부터 시작해서 직선들을 시계방향으로 돌아가며 나열하면, 도형의 모양을 숫자로 나타낼 수 있습니다. 위 그림의 예를 들면 4,3,2; 6,2,1; 5,1,3 과 같이 됩니다.

위 도형으로는 네 가지 다른 합계를 가지도록 배열할 수 있는데, 다음과 같은 여덟 개의 풀이가 존재합니다.
합계 	풀이
9 	4,2,3; 5,3,1; 6,1,2
9 	4,3,2; 6,2,1; 5,1,3
10 	2,3,5; 4,5,1; 6,1,3
10 	2,5,3; 6,3,1; 4,1,5
11 	1,4,6; 3,6,2; 5,2,4
11 	1,6,4; 5,4,2; 3,2,6
12 	1,5,6; 2,6,4; 3,4,5
12 	1,6,5; 3,5,4; 2,4,6

하나의 풀이에 대해서 각 숫자를 모두 이어붙이면 9자리의 숫자를 만들 수 있고, 그 중에서 가장 큰 것은 432621513이 됩니다.

이제 아래와 같은 도형에다 마방진의 성질을 가지도록 1부터 10까지의 숫자를 채우고, 같은 방식으로 풀이 숫자를 이어붙이면 16자리 또는 17자리의 숫자가 만들어집니다. 이 때, 16자리 숫자 중에서 가장 큰 것은 무엇입니까?"""



"""오각형을 그렸을 때 바깥으로 삐져나온 것만 모은 원과 안쪽 오각형의 꼭지점을 이은 원 두 개의 원이 있다고 했을 때, 
바깥원의 꼭지점을 A B C D E 라 하고 안쪽 꼭지점을 F G H I J 라 했을 때 각 라인의 합은

    ((A+B+C+D+E) + 2 * (F+G+H+I+J)) / 5 

또 문제의 조건에서 10이 안쪽 원에 들어가면 두 번 사용돼서 17자리가 되니 패스. 
그리고 만들어진 오방진의 가장 낮은 가지부터 둘러서 이은 가장 큰 값을 구해야 하니 
바깥쪽에 큰 수들 (6, 7, 8, 9, 10)을 먼저 배치한다고 가정해보면 각변의 합은

    ((6+7+8+9+10) + 2 *(1+2+3+4+5)) / 5 = 14 

실제로 둘러서 그려보면 각 변이 다음과 같은 걸 찾을 수 있는데요,

10 - 3 - 1
9 - 1 - 4
8 - 4 - 2
7 - 2- 5
6 - 5- 3
"""


from itertools import permutations as perm

def findSolution(numbers=None):
    # 각 변을 따라 꺼낼 숫자의 위치
    edge_indices = ((0, 1, 2), (3, 2, 4), (5, 4, 6),
                    (7, 6, 8), (9, 8, 1))
    edge_sums = {}
    s = 0
    for e in edge_indices:
        edge = [numbers[x] for x in e]
        s = sum(edge)
        edge_sums[s] = edge_sums.get(s,[]) + [edge]
    if len(edge_sums.keys()) > 1:
        return None
    min_start_index = 0
    edges = edge_sums[s]
    for x in range(len(edges)):
        if edges[x] < edges[min_start_index]:
            min_start_index = x
    edges = edges[min_start_index:] + edges[:min_start_index]
    return int("".join(str(x) for x in sum(edges,[])))


def p68():
    result = []
    for p in perm(range(1, 10)):
        s = findSolution([10]+list(p))
        if s is not None:
            result.append(s)

    print(max(result))
    
%time p68()
# 6531031914842725
# Wall time: 3.73 s

e069.py

"""오일러의 피(phi)함수 φ(n)은 n보다 작거나 같으면서 n과 서로 소인 숫자의 개수를 나타냅니다. 예를 들어, 9보다 작거나 같으면서 9와 서로 소인 것은 1, 2, 4, 5, 7, 8이므로 φ(9)=6이 됩니다.
n 	서로 소인 수 	φ(n) 	n/φ(n)
2 	1 	1 	2
3 	1, 2 	2 	1.5
4 	1, 3 	2 	2
5 	1, 2, 3, 4 	4 	1.25
6 	1, 5 	2 	3
7 	1, 2, 3, 4, 5, 6 	6 	1.1666...
8 	1, 3, 5, 7 	4 	2
9 	1, 2, 4, 5, 7, 8 	6 	1.5
10 	1, 3, 7, 9 	4 	2.5

위에서 보듯이 n ≤ 10인 경우 n/φ(n)의 값은 n=6일때 최대가 됩니다.

n이 1,000,000 이하의 자연수일 때, n/φ(n)는 언제 최대가 됩니까?"""

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

"""
    φ(n) = n - {n의 약수의 개수} 이므로
    n / φ(n)이 커지려면 n 이 커지고 n 의 약수의 개수가 많아야 한다. 
    2 * 2 * 2 > 2 * 3 이므로 이 경우 소인수가 거듭제곱 없이 많이 있는 것이 유리하다. 
    이런 조건을 만족하는 수는 2부터 연속된 소수의 곱이므로, 
    2부터 연속된 소수를 곱해 나간다.
"""


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

from functools import reduce

primes = [x for x in range(20) if is_prime(x)]
#print(reduce(lambda x, y: x*y, primes, 1))
#9,699,690 이므로 이정도면 충분합니다.

def p69():
    x = 10**6
    maxn = 1
    for p in primes:
        if maxn * p > x:
            print(maxn)
            return
        maxn *= p

%time p69()
# 510510
# Wall time: 0 ns

e070.py

"""
오일러 피(phi) 함수 φ(n)은 n보다 작거나 같은 자연수 중 n과 서로 소인 숫자의 개수를 나타냅니다. 예를 들어 9 이하에서 9와 서로 소인 자연수는 1, 2, 4, 5, 7, 8이므로 φ(9)=6입니다.
또, 1은 어떤 자연수와도 서로 소이므로 φ(1)=1입니다.

φ(87109)의 값은 79180인데, 흥미롭게도 79180은 87109로 만들 수 있는 순열 중 하나입니다.

1 < n < 107 이고 φ(n)이 n의 순열이 되는 수 중에서, n/φ(n)이 최소인 n은 얼마입니까? """



#70
"""
    φ(n)은 n 보다 작거나 같은 자연수 중 n과 서로소인 수의 개수를 나타낸다.  
    따라서 n의 약수의 개수가 많으면 많을 수록 이 값은 작아질 수 있다. 
    
    반대로 n/φ(n)는 n의 약수가 개수가 많으면 작아지고 적으면 커진다. 
    따라서 n이 완전제곱수이거나, 두 소수 p, q 의 곱인 경우가 매우 유리한데, 
    특히 두 소수 p, q의 곱인 경우 φ(n) = (p-1)(q-1)로 계산되는 특이한 성질이 있다. 
    
    그리고 이 값이 가까워지려면 p, q는 거의 비슷한 값 (즉 완전제곱수에 가까운 값)이어야
    한다. 
    
    따라서 천만의 제곱근이 언저리에서 두 소수를 찾아 (p-1)(q-1)이 최대가 되는 범위를 구해보자. 
"""

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 is 0:
        return False
    if n < 9:
        return True
    k = 5
    l = n ** 0.5
    while k <= l:
        if n % k is 0 or n % (k+2) is 0:
            return False
        k += 6
    return True

def p70():
    a = int(10**3.5)
    r = a
    xs = [x for x in range(a-r, a+r+1) if is_prime(x)]
    ys = []
    for p in xs:
        for q in xs:
            phi = (p-1)*(q-1)
            n = p * q
            if n < 10**7 and sorted(str(n)) == sorted(str(phi)):
                ys.append((n, phi))
                
    print(min(ys, key=lambda x:x[0]/x[1]))
    
%time p70()
# (8319823, 8313928)
# Wall time: 1.76 s