책 이야기

It turns out that 12 cm is the smallest length of wire that can be bent to form an integer sided right angle triangle in exactly one way, but there are many more examples.

    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)

In contrast, some lengths of wire, like 20 cm, cannot be bent to form an integer sided right angle triangle, and other lengths allow more than one solution to be found; for example, using 120 cm it is possible to form exactly three different integer sided right angle triangles.

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

Given that L is the length of the wire, for how many values of L ≤ 1,500,000 can exactly one integer sided right angle triangle be formed?

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 길이로는 변이 정수인 직각삼각형을 만들 수 없으며, 어떤 길이로는 1개 이상의 직각삼각형을 만들 수 있다. 예를 들어, 120cm로는 세가지의 변이 정수인 직각삼각형을 만들 수 있다.

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

L이 선의 길이이고 L이 150만 이하일 때, 1개의 직각삼각형만 만들 수 있는 L은 몇 개 있는가?

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

75번 문제인 것을 보면 좀 더 슬기롭게 해결하기를 요구하는 것 같은데, 문제와 관련되어 아는 공식은 피타고라스 정리 밖에 없으므로, 세 변의 길이가 L이고(a+b+c=L), 짧은 두 변 제곱의 합이 긴 변 제곱과 같다는(a²+b²=c²) 두가지를 이용해 문제를 해결하기로 했다.

실행시간이 너무 많이 걸려, L, a 기준으로 문제에서 제시한 공식을 다시 정리해서 c=(a²+(L-a)²)/2(L-a), b=L-a-c를 구하는 형태로 바꿔보았다.  이 경우에 L은 짝수인 경우에만 계산하도록 해서 시간도 조금 단축시킬 수 있었다. a값이 가장 큰 경우가 a와 b의 값이 같은 때이고, 이 경우 세 변의 합 L=(2+√2)a이며, a=L/(2+√2)a가 된다.

이렇게 범위를 가능한 줄여봤지만 L이 커지면서, a범위도 따라 커져서 실행시간은 여전히 만족스럽지 못했다. L이 10,000 커질때마다 실행시간이 15~20초씩 이전보다 늘어나고 있어 대략 50시간 정도 필요한 것으로 계산되었다.

어쩔수 없이 수학이론의 힘을 빌렸는데, m>n, m+n은 홀수, m과 n의 최대공약수는 1이라는 특성을 가지고 있으며, a=2mn, b=m²-n², c=m²+n²라는 공식이 있었다. 실제로 계산해보니 여기서 두 수의 값에 따라 제일 짧은 변이 a, b 중에 있을 수 있고, m=2, n=1일때 a=4, b=3, c=5(둘레 12)라는 직각삼각형을 구했으면, 전체 길이가 150만 이하일때까지 계속 곱해서 같은 비례를 가지는 직각삼각형을 모두 구해야 한다.

이렇게 구한 직각삼각형을 대상으로 둘레가 같으면서 a, b, c가 다른 경우를 제외하는 과정을 거치면 되는데, 참고로 150만 이하의 직각삼각형 조합이 백만개가 넘기 때문에 같은 값이 없을 때 리스트에 추가하는 것 보다는 집합을 이용하는 것이 속도가 월등히 빠르게 나왔다.

The number 145 is well known for the property that the sum of the factorial of its digits is equal to 145:

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

Perhaps less well known is 169, in that it produces the longest chain of numbers that link back to 169; it turns out that there are only three such loops that exist:

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

It is not difficult to prove that EVERY starting number will eventually get stuck in a loop. For example,

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

Starting with 69 produces a chain of five non-repeating terms, but the longest non-repeating chain with a starting number below one million is sixty terms.

How many chains, with a starting number below one million, contain exactly sixty non-repeating terms?

다음과 같이, 숫자 145는 각 자릿수의 계승(factorial)의 합과 동일하다는 것이 잘 알려져 있다.

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

169에 대해 덜 알려진 것은, 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로 시작하면 반복되지 않는 5개 항을 가지는 체인을 만든다. 하지만, 1백만 이하의 숫자로 시작해서 가장 긴 반복되지 않는 체인은 60개 항이다.

1백만 이하의 숫자로 시작해서 정확히 60개의 반복되지 않는 항을 가지는 체인은 몇 개 있는가?

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

50번 이전의 오일러 프로젝트에 가까운 문제이다. 숫자를 각 자리수로 분해하고 각 숫자에 대한 계승을 합하는 과정을 반복하면서, 이전에 나온 숫자가 다시 나오는지 확인해주고, 체인의 길이가 60개인 경우가 몇 번 나오는지 계산해주면 된다.

성능을 위해서 계승을 매번 계산하지 않고 딕셔너리를 활용하는 형태로 구현했다. 지금 생각해보니 딕셔너리의 앞자리 값이 인덱스와 같으므로 튜플이나 리스트 구조로 구현해도 상관없을 것 같다.

Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:

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

It can be seen that there are 3 fractions between 1/3 and 1/2.

How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d ≤ 12,000?

n과 d가 양의 정수인 분수 n/d를 생각해 보자. n<d이고, HCF(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 사이에는 분수가 3개 있는 것을 알 수 있다.

d가 12,000이하인 경우 1/3과 1/2 사이에는 정렬된 약분된 진분수가 몇 개 있는가?

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

71번 문제가 72번 문제에 이어 또다른 형태로 변형되어 나왔다. 앞의 3줄은 같고 마지막 문제 부분만 바뀌어 있지만 그 한 줄을 풀기 위해서는 또다른 방식으로 접근해야 한다. 72번에서는 실행 시간을 줄이는 방법이 떠오르지 않는데, 이번 문제는 71번 문제 해결 방법을 조금만 변형하면 해결가능할 것 같아 먼저 해결해 보기로 했다.

분모 기준 1/3 주변의 분자값에서 시작해서 1/2 주변의 분자값까지 비교하는 형태로 해서 비교 범위를 줄인 덕분에 빠른 성능은 아니지만 brute force에 가까운 방식으로도 답을 구할 수 있다.

Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:

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

It can be seen that 2/5 is the fraction immediately to the left of 3/7.

By listing the set of reduced proper fractions for d ≤ 1,000,000 in ascending order of size, find the numerator of the fraction immediately to the left of 3/7.

n과 d가 양의 정수인 분수 n/d를 생각해 보자. n<d이고 HCF(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

여기에서 2/5는 3/7의 바로 왼쪽에 있는 것을 알 수 있다.

1,000,000 이하의 약분된 진분수를 크기가 커지는 순서로 나열할 때 3/7의 바로 왼쪽에 있는 분수의 분자는 무엇인가?

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

문제에서 요구하는 것을 다시 풀어보면, 분자가 분모보다 작고, 분자, 분모의 최대공약수가 1인 경우 약분된 진분수라 부른다고 정의하고 있으며, 진분수를 크기대로 나열했을 때, 3/7보다 작은 수가 무엇인지 물어보고 있다.

오래간만에 구현하기 간단한 문제가 나와 처음에는 분모가 2~1,000,000일때 까지의 약분된 진분수의 목록을 (분자, 분모, 나눈값)으로 구해서, 그것을 정렬하고, 3/7 바로 앞의 값을 찾는 형태로 구현했는데, 문제에서 제시한 예시를 구현했을 때에는 금방 동작했지만, 분모가 1,000,000일 때 까지 구하도록 하니 파이썬에서 처음 보는 '메모리 에러' 메시지와 함께 중단되었다. 진분수의 목록을 구하는 라인에서 에러가 발생한 것을 보니 수백만 개의 값이 있는 목록을 만드는 것에서 문제가 생긴 것 같다.

그래서, 각 분모값에 대해 분자를 1부터 키워나가면서 3/7에 근접하게 되는 값을 구하도록 접근 방법을 바꿨다. 리스트를 쓰지 않고 단순 계산만 하도록 몇 줄의 코드로 구현되어서 금방 값을 구할 것으로 예상했는데 실행 시간은 생각보다 너무 오래 걸려서 알고리즘 개선이 필요했다.

고민을 해 보니 분모가 커질수록 분자를 1부터 키워나가면서 3/7에 근접하는 값을 구하는 것에서 시간이 많이 소요되는 것을 찾아냈다. 분자가 시작하는 위치를 1에서 답에 가까운 것으로 바꾸었더니 1일 이상 필요할 것으로 예상되었던 시간이 줄어들어 4초 이내에 답을 구할 수 있었다. 더 빠르게 결과를 구하도록 개선 가능하겠지만 일단 이정도에서 만족하기로 했다.

정답 판정 화면에서 해결 과정을 구체적으로 쓰지 말기를 당부하면서 100번 이후 문제를 스포일하면 계정을 잠그겠다고 되어 있다. 해결과정을 조금 더 간결하게 써야겠다.

We hope that you enjoyed solving this problem. Please do not deprive others of going through the same process by publishing your solution outside of Project Euler. Members found to be spoiling problems beyond the first one-hundred problems will have their accounts locked.

If you are keen to share your insights and/or wish to see how other members have solved the problem, then please visit thread 71 in our private discussion forum.

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까지만 계산하면 되는 것이었다. 그렇게 코드를 수정하고 나서 정답을 구할 수 있었다.

The cube, 41063625 (3453), can be permuted to produce two other cubes: 56623104 (3843) and 66430125 (4053). In fact, 41063625 is the smallest cube which has exactly three permutations of its digits which are also cube.

Find the smallest cube for which exactly five permutations of its digits are cube.

(3453의) 세제곱 수인 41063625는 다른 두 세제곱 수인 56623104 (3843의 세제곱), 66430125 (4053의 세제곱)을 만들어 내도록 바뀔 수(순열을 만들 수) 있다. 실제로, 41063625는 그 자릿수로 세제곱 수인 3개의 순열을 만들 수 있는 가장 작은 수이다.

그 자릿수로 5개의 세제곱 수인 순열을 만들 수 있는 가장 작은 세제곱 수는 무엇인가.

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

가장 간단한 접근은 한 숫자의 세제곱 수를 구하고, 순열을 만들어서 4개 이상의 세제곱 수가 있는 가장 작은 수를 구하는 것이다.

이렇게 할 경우 세제곱 수에 대한 순열을 만들고, 이들 중 세제곱 수가 몇 개인지 검증하는데 많은 시간이 소요될 것으로 예상되어 접근을 다르게 해보기로 했다. 1부터 커가면서 세제곱 수를 만들고, 거기에 있는 자릿수를 정렬하여, 이전의 (정렬된) 세제곱 수 중 그 값과 같은 것이 4개 이상인 것을 찾는 방식으로 접근해 봤다. 논리는 조금 허술한 것 같았는데, 늦지 않는 시간에 정답을 구할 수 있었다.

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.

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

It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13 ≈ 62%.

If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

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

흥미롭게도 오른쪽 아래쪽 대각선에는 제곱수가 놓이고, 더욱 흥미있는 것은 두 대각선에 있는 13개 숫자 중 소수는 8개이며, 비율은 8/13≈ 62%이다.

회전하면서 둘러싸는 새로운 층을 만들면, 한 변의 길이가 9인 정사각형을 만든다. 이 과정이 계속될 때, 두 대각선에 있는 숫자 중 소수의 비율이 10% 이하가 되는 것은 언제인가?

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

1에서 오른쪽 아래에 대각선 방향에 있는 9, 25, 49, ... 는 제곱수이므로 소수가 아니다. 사각형이 커질 때마다 새롭게 검증 대상이 되는 숫자는 처음의 3, 5, 7, 두번째 13, 17, 21의 세 숫자씩이 된다.

대각선에 추가로 포함되는 3개 숫자 중 소수를 판별하고, 대각선 숫자 중 소수의 비율을 구하면 되므로 그렇게 까다롭지 않게 해결 가능하다.

루트2는 무한하게 반복되는 분수로 표현될 수 있다.

처음 4번의 반복을 확장하면 위 그림과 같다:

다음 3번 확장은 99/70, 239/169, 577/408이지만, 8번째 확장은 1393/985이며 분자의 자릿수가 분모 자릿수보다 크게 되는 첫 숫자이다.

처음 1천번 확장에서 몇 개의 분수에서 분자가 분모보다 자릿수가 더 큰가?

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

이 문제에서 루트2를 구하는 과정을 잘 이해했으면, 뒤에 연계되어 나오는 연분수 문제들을 쉽게 해결할 수 있었는데 너무 기계적으로 간단하게 해결해버렸다.

가만히 살펴보면 분모는 직전 분모x2와 2번 직전 분모를 합한 값이며, 그 때 분자는 1을 빼면 직전 분모 값이 되는 것이 보였다. 예를 들어, 3/2, 7/5 다음 수의 분모는 5x2+2=12이며, 분자는 1을 제외하면 5가 되므로 1+5/12=17/12가 된다.

이 과정을 반복하면서 자릿수가 차이나는 경우를 찾는 것으로 간단하게 해결되었다.

A googol (10¹⁰⁰) is a massive number: one followed by one-hundred zeros; 100¹⁰⁰ is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only 1.

Considering natural numbers of the form, a^b, where a, b < 100, what is the maximum digital sum?

구골(10¹⁰⁰)은 100개의 0이 필요한 매우 큰 수이다. 100¹⁰⁰ 은 200개의 0이 필요한 거의 상상할 수 없는 큰 수이다. 크기에도 불구하고 각 자리 숫자의 합은 겨우 1이다.

a, b가 100보다 작고 a^b인 자연수가 있을 때, 각 자릿수 합계의 최대값은 얼마인가?

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

매우 큰 수를 다루는 문제이기 때문에 다른 언어에서는 고려할 요소가 많이 생길 것이지만, 파이썬에서는 문제에서 요구하는 절차를 충실하게 따르면 해결가능한 문제이다.

100미만의 수를 a, b에 순차적으로 대입해서 나온 결과의 각 자릿수를 더하는 것으로 어렵지 않게 구할 수 있다

If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.

Not all numbers produce palindromes so quickly. For example,

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

That is, 349 took three iterations to arrive at a palindrome.

Although no one has proved it yet, it is thought that some numbers, like 196, never produce a palindrome. A number that never forms a palindrome through the reverse and add process is called a Lychrel number. Due to the theoretical nature of these numbers, and for the purpose of this problem, we shall assume that a number is Lychrel until proven otherwise. In addition you are given that for every number below ten-thousand, it will either (i) become a palindrome in less than fifty iterations, or, (ii) no one, with all the computing power that exists, has managed so far to map it to a palindrome. In fact, 10677 is the first number to be shown to require over fifty iterations before producing a palindrome: 4668731596684224866951378664 (53 iterations, 28-digits).

Surprisingly, there are palindromic numbers that are themselves Lychrel numbers; the first example is 4994.

How many Lychrel numbers are there below ten-thousand?

NOTE: Wording was modified slightly on 24 April 2007 to emphasise the theoretical nature of Lychrel numbers.

47의 순서를 반대로 하여 더하면 나오는, 47+74=121은 회문이다.

모든 숫자가 회문을 이렇게 빨리 생성하지 않는다. 예를 들면, 다음과 같다.

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

즉, 349는 회문이 되기 위해 3번 반복이 필요하다.

비록 아직 아무도 증명하지 않았지만, 196 같은 숫자는 절대로 회문을 생성하지 않는 것으로 생각되고 있다. 숫자를 반대로 하고 더하는 숫자를 반복해도 회문을 만들지 못하는 숫자를 라이크렐(Lychrel) 수 라고 한다. 이들 숫자의 이론적인 특성과 이 문제의 목적을 위하여, 다른 방법으로 증명되지 않은 숫자를 라이크렐 수로 가정한다. 추가로, 주어진 1만 이하의 숫자 모두는 (1) 50번 이하의 반복으로 회문이 되거나, (2)  보유한 계산 능력을 활용하여도 회문으로 만들지 못한 것이다. 실제로, 10677은 회문을 만들기 위해 50회 이상의 반복이 필요한 첫 숫자이다: 4668731596684224866951378664 (53회 반복, 28자리 수)

놀랍게도, 회문인 숫자이지만 자신은 라이크렐 수인 숫자가 있다: 첫 예시는 4994이다.

1만 이하의 숫자 중에 몇 개의 라이크렐 수 가 있는가?

주의: 라이크렐 수의 이론적 특성을 강조하기 위해 2007.4.27일 단어가 일부 수정되었다.

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

문제가 어렵다기 보다는 문제를 이해하기 어려웠던 문제였다. 복잡하고 길게 쓰여있지만, 문제에서 요구한 것은 숫자를 반대로 하여 더하는 과정을 50번 반복할 때까지 회문이 되지 않는 경우를 라이크렐(Lychrel) 수라 하고, 1만 이하의 숫자 중 라이크렐 수가 몇 개인지 구하는 것이다.

숫자의 순서를 반대로 하고 두 숫자를 더하는 부분과 특정 숫자가 회문인지를 판별하는 부분을 작성하면, 1만까지 반복하면서 회문이 구해지지 않는 라이크렐 수가 몇 개인지 찾으면 되기 때문에 오일러 프로젝트를 여기까지 풀었으면 그리 어렵지 않게 해결 가능하다.

12345의 숫자 5개에서 3개를 선택하는 방법에는 10가지가 있다.

조합론에서는 ₅C₃=10으로 나타낸다.

일반적으로 r<=n, n!=nx(n-1)x...x3x2x1이고 0!=1일 때, _nC_r=n!/(r!(n-r)!)이다.

n=23이 되어 ₂₃C₁₀=1144066이 되기 전에는 1백만을 넘지 않는다.

1에서 100사이의 n일 때, 몇 개의 _nC_r이 1백만보다 큰가(서로 다를 필요는 없음)?

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

html로 수학 공식을 표현하기 힘들어서 문제를 오일러 프로젝트에서 캡처했고, 조합은 C를 이용해서 표현했다.

팩토리얼(계승) 숫자가 기하급수적으로 커지기는 하지만 파이썬에서 다루는 데 아무 문제가 없기 때문에 리스트로 100!까지 미리 구해놓고 계산을 시작했다.

n과 r을 이중반복문으로 구성해서 n!을 r! x (n-r)!로 나누고 1백만이 넘는 경우가 몇 개인지 계산하면 되므로 그렇게 어렵지 않게 구할 수 있다.

It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.

Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.

숫자 125874와 그 것의 2배인 251748에는 순서가 다르지만 정확히 같은 자릿수가 있다.

2배, 3배, 4배, 5배, 6배 한 숫자와 동일한 자릿수가 있는 가장 작은 양의 자연수는 무엇인가.

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

6배를 한 숫자와 동일한 자릿수가 되려면 1로 시작해야 한다는 것을 알 수 있다. 그 전제에서 원래 숫자와 2배, 3배, 4배, 5배, 6배 한 숫자를 리스트 형태로 정렬해서 비교한 것이 같은 숫자를 찾으면 된다.

51번 이후 문제를 100번까지 모두 풀고 순차적으로 포스팅할 생각이었는데, 아무리봐도 26번과 같이 해결 못하는 문제가 곳곳에 있을 것 같아서 해결하는 순서대로 포스팅하기로 했다.

The prime 41, can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

소수인 41은 다음과 같이 여섯 개의 연속된 소수의 합으로 표현할 수 있다:

41 = 2 + 3 + 5 + 7 + 11 + 13

이것은 100 이하에서 가장 긴 연속된 소수의 합인 소수이다.

1000 이하에서 가장 긴 연속된 소수의 합인 소수는 21개 항목이 있는 953이다.

1백만 이하에서 가장 긴 연속된 소수의 합인 소수는 무엇인가?

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

이 문제에서 시행착오는 시작을 반드시 2로 해야한다고 생각했던 것이다. 프로젝트 오일러에서는 구했던 답이 틀렸다고 나와 이유를 찾는데 한참 걸렸다.

간단하게는 1백만 이하의 소수를 구하고, 그 리스트의 첫번째 요소로 시작해서 만들어지는 1백만 이하의 가장 큰 소수, 두번째 요소로 시작하는 1백만 이하의 가장 큰 소수를 차례로 만들면서 가장 긴 연속된 소수의 합을 구하면 된다.

파이썬 프로그램에 익숙해지기 위해 시작한 프로젝트 오일러 문제풀기였지만, 50번이 넘어가면서 파이썬 보다는 수학에 대한 이해의 비중이 점점 더 커지는 것 갈은데, 흥미가 완전히 없어질때까지 문제풀기를 계속해 보겠다. 이제는 문제들을 풀고 나서 포스팅 해야하기 때문에 포스팅 주기가 매우 길어질 것 갈다.

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?

3330씩 커지는 등차수열 1487, 4817, 8147은 2가지 면에서 특이하다. (i) 세 숫자 모두 소수이고, (ii) 각 4자리 숫자는 서로의 순열이다.

1, 2, 3자리 소수에서는 이런 특성을 가지는 등차수열이 없으며, 4자리 숫자에서 하나의 등차수열이 더 있다.

이 수열의 3개 항목을 연결한 12자리 숫자는 무엇인가?

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

첫 시행착오는 3개의 숫자가 서로의 순열일 뿐이지, 한쪽 방향으로 각 자리수를 이동하는 것이 아니었는데 그런 방식으로 해결하려 했던 것이다. 방향을 잘못 잡았던 덕분에 문제를 처음부터 다시 해결해야 했다.

해결한 방법은 지금 생각하면 효율성은 낮지만, 4자리 소수를 구하고, 그 수로 만들 수 있는 순열 중 소수인 것을 구하고, 소수+순열이 3개 이상인 경우 각 수의 차이가 같은 것이 있는지 찾는 것을 반복하는 것이다.

이 방법의 성능을 개선할 방법으로는 4자리 소수 리스트를 만든 후에, 특정 숫자(소수)와 그 숫자로 만들 수 있는 순열 중 소수인 것을 소수 리스트에서 삭제하면서 구하고, 3개 이상인 경우 각 수의 차이가 같은 것이 있는지 찾는 것을 반복하는 것이다. 이렇게 하면 중복되는 소수여부 검사, 순열 작성 등의 부담이 줄어들 것이다.

The series, 1¹ + 2² + 3³ + ... + 10¹⁰ = 10405071317.

Find the last ten digits of the series, 1¹ + 2² + 3³ + ... + 1000¹⁰⁰⁰.

1¹ + 2² + 3³ + ... + 10¹⁰ = 10405071317 이다.

1¹ + 2² + 3³ + ... + 1000¹⁰⁰⁰ 의 마지막 10자리 숫자는 무엇인가.

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

글을 작성하는 시점 기준으로 30번 이후 처음으로 10만 명이 넘는 사람(정확하게는 115,578명)이 정답을 작성한 문제이다. 1000의 1000승을 구하는 것이 다른 언어였으면 최대값 제한으로 integer가 아닌 자료형을 사용하는 등 까다로웠겠지만, 파이썬에서는 그냥 계산해서 끝의 10자리 숫자를 구하면 되기 때문에 정답자가 많은 것 갈다.

The first two consecutive numbers to have two distinct prime factors are:

    14 = 2 × 7
    15 = 3 × 5

The first three consecutive numbers to have three distinct prime factors are:

    644 = 2² × 7 × 23
    645 = 3 × 5 × 43
    646 = 2 × 17 × 19.

Find the first four consecutive integers to have four distinct prime factors each. What is the first of these numbers?

2개의 서로 다른 소수 인수를 가지는, 처음으로 연속되는 2개의 숫자는 다음과 같다:

    14 = 2 × 7
    15 = 3 × 5

3개의 서로 다른 소수 인수를 가지는, 처음으로 연속되는 3개의 숫자는 다음과 같다:

    644 = 2² × 7 × 23
    645 = 3 × 5 × 43
    646 = 2 × 17 × 19.

4개의 서로 다른 소수를 인자로 가지는, 처음으로 연속되는 3개의 숫자를 구하시오. 이 중 첫 숫자는 무엇인가?

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

5번 문제를 풀 때 소인수분해를 구현할 만큼 파이썬을 이해한 것이 아니어서 우회하는 방법으로 해결했는데, 이 문제에서는 소인수분해를 이용해서 해결했다.

해당하는 숫자보다 작은 값을 가지는 소수 리스트를 만들어 나가면서, 해당 숫자를 소수 리스트의 값으로 차례대로 계속 나눠 몇 개의 소수로 구성되는지를 판별하는 것이다. 예를 들어, 45는 2로 나눠지지 않고, 3으로는 2번 나눠지고(45/3=15, 15/3=5), 5는 5로 1번 나눠지므로 소인수는 3,5인 2개로 판별한다.

문제에서 요구하는 대로 소인수분해를 단순하게 구현한 덕분에 답을 구하는 데 시간이 많이 소요되었다. 아무래도 이 문제에서 요구하는 것은 문제에 충실하게 답을 구하는 것 보다는, 좀 더 효율적으로 답을 구하는 방법을 생각해 보는 것일 수도 있겠다.