책 이야기

By replacing the 1^st digit of the 2-digit number *3, it turns out that six of the nine possible values: 13, 23, 43, 53, 73, and 83, are all prime.

By replacing the 3^rd and 4^th digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes among the ten generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property.

Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.

2자리 숫자 *3의 첫번째 자릿수를 바꾸면 가능한 9개의 값 중 6개인 13, 23, 43, 53, 73, 83이 소수이다.

56**3의 3번째, 4번째 자릿수를 같은 숫자로 바꾸면, 가능한 10개의 값 중 5개(56003, 56113, 56333, 56443, 56663, 56773, 56993)가 소수가 되는 최초의 숫자이다. 따라서, 56003은 이러한 속성을 가지는 숫자 중 가장 작은 소수이다.

같은 자리의 숫자 일부를 바꿔(인접한 숫자일 필요 없음) 8개의 소수를 만드는 가장 작은 소수는 무엇인가?

--------------------------------------------------------------------------

문제를 보고 가장 난감했던 부분은 대상 숫자의 자릿수가 없고, 몇 개의 숫자를 바꿀 것인지 없으며, 어느 자리를 바꿀 것인지에 대한 힌트도 없는데 8개의 소수를 만들어내는 숫자를 찾으라는 것이었다. 짝수는 소수가 아니므로 8개를 만들기 위해서는 1의 자리 숫자를 바꾸지 않는 것은 확실한데 다른 숫자는 엄두가 나지 않았다.

몇 번의 반복문을 통해 해결했는데, 전체 자릿수를 두고, 바꾸면서 들어갈 숫자가 몇자리인지 정하고, 고정되게 들어갈 숫자를 반복하게 하고, 조합(combinations)을 이용해 바꾸면서 숫자가 들어갈 자리를 반복하고, 각 자리에 0~9를 대입하여 그 중 소수가 몇 개인지 찾도록 하였다.

반복되는 부분이 많고, 반복문이 독립적이지 않고 앞의 반복문에 연동되고(6자리 숫자인데 바꾸면서 들어갈 숫자가 2자리이면 고정되게 들어갈 숫자는 4자리), 파이썬의 특징을 살리지 못하는 전통적인 방식으로 코딩을 하다 보니 생각보다 코딩은 복잡했는데 답은 구할 수 있었다.

앞의 반복문에 연동되는 범위 계산을 잘못해서 오답을 구한 덕분에, 프로그램을 구성하는 시간만큼 수정하는 시간이 필요했다.

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom in triangle.txt (right click and 'Save Link/Target As...'), a 15K text file containing a triangle with one-hundred rows.

NOTE: This is a much more difficult version of Problem 18. It is not possible to try every route to solve this problem, as there are 2⁹⁹ altogether! If you could check one trillion (10⁹⁹) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)

아래 삼각형의 정상에서 시작하여 다음 줄의 인접한 숫자로 이동할 때, 정상에서 끝까지 가장 큰 합계는 23이다.

3
7 4
2 4 6
8 5 9 3

즉, 3 + 7 + 4 + 9 = 23 이다.

100개 줄이 있는 15K 크기의 triangle.txt (우클릭하고 "(으)로 링크 저장")에서 정상에서 끝까지 가장 큰 합계를 구하시오.

주의: 이것은 Problem 18의 훨씬 어려운 버전이다. 2⁹⁹ 개의 경로가 있으므로, 이 문제를 해결하기 위해 모든 경로를 확인하는 것은 불가능하다! 1초에 1조(10⁹⁹)개의 경로를 검사할 수 있으면 모든 경로를 검사하는 데 200억 년 이상 소요된다. 이 문제를 풀기 위해 더 효율적인 알고리즘이 필요하다. ;o)

--------------------------------------------------------------------------

18번 문제를 해결할 때 사용한 방법으로 해결하였다. 문제는 top-down 방식으로 물어봤지만, 해결은 bottom-up 방식으로 아래에서 올라가는 전략을 선택하는 것이다.

예를 들어 3번째 줄을 기준으로 보면, 2는 8과 5중 8이 크므로 둘을 합한 10, 4는 5와 9중 9가 크므로 13, 6은 9와 3중 9가 크므로 15, 이런 식으로 정상에 도달할 때까지 계산해 나가면 가장 큰 경로를 적은 시간으로 구할 수 있다.

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

    1/2=0.5

    1/3=0.(3)

    1/4=0.25

    1/5=0.2

    1/6=0.1(6)

    1/7=0.(142857)

    1/8=0.125

    1/9=0.(1)

    1/10=0.1

Where 0.1(6) means 0.166666⋯, and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.

Find the value of d<1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

분자가 1인 분수를 단위 분수(unit fraction)이라 한다. 분모가 2에서 10인 단위 분수는 다음과 같이 10진수로 나타낼 수 있다:

    1/2=0.5

    1/3=0.(3)

    1/4=0.25

    1/5=0.2

    1/6=0.1(6)

    1/7=0.(142857)

    1/8=0.125

    1/9=0.(1)

    1/10=0.1

0.1(6)은 0.166666⋯을 의미하고, 1자리의 반복 사이클을 가지고 있다. 1/7은 6자리의 순환마디가 있음을 알 수 있다. d<1000일 때, 1/d이 가장 긴 순환마디를 가지는 d를 찾으시오.

--------------------------------------------------------------------------

분수 값에서 순환소수 값을 구하는 방법을 알면 쉽게 풀 수 있고, 이것은 초등학교 산수 수준의 문제인 것 같기는 한데 어떻게 구하는 지 전혀 아이디어가 떠오르지 않아 보류하고 지나갔던 문제이다.

다시 봐도 아이디어가 떠오르지 않아 분수를 순환소수로 구하는 요령을 인터넷으로 검색하고 그것을 파이썬 코드로 만들어서 답을 구할 수 있었다. 9를 계속 만들어가면서 나눠지면 그 때 있는 9의 갯수가 순환마디의 크기를 뜻하는 것이 되는데, 예를 들어, 분모가 6일 때 90을 나눌 수 있고, 이 때 9는 1개 있으므로 순환마디는 1이고, 분모가 7일 때 999999을 나눌 수 있고, 이 때 9가 6개 있으므로 순환마디 6이 된다.

2~999까지의 반복문 안에, 9의 갯수(순환마디)를 찾는 2개의 반복문으로 구성해서 문제를 풀었고, 답을 구하는데 28초가 걸려 그리 성능이 좋은 방법으로 구현하지 않았다는 것을 알았지만 묵혀둔 미결 문제를 해결한 기쁨이 더 컸다.

프로젝트 오일러 문제를 100번까지 시도했는데, 이 중 (직접 풀어 해결한 79번 포함한) 72개를 풀었고, 28개 문제는 아직 해결하지 못했다. 남은 문제를 난이도 기준으로 보면, 난이도 5% 문제 2개(26, 59번), 10% 문제 4개(54, 69, 76, 81), 15% 문제 3개(51, 65, 85), 20% 문제 7개(60, 61, 64, 70, 72, 80, 82), 25% 문제 5개(66, 68, 77, 83, 96), 30% 문제 2개(78, 100), 35% 문제 4개(84, 86, 93, 98), 40% 문제 1개(88)이다.

바로 해결하지 못한 문제만 남았기에 시간이 많이 필요할 수도 있을 것 같지만, 일단 100번까지는 모두 해결하는 것을 목표로 계속 시도해봐야겠다.

파이썬을 익히기 위해 시작한 프로젝트 오일러인데, 이제는 수학공부를(특히나 정수론) 더 많이 한다는 느낌이긴 한데, 그래도 프로젝트 오일러 덕분에 파이썬 기반으로 파일 읽고 쓰기, 자료형 변환과 활용, 함수 활용, 모듈 사용 등을 편하게 활용가능하게 되었다. 하지만, 람다 표현식, 클래스, 제너레이터, 정규표현식 등 좀 더 파이썬스럽게 프로그래밍하기 위해 필요한 부분은 문제 해결에 잘 활용되지 않고, 아직도 체계적으로 이해하지 못하고 있는 것 같다.

그리고, 문제 해결하기 위해 작성한 코드가 파이썬이라기 보다는 C와 같은 전통적인 프로그램 형태에 가깝기 때문에 소스코드 없이 어떤 로직(내지는 알고리즘)이 필요한지만 기록하는 형태로 계속 정리할 생각이다.

The 5-digit number, 16807=7⁵, is also a fifth power. Similarly, the 9-digit number, 134217728=8⁹, is a ninth power.

How many n-digit positive integers exist which are also an nth power?

5자리 수인 16807은 또한 5제곱 수이기도(7⁵) 하다. 비슷하게, 9자리 수인 134217728은 9제곱 수이다(8⁹).

n자리 제곱수이기도 한 n자리 양의 자연수는 몇 개 있는가?

--------------------------------------------------------------------------

숫자에서 범위를 명확하게 얘기하지 않아 고민하는 시간이 필요했다. 답을 구하는 알고리즘 자체는 각 숫자의 제곱수를 구해서(5의 경우 5, 25, 125, 625, ...), 각 숫자가 각 자리의 제곱수에 해당하는지 확인하면 된다. 예로 든 5의 경우 5의 1제곱은 5이므로 1자리 수, 5의 2제곱은 25로 2자리 수, 5의 3제곱은 125로 3자리 수이지만, 5의 4제곱은 625로 4자리 수가 아니다.

처음에는 n자리를 한자리 수로 생각해서 9의 9제곱까지만 구했는데 정답이 아니었다. 곰곰히 생각해 보니 상한을 두지 말고 구해야 하는 것이었고, 밑에 해당하는 숫자는 10의 1승은 2자리 수(10)이므로 9까지만 계산하면 되는 것이었다. 그렇게 코드를 수정하고 나서 정답을 구할 수 있었다.