sooop/e051.py

## e051.py
"""두 자리 숫자 *3의 첫번째 자리를 여러가지로 바꿨을 때 가능한 아홉 가지의 결과 중에서 13, 23, 43, 53, 73, 83의 여섯 개는 소수입니다.

56**3 의 3번째와 4번째 자리를 동일한 숫자로 바꿔서 만들어지는 10개의 다섯자리 숫자 중에서는 아래에서 보듯이 7개가 소수가 되며, 이것은 이런 식으로 7개의 소수가 만들어지는 첫번째 경우입니다. 이 소수 집단의 첫번째 수인 56003은 이런 성질을 갖는 가장 작은 소수입니다.

    56003, 56113, 56333, 56443, 56663, 56773, 56993

위의 예처럼 원래의 일부를 동일한 숫자로 치환했을 때 8개의 소수 집단이 만들어지는 경우를 찾고, 그 집단에 속한 가장 작은 소수를 구하세요.
치환하는 자리는 인접하지 않아도 되고, 가장 앞부분을 치환하는 경우 거기에 0은 올 수 없습니다."""


""" 6자리 소수를 모두 구한다음, 이 중 같은 숫자가 3개 있는 소수를 추려내고,
이 소수들에 대해서 반복되는 숫자를 치환하여 8개 소수가 나오는지 찾는다. """


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

@memoize
def is_prime(n):
    if n < 2:
        return False
    if n is 2 or n is 3:
        return True
    if n % 2 == 0 and 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


# 같은 숫자가 3개 반복되는 수를 찾는다.
def tnumber(n):
    s = str(n)
    ds = [(i, s.count(i)) for i in '0123456789']
    r = [x for x, y in ds if y ==3]
    if r:
        return r[0]
    return None

# 같은 숫자를 치환하여 소수 8개가 나올 수 있는지 검사
# 소수검사는 캐시된 값을 쓰므로 매우 빠르게 처리될 수 있다.
def test(n, h):
    s = str(n)
    ds = "123456789" if s[0] == h else "0123456789"
    result = [int(s.replace(h, d)) for d in ds]
    return len(list((filter(is_prime, result)))) == 8


def p51():
    # 6자리 소수를 모두 찾는다.
    primes = [x for x in range(100000, 1000000) if is_prime(x)]
    for p in primes:
        h = tnumber(p)
        if h is not None and test(p, h):
            print(p)
            return

%time p51()
# 121313
# Wall time: 6.98 s

## e052.py


"""
125874를 2배 하면 251748이 되는데, 이 둘은 같은 숫자로 이루어져 있고 순서만 다릅니다.
2배, 3배, 4배, 5배, 6배의 결과도 같은 숫자로 이루어지는 가장 작은 수는 무엇입니까?"""


"""순열인 두 수의 차이는 항상 9의 배수. 따라서 찾아야 하는 수도 9의 배수이며 최소 6자리이다."""


def check(n):
    for i in range(2, 7):
        if sorted(str(n * i)) != sorted(str(n)):
            return False
    return True

def p52():
    for i in range(99999, 1000000//6, 9):
        if check(i):
            print(i)
            return

%time p52()
# 142857
# Wall time: 28 ms

## e053.py
from functools import reduce
"""


1,2,3,4,5 다섯 숫자 중에서 세 개를 고르는 것에는 다음과 같은 10가지 경우가 있습니다.

123, 124, 125, 134, 135, 145, 234, 235, 245, 345

조합론이라는 분야에서는 이것을 5C3 = 10 이라고 표시하며, 일반적인 식은 아래와 같습니다.
nCr =
n!
r!(n−r)!
	,   단 r ≤ n 이고, n! = n×(n−1)×...×3×2×1 이며 0! = 1.

이 값은 n = 23 에 이르러서야 23C10 = 1144066 으로 처음 1백만을 넘게 됩니다.

1 ≤ n ≤ 100 일때 nCr의 값이 1백만을 넘는 경우는 모두 몇 번입니까? (단, 중복된 값은 각각 계산합니다)
"""

""" 그냥 공식대로 계산해서 카운트"""

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

def ncr(n, r):
    return factorial(n) // (factorial(r) * factorial(n-r))

def p53():
    n = [ncr(x, y) for x in range(1, 101) for y in range(1, x+1)]
    return sum((1 for x in n if x > 1000000))

%time p53()
# Wall time: 166 ms
# 4075

## e054.py
"""

포커라는 카드게임은 다섯 장으로 된 패의 높고 낮음에 따라 승부를 냅니다. (포커 규칙을 이미 아는 분이라면 규칙 설명 부분은 건너뛰셔도 좋습니다)

    카드 한 장은 아래와 같은 순서대로 값이 높아집니다.

        2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A

    다섯 장으로 이루어진 패의 계급(세칭 "족보")은, 낮은 것부터 높은 순서로 아래와 같습니다.

        High Card : 가장 높은 카드의 값으로 비교.
        One Pair : 한 쌍이 같은 카드.
        Two Pairs : 서로 다른 두 쌍이 같은 카드.
        Three of a Kind : 세 장이 같은 카드.
        Straight : 모든 카드가 연속된 숫자.
        Flush : 모든 카드의 무늬가 같음.
        Full House : 세 장이 같고, 또 한 쌍이 같음 (Three of a Kind + One Pair).
        Four of a Kind : 네 장이 같은 카드.
        Straight Flush : 모든 카드가 연속된 숫자이면서 무늬도 같음.
        Royal Flush : 10, J, Q, K, A가 무늬도 같음.

    두 사람의 패가 같은 종류의 계급이라면, 계급을 구성하는 카드 중 높은 쪽을 쥔 사람이 이깁니다. 예를 들면 8 원페어는 5 원페어를 이깁니다.
    계급을 이루는 카드 숫자까지 같으면 (예: 둘 다 Q 원페어), 다른 카드를 높은 순서대로 비교해서 승부를 정합니다.

텍스트파일 poker.txt 에는 두 선수가 벌인 1,000회의 승부가 저장되어 있습니다. (우클릭해서 다운로드 받으세요)
한 줄에는 10장의 카드가 공백으로 분리되어 들어있는데, 앞의 다섯 장은 1번 선수 것이고 뒤의 다섯 장은 2번 선수의 패입니다. 잘못되거나 중복된 데이터는 없으며, 무승부도 없습니다.

카드 숫자는 2, 3, ... , 9, T, J, Q, K, A 로 (숫자 10은 T로 표시),
무늬는 C (Club - ♣), D (Diamond - ♦), H (Heart - ♥), S (Spade - ♠) 로 표시되어 있습니다.
예를 들면 3C 3D 3S 9S 9D 의 경우 3 풀하우스가 됩니다.

이 데이터를 분석하고, 1번 선수가 이긴 횟수를 구하세요."""


"""
  카드와 덱을 클래스로 구현하고
  덱에서 카드들의 조합으로 점수를 평가하는 evaluate 메소드를 구현했다.
  두 덱에서 조합과 카드 번호로 승패를 가른다.
"""

card_numbers = tuple("23456789TJQKA")
card_kinds = tuple("CDHS")

class Card:
    def __init__(self, c):
        self.number = c[0]
        self.kind = c[1]

    @property
    def priority(self):
        return card_numbers.index(self.number)

    def __repr__(self):
        return self.number + self.kind


class Deck:
    def __init__(self, cards):
        self.cards = cards
        self.cards.sort(key=lambda x:x.priority)

    def groups_number(self):
        val = {}
        for c in self.cards:
            val.setdefault(c.number, []).append(c)
        result = sorted(val.values(), key=lambda x:len(x), reverse=True)
        return result

    def groups_kind(self):
        val = {}
        for c in self.cards:
            val.setdefault(c.kind, []).append(c)
        result = [sorted(x, key=lambda x:x.priority) for x in val.values()]
        return sorted(result, key=lambda x:len(x), reverse=True)

    @property
    def numbers(self):
        return "".join([c.number for c in self.cards])

    def is_Royal_Flush(self):
        if len(self.groups_kind()) == 1 and \
            self.numbers == "TJQKA":
                return True
        return False

    def is_Straight_Flush(self):
        if len(self.groups_kind()) == 1:
            if self.numbers in "".join(card_numbers) * 2:
                return self.cards[-1].priority
        return None

    def is_Four_Kind(self):
        test = [x for x in self.groups_number() if len(x) == 4]
        if test:
            return test[0][-1].priority
        return None


    def is_Full_House(self):
        if len(self.groups_number()) == 2:
            return self.groups_number()[0][-1].priority
        return None

    def is_Flush(self):
        if len(self.groups_kind()) == 1:
            return self.groups_kind()[0][-1].priority
        return None

    def is_Straight(self):
        if self.numbers in "".join(card_numbers) * 2:
            return self.cards[-1].priority

    def is_Three_Kind(self):
        test = [x for x in self.groups_number() if len(x) == 3]
        if test:
            return test[0][-1].priority
        return None

    def is_Two_Pairs(self):
        test = [x for x in self.groups_number() if len(x) == 2]
        if len(test) == 2:
            return max([x[1].priority for x in test])
        return None

    def is_One_Pair(self):
        test = [x for x in self.groups_number() if len(x) == 2]
        if len(test) == 1:
            return test[0][-1].priority
        return None

    def high_card(self):
        return self.cards[-1].priority


    def __repr__(self):
        return str(self.cards)

    def evaluate(self):
        level = ("RF", "SF", "FK", "FH", "FL", "ST", "TK", "TP", "OP", "HC")
        vs = {
            "RF": self.is_Royal_Flush,
            "SF": self.is_Straight_Flush,
            "FK": self.is_Four_Kind,
            "FH": self.is_Full_House,
            "FL": self.is_Flush,
            "ST": self.is_Straight,
            "TK": self.is_Three_Kind,
            "TP": self.is_Two_Pairs,
            "OP": self.is_One_Pair,
            "HC": self.high_card
        }

        for l in level:
            r = vs[l]()
            if r:
                return (l, r, self.high_card())

def build_deck(s):
    cards = list(map(Card, s.split(" ")))
    return Deck(cards)


def duel(d1, d2):
    level = dict(zip(("RF", "SF", "FK", "FH", "FL", "ST", "TK", "TP", "OP", "HC"), range(10, 0, -1)))
    l1, e1, c1 = d1.evaluate()
    l2, e2, c2 = d2.evaluate()
    if level[l1] > level[l2]:
        return 1
    if level[l1] == level[l2]:
        if e1 > e2:
            return 1
        elif e1 == e2:
            if c1 > c2:
                return 1
    return 0


def process(line):
    if line.strip(" ") == "": #빈줄때문에 에러가 난다;;;
        return 0
    cards = list(map(Card, line.split(" ")))
    d1 = Deck(cards[:5])
    d2 = Deck(cards[5:])
    return duel(d1, d2)

from urllib.request import urlopen

def p54():
    s = 0
    f = urlopen('http://euler.synap.co.kr/files/poker.txt').read().decode('utf-8').split('\n')
    for line in f:
        s += process(line.strip(" "))
    print(s)

%time p54()
# 376
# Wall time: 310 ms

## e055.py
"""

47이란 숫자를 골라서 뒤집은 다음 다시 원래 수에 더하면, 47 + 74 = 121 과 같이 대칭수(palindrome)가 됩니다.
물론 모든 숫자가 이토록 쉽게 대칭수를 만들어내지는 않습니다. 예를 들어 349의 경우,

349 + 943 = 1292
1292 + 2921 = 4213
4213 + 3124 = 7337

위에서 보는 것처럼 3번의 반복과정을 거쳐야 대칭수가 됩니다.

196과 같은 몇몇 숫자들은 이와 같은 과정을 아무리 반복해도 대칭수가 되지 않을 것이라고 추측되는데, 이런 수를 라이크렐 수 (Lychrel number) 라고 부릅니다. 아직 증명되지는 않았지만, 문제 풀이를 위해서 일단 라이크렐 수가 존재한다고 가정을 하겠습니다.

또한 1만 이하의 숫자들은, 50번 미만의 반복으로 대칭수가 되든지 라이크렐 수이든지 둘 중 하나라고 합니다.
1만을 넘어서면 10677에 이르렀을 때 비로소 53번의 반복으로 4668731596684224866951378664 라는 28자리의 대칭수가 만들어집니다.

그러면 1만 이하에는 몇 개의 라이크렐 수가 존재합니까?"""


def is_palindrome(n):
    s = str(n)
    return s == s[::-1]

def reversed_number(n):
    return int(str(n)[::-1])

def check(n):
    for _ in range(50):
        n = n + reversed_number(n)
        if is_palindrome(n):
            return False
    return True

def p55():
    print(len([x for x in range(1, 10001) if check(x)]))

%time p55()
# 249
# Wall time: 110 ms

## e056.py

"""
구골(googol)은 10100을 일컫는 말로, 1 뒤에 0이 백 개나 붙는 어마어마한 수입니다.
100100은 1 뒤에 0이 2백 개가 붙으니 상상을 초월할만큼 크다 하겠습니다.
하지만 이 숫자들이 얼마나 크건간에, 각 자릿수를 모두 합하면 둘 다 겨우 1밖에 되지 않습니다.

a, b < 100 인 자연수 ab 에 대해서, 자릿수의 합이 최대인 경우 그 값은 얼마입니까?
"""

"""
각자리 수의 합을 구해서 최대치를 뽑으면 끝
"""

def calc(s):
    return sum([int(c) for c in s])

def p56():
    xs = [calc(str(a**b)) for a in range(1, 100) for b in range(1, 100)]
    print(max(xs))

%time p56()
# 972
# Wall time: 286 ms

## e057.py
"""

제곱근 2는 다음과 같은 연분수의 형태로 나타낼 수 있습니다.

√ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...

위 식을 처음부터 한 단계씩 확장해 보면 아래와 같습니다.

    1 + 1/2 = 3/2 = 1.5
    1 + 1/(2 + 1/2) = 7/5 = 1.4
    1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...
    1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...

그 다음은 99/70, 239/169, 577/408 로 확장이 되다가, 여덟번째인 1393/985 에 이르면 처음으로 분자의 자릿수가 분모의 자릿수를 넘어섭니다.

처음부터 1천번째 단계까지 확장하는 중에, 분자의 자릿수가 분모보다 많아지는 경우는 몇 번이나 됩니까?"""


"""
계산의 편의를 위해서 클래스를 따로 만들었는데,
유심히 살펴보면 규칙이 있고, 이 규칙만으로 좀 더 간단한 코드도 만들 수 있을 듯 하다.
"""

from math import log10

# 분수꼴을 사용하는 표준 라이브러리 모듈도 있지만, 별도로 구현해본다.

class Rational(object):
    def __init__(self, q, d, integer=0):
        # q/r
        g = self.gcd(q, d)
        _q = q//g
        _d = d//g
        self.q = _q + _d * integer # 분자
        self.d = _d # 분모

    def gcd(self, a, b):
        if a*b == 0:
            return 1
        (_max, _min) = (a, b) if a > b else (b, a)
        if _max % _min == 0:
            return _min
        else:
            return self.gcd(_min, _max%_min)

    def abbrev(self):
      """약분된 (분자, 분모)의 쌍을 리턴한다."""
        return (self.q, self.d)


    def description(self, include_integer=True):
      """분자 / 분모"""의 꼴로 출력한다.
        a = self.abbrev()
        return "%d/%d" % (a[0] + a[1]*self.integer, a[1])


    def reverse(self):
      """역수를 만듬"""
        self.q, self.d = self.d, self.q


    def addInteger(self, number):
      """정수를 더해줌"""
        self.q = self.q + self.d * number


class ChainRational(Rational):
  """연분수꼴을 만들어 나갈 수 있는 분수 클래스"""

    def __init__(self, q, d, integer, chains):
        super(ChainRational, self).__init__(q, d, integer)
        self.integer = integer
        self.chains = chains

    def getApx(self, n=None):
        self.integer = self.q // self.d
        self.q = 0
        self.d = 1
        n = len(self.chains) if n is None else n
        for i in range(n+1, 1, -1):
            idx = (i-1) % len(self.chains)
            m = self.chains[idx]
            self.addInteger(m)
            self.reverse()
        self.addInteger(self.integer)
        return self.abbrev()


def p57():
    a = ChainRational(1, 2, 1, (2,2,))
    c = 0
    for i in range(1, 1000):
        q, d = a.getApx(i)
        if int(log10(q)) > int(log10(d)):
            c += 1
    print(c)

%time p57()
# 153
# Wall time: 735 ms

## e058.py
"""자를 1부터 시작해서 하나씩 늘려가며 아래와 같이 시계반대방향으로 감아가면 한 변의 크기가 7인 정사각형 소용돌이가 만들어집니다.

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

우하단 대각선쪽으로 홀수 제곱수(9, 25, 49)들이 늘어서 있는 것이 눈에 띕니다만, 더 흥미로운 사실은 양 대각선상에 놓인 13개의 숫자 중 8개가 소수라는 것입니다. 그 비율은 대략 8/13 ≈ 62% 정도가 됩니다.

이런 식으로 계속 소용돌이를 만들어갈 때, 양 대각선상의 소수 비율이 처음으로 10% 미만이 되는 것은 언제입니까? 정사각형 한 변의 크기로 답하세요.
"""


"""
격자문제는

1. 1부터 시작
2. 2(변의 길이)씩 증가하고 네 번 돌면 한 바퀴
3. 한바퀴돌고나면 다시 변의 길이가 2씩 증가

이런 순환을 거치며, 증가값+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 == 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 p58():
    k = 1
    e = 2
    ncount = 1
    pcount = 0

    while True:
        for _ in range(4):
            k += e
            if is_prime(k):
                pcount += 1
            ncount += 1

        if pcount * 10 < ncount:
            print(e+1)
            break
        e += 2


%time p58()
# 26241
# Wall time: 10.5 s

## e059.py
"""
컴퓨터상의 모든 문자들은 유일한 코드값에 대응되는데, 보통 ASCII 표준이 널리 쓰입니다.
예를 들면 대문자 A는 65, 별표(*)는 42, 소문자 k는 107라는 값을 가집니다.
현대적인 암호화 기법 중에, 텍스트 파일의 내용을 ASCII 코드로 바꾸고
각 바이트를 비밀키의 값으로 XOR 시키는 것이 있습니다.
이 방법의 장점은 암호화와 복호화에 동일한 키를 사용할 수 있다는 것입니다.
예를 들어 65 XOR 42 = 107 이고, 107 XOR 42 = 65 가 됩니다.

암호문을 절대 깰 수 없도록 하려면, 암호화할 문장의 길이와 같은 무작위의 비밀키를 만들면 됩니다.
암호문과 비밀키는 따로따로 보관해둬야 하고, 그 반쪽짜리 정보 두 개를 함께 확보하지 않는 한 해독은 불가능합니다.
하지만 이 방법은 대부분의 경우 실용적이지 못하므로,
원문보다 짧은 비밀키를 사용하게 됩니다.
이런 경우 비밀키는 전체 메시지에 대해서 반복적으로 돌아가며 적용됩니다.
이 때 키의 길이는 보안상 충분할 정도로 길어야 하지만
또한 쉽게 기억할 수 있을 정도로 짧아야 한다는 미묘한 균형이 요구됩니다.

이번 문제를 위해서 준비된 암호화 키는 단 3개의 영어 소문자이고,
cipher1.txt 파일에 암호화된 ASCII 코드값이 들어있습니다.
원래의 메시지는 평범한 영어 문장임을 힌트로 삼아서 암호문을 해독하고,
원문에 포함된 모든 ASCII 코드 값의 총합을 구하세요."""

"""
일반적인 영어문장에서 가장 많이 나오는 글자는? "e"인데, 실제로는 공백의 가장 많이 나온다.
암호화된 코드 중에서 가장 많이 나오는 값 3개를 공백문자의 코드값으로 XOR해보면 키가 나올 확률이 크다.

이 키를 이용해서 복호화한다음, 단어중에서 가장 자주 쓰이는 "the"가 2번 이상 나오는 후보를 걸러내면
답을 구할 수 있다.
"""

from itertools import cycle, combinations_with_replacement, product
from urllib.request import urlopen


data = urlopen('http://euler.synap.co.kr/files/cipher1.txt').read().decode('utf-8')
codes = [int(x) for x in data.split(',')]

def decode(ciphers, key):
    return "".join([chr(x^y) for x, y in zip(ciphers, cycle([ord(c) for c in key]))])


def guess_key_from_spaces():
    m = {}
    for c in codes:
        m[c] = m.setdefault(c, 0) + 1

    fc = sorted(m.items(), key=lambda x:x[1], reverse=True)[:3]
    return [chr(x^ord(' ')) for x, _ in fc]


def p59():
    msg = [decode(codes, x) for x in product(guess_key_from_spaces(), repeat=3) if decode(codes, x).count('the') > 1]
    print(sum((ord(x) for x in msg[0])))

%time p59()
# 107359
# Wall time: 16 ms

## e060.py
"""

네 개의 소수 3, 7, 109, 673은 상당히 특이한 성질이 있습니다. 넷 중에 아무것이나 두 개를 골라서 어떤 쪽으로 이어붙이던지 그 결과도 소수가 됩니다. 예를 들어 7과 109를 고르면 7109와 1097 또한 소수입니다.
3, 7, 109, 673는 이런 성질을 가진 네 소수 중에서 그 합이 792로 가장 작습니다,

다섯 소수 중에 어떤 두 개를 골라 이어붙여도 소수가 되는 수들을 찾아서, 그 합의 최소값을 구하세요."""


def is_prime(n):
    if n < 2:
        return False
    if n is 2 or n is 3:
        return True
    if n % 2 is 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 == 0 or n % (k+2) == 0:
            return False
        k += 6
    return True

"""
    0. 특정한 범위 내의 소수 집합을 만든다.
    1. 가장 작은 수로 부터 시작하여 한 원소 n 을 정하고 n을 앞뒤로 붙여 소수가 되는 수로 구성된 부분집합을 구한다.
    2. 다시 부분집합에 대해 가장 작은 원소 m 에 대해서 같은 방법으로 부분집합을 구한다.
    3. 목표한 만큼(5개)의 수를 뽑아낼 수 없으면 이전 레벨로 돌아간다.

    이 과정을 재귀적으로 처리한다.
"""


def p60():


    def test(a, b):
        n = int(str(a) + str(b))
        m = int(str(b) + str(a))
        return is_prime(n) and is_prime(m)

    def process(xs, depth=1):
        if depth > hence:
            return xs

        for x in sorted(xs):
            ys = {i for i in xs if test(i, x)}
            if len(ys) < hence - depth:
                continue
            result = process(ys, depth=depth+1)
            if result is not None:
                result.add(x)
                return result
        else:
            return None

    limit = 10000
    hence = 5
    primes = set((x for x in range(3, limit, 2) if is_prime(x)))

    print(process(primes))


%time p60()
# 26033
# Wall time: 5.98 s
	"""두 자리 숫자 *3의 첫번째 자리를 여러가지로 바꿨을 때 가능한 아홉 가지의 결과 중에서 13, 23, 43, 53, 73, 83의 여섯 개는 소수입니다.

	56**3 의 3번째와 4번째 자리를 동일한 숫자로 바꿔서 만들어지는 10개의 다섯자리 숫자 중에서는 아래에서 보듯이 7개가 소수가 되며, 이것은 이런 식으로 7개의 소수가 만들어지는 첫번째 경우입니다. 이 소수 집단의 첫번째 수인 56003은 이런 성질을 갖는 가장 작은 소수입니다.

	56003, 56113, 56333, 56443, 56663, 56773, 56993

	위의 예처럼 원래의 일부를 동일한 숫자로 치환했을 때 8개의 소수 집단이 만들어지는 경우를 찾고, 그 집단에 속한 가장 작은 소수를 구하세요.
	치환하는 자리는 인접하지 않아도 되고, 가장 앞부분을 치환하는 경우 거기에 0은 올 수 없습니다."""



	""" 6자리 소수를 모두 구한다음, 이 중 같은 숫자가 3개 있는 소수를 추려내고,
	이 소수들에 대해서 반복되는 숫자를 치환하여 8개 소수가 나오는지 찾는다. """


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

	@memoize
	def is_prime(n):
	if n < 2:
	return False
	if n is 2 or n is 3:
	return True
	if n % 2 == 0 and 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



	# 같은 숫자가 3개 반복되는 수를 찾는다.
	def tnumber(n):
	s = str(n)
	ds = [(i, s.count(i)) for i in '0123456789']
	r = [x for x, y in ds if y ==3]
	if r:
	return r[0]
	return None

	# 같은 숫자를 치환하여 소수 8개가 나올 수 있는지 검사
	# 소수검사는 캐시된 값을 쓰므로 매우 빠르게 처리될 수 있다.
	def test(n, h):
	s = str(n)
	ds = "123456789" if s[0] == h else "0123456789"
	result = [int(s.replace(h, d)) for d in ds]
	return len(list((filter(is_prime, result)))) == 8


	def p51():
	# 6자리 소수를 모두 찾는다.
	primes = [x for x in range(100000, 1000000) if is_prime(x)]
	for p in primes:
	h = tnumber(p)
	if h is not None and test(p, h):
	print(p)
	return

	%time p51()
	# 121313
	# Wall time: 6.98 s


	"""
	125874를 2배 하면 251748이 되는데, 이 둘은 같은 숫자로 이루어져 있고 순서만 다릅니다.
	2배, 3배, 4배, 5배, 6배의 결과도 같은 숫자로 이루어지는 가장 작은 수는 무엇입니까?"""



	"""순열인 두 수의 차이는 항상 9의 배수. 따라서 찾아야 하는 수도 9의 배수이며 최소 6자리이다."""



	def check(n):
	for i in range(2, 7):
	if sorted(str(n * i)) != sorted(str(n)):
	return False
	return True

	def p52():
	for i in range(99999, 1000000//6, 9):
	if check(i):
	print(i)
	return

	%time p52()
	# 142857
	# Wall time: 28 ms
	from functools import reduce
	"""


	1,2,3,4,5 다섯 숫자 중에서 세 개를 고르는 것에는 다음과 같은 10가지 경우가 있습니다.

	123, 124, 125, 134, 135, 145, 234, 235, 245, 345

	조합론이라는 분야에서는 이것을 5C3 = 10 이라고 표시하며, 일반적인 식은 아래와 같습니다.
	nCr =
	n!
	r!(n−r)!
	, 단 r ≤ n 이고, n! = n×(n−1)×...×3×2×1 이며 0! = 1.

	이 값은 n = 23 에 이르러서야 23C10 = 1144066 으로 처음 1백만을 넘게 됩니다.

	1 ≤ n ≤ 100 일때 nCr의 값이 1백만을 넘는 경우는 모두 몇 번입니까? (단, 중복된 값은 각각 계산합니다)
	"""

	""" 그냥 공식대로 계산해서 카운트"""

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

	def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(n-r))

	def p53():
	n = [ncr(x, y) for x in range(1, 101) for y in range(1, x+1)]
	return sum((1 for x in n if x > 1000000))

	%time p53()
	# Wall time: 166 ms
	# 4075
	"""

	포커라는 카드게임은 다섯 장으로 된 패의 높고 낮음에 따라 승부를 냅니다. (포커 규칙을 이미 아는 분이라면 규칙 설명 부분은 건너뛰셔도 좋습니다)

	카드 한 장은 아래와 같은 순서대로 값이 높아집니다.

	2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A

	다섯 장으로 이루어진 패의 계급(세칭 "족보")은, 낮은 것부터 높은 순서로 아래와 같습니다.

	High Card : 가장 높은 카드의 값으로 비교.
	One Pair : 한 쌍이 같은 카드.
	Two Pairs : 서로 다른 두 쌍이 같은 카드.
	Three of a Kind : 세 장이 같은 카드.
	Straight : 모든 카드가 연속된 숫자.
	Flush : 모든 카드의 무늬가 같음.
	Full House : 세 장이 같고, 또 한 쌍이 같음 (Three of a Kind + One Pair).
	Four of a Kind : 네 장이 같은 카드.
	Straight Flush : 모든 카드가 연속된 숫자이면서 무늬도 같음.
	Royal Flush : 10, J, Q, K, A가 무늬도 같음.

	두 사람의 패가 같은 종류의 계급이라면, 계급을 구성하는 카드 중 높은 쪽을 쥔 사람이 이깁니다. 예를 들면 8 원페어는 5 원페어를 이깁니다.
	계급을 이루는 카드 숫자까지 같으면 (예: 둘 다 Q 원페어), 다른 카드를 높은 순서대로 비교해서 승부를 정합니다.

	텍스트파일 poker.txt 에는 두 선수가 벌인 1,000회의 승부가 저장되어 있습니다. (우클릭해서 다운로드 받으세요)
	한 줄에는 10장의 카드가 공백으로 분리되어 들어있는데, 앞의 다섯 장은 1번 선수 것이고 뒤의 다섯 장은 2번 선수의 패입니다. 잘못되거나 중복된 데이터는 없으며, 무승부도 없습니다.

	카드 숫자는 2, 3, ... , 9, T, J, Q, K, A 로 (숫자 10은 T로 표시),
	무늬는 C (Club - ♣), D (Diamond - ♦), H (Heart - ♥), S (Spade - ♠) 로 표시되어 있습니다.
	예를 들면 3C 3D 3S 9S 9D 의 경우 3 풀하우스가 됩니다.

	이 데이터를 분석하고, 1번 선수가 이긴 횟수를 구하세요."""


	"""
	카드와 덱을 클래스로 구현하고
	덱에서 카드들의 조합으로 점수를 평가하는 evaluate 메소드를 구현했다.
	두 덱에서 조합과 카드 번호로 승패를 가른다.
	"""

	card_numbers = tuple("23456789TJQKA")
	card_kinds = tuple("CDHS")

	class Card:
	def __init__(self, c):
	self.number = c[0]
	self.kind = c[1]

	@property
	def priority(self):
	return card_numbers.index(self.number)

	def __repr__(self):
	return self.number + self.kind


	class Deck:
	def __init__(self, cards):
	self.cards = cards
	self.cards.sort(key=lambda x:x.priority)

	def groups_number(self):
	val = {}
	for c in self.cards:
	val.setdefault(c.number, []).append(c)
	result = sorted(val.values(), key=lambda x:len(x), reverse=True)
	return result

	def groups_kind(self):
	val = {}
	for c in self.cards:
	val.setdefault(c.kind, []).append(c)
	result = [sorted(x, key=lambda x:x.priority) for x in val.values()]
	return sorted(result, key=lambda x:len(x), reverse=True)

	@property
	def numbers(self):
	return "".join([c.number for c in self.cards])

	def is_Royal_Flush(self):
	if len(self.groups_kind()) == 1 and \
	self.numbers == "TJQKA":
	return True
	return False

	def is_Straight_Flush(self):
	if len(self.groups_kind()) == 1:
	if self.numbers in "".join(card_numbers) * 2:
	return self.cards[-1].priority
	return None

	def is_Four_Kind(self):
	test = [x for x in self.groups_number() if len(x) == 4]
	if test:
	return test[0][-1].priority
	return None


	def is_Full_House(self):
	if len(self.groups_number()) == 2:
	return self.groups_number()[0][-1].priority
	return None

	def is_Flush(self):
	if len(self.groups_kind()) == 1:
	return self.groups_kind()[0][-1].priority
	return None

	def is_Straight(self):
	if self.numbers in "".join(card_numbers) * 2:
	return self.cards[-1].priority

	def is_Three_Kind(self):
	test = [x for x in self.groups_number() if len(x) == 3]
	if test:
	return test[0][-1].priority
	return None

	def is_Two_Pairs(self):
	test = [x for x in self.groups_number() if len(x) == 2]
	if len(test) == 2:
	return max([x[1].priority for x in test])
	return None

	def is_One_Pair(self):
	test = [x for x in self.groups_number() if len(x) == 2]
	if len(test) == 1:
	return test[0][-1].priority
	return None

	def high_card(self):
	return self.cards[-1].priority


	def __repr__(self):
	return str(self.cards)

	def evaluate(self):
	level = ("RF", "SF", "FK", "FH", "FL", "ST", "TK", "TP", "OP", "HC")
	vs = {
	"RF": self.is_Royal_Flush,
	"SF": self.is_Straight_Flush,
	"FK": self.is_Four_Kind,
	"FH": self.is_Full_House,
	"FL": self.is_Flush,
	"ST": self.is_Straight,
	"TK": self.is_Three_Kind,
	"TP": self.is_Two_Pairs,
	"OP": self.is_One_Pair,
	"HC": self.high_card
	}

	for l in level:
	r = vs[l]()
	if r:
	return (l, r, self.high_card())

	def build_deck(s):
	cards = list(map(Card, s.split(" ")))
	return Deck(cards)


	def duel(d1, d2):
	level = dict(zip(("RF", "SF", "FK", "FH", "FL", "ST", "TK", "TP", "OP", "HC"), range(10, 0, -1)))
	l1, e1, c1 = d1.evaluate()
	l2, e2, c2 = d2.evaluate()
	if level[l1] > level[l2]:
	return 1
	if level[l1] == level[l2]:
	if e1 > e2:
	return 1
	elif e1 == e2:
	if c1 > c2:
	return 1
	return 0


	def process(line):
	if line.strip(" ") == "": #빈줄때문에 에러가 난다;;;
	return 0
	cards = list(map(Card, line.split(" ")))
	d1 = Deck(cards[:5])
	d2 = Deck(cards[5:])
	return duel(d1, d2)

	from urllib.request import urlopen

	def p54():
	s = 0
	f = urlopen('http://euler.synap.co.kr/files/poker.txt').read().decode('utf-8').split('\n')
	for line in f:
	s += process(line.strip(" "))
	print(s)

	%time p54()
	# 376
	# Wall time: 310 ms
	"""

	47이란 숫자를 골라서 뒤집은 다음 다시 원래 수에 더하면, 47 + 74 = 121 과 같이 대칭수(palindrome)가 됩니다.
	물론 모든 숫자가 이토록 쉽게 대칭수를 만들어내지는 않습니다. 예를 들어 349의 경우,

	349 + 943 = 1292
	1292 + 2921 = 4213
	4213 + 3124 = 7337

	위에서 보는 것처럼 3번의 반복과정을 거쳐야 대칭수가 됩니다.

	196과 같은 몇몇 숫자들은 이와 같은 과정을 아무리 반복해도 대칭수가 되지 않을 것이라고 추측되는데, 이런 수를 라이크렐 수 (Lychrel number) 라고 부릅니다. 아직 증명되지는 않았지만, 문제 풀이를 위해서 일단 라이크렐 수가 존재한다고 가정을 하겠습니다.

	또한 1만 이하의 숫자들은, 50번 미만의 반복으로 대칭수가 되든지 라이크렐 수이든지 둘 중 하나라고 합니다.
	1만을 넘어서면 10677에 이르렀을 때 비로소 53번의 반복으로 4668731596684224866951378664 라는 28자리의 대칭수가 만들어집니다.

	그러면 1만 이하에는 몇 개의 라이크렐 수가 존재합니까?"""



	def is_palindrome(n):
	s = str(n)
	return s == s[::-1]

	def reversed_number(n):
	return int(str(n)[::-1])

	def check(n):
	for _ in range(50):
	n = n + reversed_number(n)
	if is_palindrome(n):
	return False
	return True

	def p55():
	print(len([x for x in range(1, 10001) if check(x)]))

	%time p55()
	# 249
	# Wall time: 110 ms

	"""
	구골(googol)은 10100을 일컫는 말로, 1 뒤에 0이 백 개나 붙는 어마어마한 수입니다.
	100100은 1 뒤에 0이 2백 개가 붙으니 상상을 초월할만큼 크다 하겠습니다.
	하지만 이 숫자들이 얼마나 크건간에, 각 자릿수를 모두 합하면 둘 다 겨우 1밖에 되지 않습니다.

	a, b < 100 인 자연수 ab 에 대해서, 자릿수의 합이 최대인 경우 그 값은 얼마입니까?
	"""

	"""
	각자리 수의 합을 구해서 최대치를 뽑으면 끝
	"""

	def calc(s):
	return sum([int(c) for c in s])

	def p56():
	xs = [calc(str(a**b)) for a in range(1, 100) for b in range(1, 100)]
	print(max(xs))

	%time p56()
	# 972
	# Wall time: 286 ms
	"""

	제곱근 2는 다음과 같은 연분수의 형태로 나타낼 수 있습니다.

	√ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...

	위 식을 처음부터 한 단계씩 확장해 보면 아래와 같습니다.

	1 + 1/2 = 3/2 = 1.5
	1 + 1/(2 + 1/2) = 7/5 = 1.4
	1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...
	1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...

	그 다음은 99/70, 239/169, 577/408 로 확장이 되다가, 여덟번째인 1393/985 에 이르면 처음으로 분자의 자릿수가 분모의 자릿수를 넘어섭니다.

	처음부터 1천번째 단계까지 확장하는 중에, 분자의 자릿수가 분모보다 많아지는 경우는 몇 번이나 됩니까?"""




	"""
	계산의 편의를 위해서 클래스를 따로 만들었는데,
	유심히 살펴보면 규칙이 있고, 이 규칙만으로 좀 더 간단한 코드도 만들 수 있을 듯 하다.
	"""

	from math import log10

	# 분수꼴을 사용하는 표준 라이브러리 모듈도 있지만, 별도로 구현해본다.

	class Rational(object):
	def __init__(self, q, d, integer=0):
	# q/r
	g = self.gcd(q, d)
	_q = q//g
	_d = d//g
	self.q = _q + _d * integer # 분자
	self.d = _d # 분모

	def gcd(self, a, b):
	if a*b == 0:
	return 1
	(_max, _min) = (a, b) if a > b else (b, a)
	if _max % _min == 0:
	return _min
	else:
	return self.gcd(_min, _max%_min)

	def abbrev(self):
	"""약분된 (분자, 분모)의 쌍을 리턴한다."""
	return (self.q, self.d)


	def description(self, include_integer=True):
	"""분자 / 분모"""의 꼴로 출력한다.
	a = self.abbrev()
	return "%d/%d" % (a[0] + a[1]*self.integer, a[1])


	def reverse(self):
	"""역수를 만듬"""
	self.q, self.d = self.d, self.q


	def addInteger(self, number):
	"""정수를 더해줌"""
	self.q = self.q + self.d * number


	class ChainRational(Rational):
	"""연분수꼴을 만들어 나갈 수 있는 분수 클래스"""

	def __init__(self, q, d, integer, chains):
	super(ChainRational, self).__init__(q, d, integer)
	self.integer = integer
	self.chains = chains

	def getApx(self, n=None):
	self.integer = self.q // self.d
	self.q = 0
	self.d = 1
	n = len(self.chains) if n is None else n
	for i in range(n+1, 1, -1):
	idx = (i-1) % len(self.chains)
	m = self.chains[idx]
	self.addInteger(m)
	self.reverse()
	self.addInteger(self.integer)
	return self.abbrev()


	def p57():
	a = ChainRational(1, 2, 1, (2,2,))
	c = 0
	for i in range(1, 1000):
	q, d = a.getApx(i)
	if int(log10(q)) > int(log10(d)):
	c += 1
	print(c)

	%time p57()
	# 153
	# Wall time: 735 ms
	"""자를 1부터 시작해서 하나씩 늘려가며 아래와 같이 시계반대방향으로 감아가면 한 변의 크기가 7인 정사각형 소용돌이가 만들어집니다.

	37 36 35 34 33 32 31
	38 17 16 15 14 13 30
	39 18 5 4 3 12 29
	40 19 6 1 2 11 28
	41 20 7 8 9 10 27
	42 21 22 23 24 25 26
	43 44 45 46 47 48 49

	우하단 대각선쪽으로 홀수 제곱수(9, 25, 49)들이 늘어서 있는 것이 눈에 띕니다만, 더 흥미로운 사실은 양 대각선상에 놓인 13개의 숫자 중 8개가 소수라는 것입니다. 그 비율은 대략 8/13 ≈ 62% 정도가 됩니다.

	이런 식으로 계속 소용돌이를 만들어갈 때, 양 대각선상의 소수 비율이 처음으로 10% 미만이 되는 것은 언제입니까? 정사각형 한 변의 크기로 답하세요.
	"""



	"""
	격자문제는

	1. 1부터 시작
	2. 2(변의 길이)씩 증가하고 네 번 돌면 한 바퀴
	3. 한바퀴돌고나면 다시 변의 길이가 2씩 증가

	이런 순환을 거치며, 증가값+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 == 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 p58():
	k = 1
	e = 2
	ncount = 1
	pcount = 0

	while True:
	for _ in range(4):
	k += e
	if is_prime(k):
	pcount += 1
	ncount += 1

	if pcount * 10 < ncount:
	print(e+1)
	break
	e += 2


	%time p58()
	# 26241
	# Wall time: 10.5 s
	"""
	컴퓨터상의 모든 문자들은 유일한 코드값에 대응되는데, 보통 ASCII 표준이 널리 쓰입니다.
	예를 들면 대문자 A는 65, 별표(*)는 42, 소문자 k는 107라는 값을 가집니다.
	현대적인 암호화 기법 중에, 텍스트 파일의 내용을 ASCII 코드로 바꾸고
	각 바이트를 비밀키의 값으로 XOR 시키는 것이 있습니다.
	이 방법의 장점은 암호화와 복호화에 동일한 키를 사용할 수 있다는 것입니다.
	예를 들어 65 XOR 42 = 107 이고, 107 XOR 42 = 65 가 됩니다.

	암호문을 절대 깰 수 없도록 하려면, 암호화할 문장의 길이와 같은 무작위의 비밀키를 만들면 됩니다.
	암호문과 비밀키는 따로따로 보관해둬야 하고, 그 반쪽짜리 정보 두 개를 함께 확보하지 않는 한 해독은 불가능합니다.
	하지만 이 방법은 대부분의 경우 실용적이지 못하므로,
	원문보다 짧은 비밀키를 사용하게 됩니다.
	이런 경우 비밀키는 전체 메시지에 대해서 반복적으로 돌아가며 적용됩니다.
	이 때 키의 길이는 보안상 충분할 정도로 길어야 하지만
	또한 쉽게 기억할 수 있을 정도로 짧아야 한다는 미묘한 균형이 요구됩니다.

	이번 문제를 위해서 준비된 암호화 키는 단 3개의 영어 소문자이고,
	cipher1.txt 파일에 암호화된 ASCII 코드값이 들어있습니다.
	원래의 메시지는 평범한 영어 문장임을 힌트로 삼아서 암호문을 해독하고,
	원문에 포함된 모든 ASCII 코드 값의 총합을 구하세요."""

	"""
	일반적인 영어문장에서 가장 많이 나오는 글자는? "e"인데, 실제로는 공백의 가장 많이 나온다.
	암호화된 코드 중에서 가장 많이 나오는 값 3개를 공백문자의 코드값으로 XOR해보면 키가 나올 확률이 크다.

	이 키를 이용해서 복호화한다음, 단어중에서 가장 자주 쓰이는 "the"가 2번 이상 나오는 후보를 걸러내면
	답을 구할 수 있다.
	"""

	from itertools import cycle, combinations_with_replacement, product
	from urllib.request import urlopen



	data = urlopen('http://euler.synap.co.kr/files/cipher1.txt').read().decode('utf-8')
	codes = [int(x) for x in data.split(',')]

	def decode(ciphers, key):
	return "".join([chr(x^y) for x, y in zip(ciphers, cycle([ord(c) for c in key]))])


	def guess_key_from_spaces():
	m = {}
	for c in codes:
	m[c] = m.setdefault(c, 0) + 1

	fc = sorted(m.items(), key=lambda x:x[1], reverse=True)[:3]
	return [chr(x^ord(' ')) for x, _ in fc]


	def p59():
	msg = [decode(codes, x) for x in product(guess_key_from_spaces(), repeat=3) if decode(codes, x).count('the') > 1]
	print(sum((ord(x) for x in msg[0])))

	%time p59()
	# 107359
	# Wall time: 16 ms
	"""

	네 개의 소수 3, 7, 109, 673은 상당히 특이한 성질이 있습니다. 넷 중에 아무것이나 두 개를 골라서 어떤 쪽으로 이어붙이던지 그 결과도 소수가 됩니다. 예를 들어 7과 109를 고르면 7109와 1097 또한 소수입니다.
	3, 7, 109, 673는 이런 성질을 가진 네 소수 중에서 그 합이 792로 가장 작습니다,

	다섯 소수 중에 어떤 두 개를 골라 이어붙여도 소수가 되는 수들을 찾아서, 그 합의 최소값을 구하세요."""



	def is_prime(n):
	if n < 2:
	return False
	if n is 2 or n is 3:
	return True
	if n % 2 is 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 == 0 or n % (k+2) == 0:
	return False
	k += 6
	return True

	"""
	0. 특정한 범위 내의 소수 집합을 만든다.
	1. 가장 작은 수로 부터 시작하여 한 원소 n 을 정하고 n을 앞뒤로 붙여 소수가 되는 수로 구성된 부분집합을 구한다.
	2. 다시 부분집합에 대해 가장 작은 원소 m 에 대해서 같은 방법으로 부분집합을 구한다.
	3. 목표한 만큼(5개)의 수를 뽑아낼 수 없으면 이전 레벨로 돌아간다.

	이 과정을 재귀적으로 처리한다.
	"""



	def p60():


	def test(a, b):
	n = int(str(a) + str(b))
	m = int(str(b) + str(a))
	return is_prime(n) and is_prime(m)

	def process(xs, depth=1):
	if depth > hence:
	return xs

	for x in sorted(xs):
	ys = {i for i in xs if test(i, x)}
	if len(ys) < hence - depth:
	continue
	result = process(ys, depth=depth+1)
	if result is not None:
	result.add(x)
	return result
	else:
	return None

	limit = 10000
	hence = 5
	primes = set((x for x in range(3, limit, 2) if is_prime(x)))

	print(process(primes))


	%time p60()
	# 26033
	# Wall time: 5.98 s