책 이야기

The smallest number expressible as the sum of a prime square, prime cube, and prime fourth power is 28. In fact, there are exactly four numbers below fifty that can be expressed in such a way:

    28 = 2² + 2³ + 2⁴
    33 = 3² + 2³ + 2⁴
    49 = 5² + 2³ + 2⁴
    47 = 2² + 3³ + 2⁴

How many numbers below fifty million can be expressed as the sum of a prime square, prime cube, and prime fourth power?

소수의 제곱, 세제곱, 네제곱의 합계로 구할 수 있는 가장 작은 수는 28이다. 실제로, 소수의 제곱, 세제곱, 네제곱을 합하여 구할 수 있는 50이하의 수는 다음과 같이 4가지가 있다:

    28 = 2² + 2³ + 2⁴
    33 = 3² + 2³ + 2⁴
    49 = 5² + 2³ + 2⁴
    47 = 2² + 3³ + 2⁴

소수의 제곱, 세제곱, 네제곱의 합으로 구할 수 있는 5천만 이하의 숫자는 몇가지인가?

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

문제 난이도는 20%로 높게 책정되어 있지만, 그동안 많이 다뤄왔던 소수의 연장선에 있고 파이썬이 큰 숫자를 쉽게 다룰 수 있게 지원하기 때문에 그렇게 어렵지 않게 해결할 수 있었다. 문제 난이도를 생각하면 좀 더 빠르게 해결가능한 방법이 있을 것 같았지만, 문제에서 요구하는 정석대로 접근해서 해결했다.

5천만 이하의 소수의 제곱, 세제곱, 네제곱을 구하고, 이것을 반복문을 통해 서로 더해나가면 어렵지 않게 구할 수 있다.

처음에, 문제에 있는 prime을 간과한 덕분에 모든 자연수의 제곱, 세제곱, 네제곱을 구하고, 반복문을 통해 더한 것을 모두 나열하니 1.47억개의 리스트가 나왔고, 여기에서 중복을 제거하려 하니 몇시간이 걸려도 답이 나오지 않는 상황이 발생했다.

문제를 다시 읽어보니 소수를 대상으로 하는 것이어서 제곱, 세제곱, 네제곱이 훨씬 적게 되고, 마지막에 중복을 제거하지 않고 집합 자료형을 이용하여 중복을 제거하면서 합을 구했더니 훨씬 간단한 로직으로 구할 수 있었다.

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.