책 이야기

It is easily proved that no equilateral triangle exists with integral length sides and integral area. However, the almost equilateral triangle 5-5-6 has an area of 12 square units.

We shall define an almost equilateral triangle to be a triangle for which two sides are equal and the third differs by no more than one unit.

Find the sum of the perimeters of all almost equilateral triangles with integral side lengths and area and whose perimeters do not exceed one billion (1,000,000,000).

변의 길이가 정수이고 정수 크기의 면적을 가지는 정삼각형이 없다는 것은 증명하기 쉽다. 그러나, 거의 정삼각형인 5-5-6의 면적은 12로 정수가 된다.

두 변이 같고 다른 변과 길이 차이가 1 이하인 삼각형을 "거의 정삼각형"으로 정의하고자 한다.

변의 길이와 면적이 정수이고 둘라가 10억을 이하인 모든 "거의 정삼각형"의 둘래의 합계를 구하시오.

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

"거의 정삼각형"을 다시 생각해보면 2개의 직각삼각형이 붙어 있는 구조이며, 직각삼각형의 빗변(가장 긴 변)이 "거의 정삼각형"에서 길이가 같은 변이 된다. 그리고 길이가 같은 변을 a, 나머지 변을 b라 하면, 문제에서 정의한 내용에 따라 b=a±1이 되고, "거의 정삼각형" 안에 있는 직각삼각형은 빗변이 a, 다른 변은 피타고라스 정리에 의해 각각 b/2=(a±1)/2, (a**2-(b/2)**2)**0.5가 된다.

문제에서 둘레와 면적이 모두 정수가 된다고 했으므로 b, b/2, (a**2-(b/2)**2)**0.5 모두 정수가 되어야 하며 a*2+b는 10억 이하가 되어야 한다. 그리고, b/2가 정수가 되기 위해서는 a는 홀수가 된다.

이런 전제조건에 따라 a가 커지면서 b, b/2, (a**2-(b/2)**2)**0.5가 정수이고, 둘레가 10억 이하인 "거의 정삼각형"을 계속 구했는데, 정상적으로 나와야 할 갯수보다 6개가 더 나와서 둘레의 합이 훨씬 크게 나오는 문제가 생겼다.

원인을 파악해 보니 (a**2-(b/2)**2)**0.5 값을 int(a**2-(b/2)**2)**0.5)와 비교해서 같으면 정수로 판별했는데, 제곱수와 차이가 매우 미세하면 제곱수가 아닌데도 두 값이 같게 나오는 문제 때문에 답을 6개나 더 구한 것으로 추정되었다.

is_integer() 등 몇 가지 방법을 적용했지만 해결되지 않아서, 제곱근을 씌운 상태에서 계산하지 않고 제곱인 상태에서 값을 비교해서 제곱수 여부를 판별하게 했더니 정답을 구할 수 있었다. 이전 문제에서 비슷한 경험이 있어 빨리 해결 가능했지, 로직의 문제가 아닌 프로그램 고유 특성에서 생기는 이런 현상은 찾기가 쉽지 않은 것 같다.

By using each of the digits from the set, {1, 2, 3, 4}, exactly once, and making use of the four arithmetic operations (+, −, *, /) and brackets/parentheses, it is possible to form different positive integer targets.

For example,

    8 = (4 * (1 + 3)) / 2
    14 = 4 * (3 + 1 / 2)
    19 = 4 * (2 + 3) − 1
    36 = 3 * 4 * (2 + 1)

Note that concatenations of the digits, like 12 + 34, are not allowed.

Using the set, {1, 2, 3, 4}, it is possible to obtain thirty-one different target numbers of which 36 is the maximum, and each of the numbers 1 to 28 can be obtained before encountering the first non-expressible number.

Find the set of four distinct digits, a < b < c < d, for which the longest set of consecutive positive integers, 1 to n, can be obtained, giving your answer as a string: abcd.

{1, 2, 3, 4}의 각 숫자를 한 번씩 사용하고, 4개 연산자(+, -, *, /)와 괄호를 사용하여, 서로 다른 정수를 구할 수 있다.

예를 들면 다음과 같다.

    8 = (4 * (1 + 3)) / 2
    14 = 4 * (3 + 1 / 2)
    19 = 4 * (2 + 3) − 1
    36 = 3 * 4 * (2 + 1)

주의할 것은 숫자를 연결하여 12+34로 계산하는 것은 허용되지 않는다.

{1, 2, 3, 4} 집합을 이용하여 31가지 다른 숫자를 구할 수 있고, 최대값은 36이다. 그리고, 1~28까지는 연속해서 구할 수 있다.

1부터 n까지 가장 긴 연속으로 숫자를 구할 수 있는 a<b<c<d인 숫자 4개를 구하고, 답안은 abcd 형태로 작성하라.,

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

몇가지 고민할 사항이 있어 나중에 해결했는데, 인터넷에서 누군가가 알려준 eval() 함수를 활용하면서 많은 부담을 덜 수 있었다.

연산자는 +,-,*,/의 4가지를 사용하는데, 예시에 있는 것처럼 연산자의 우선순위와 관계없이 계산하기 위하여 괄호를 이용해 인위적으로 순서를 지정할 필요가 있다. 연산자가 들어갈 곳은 3자리이므로 괄호를 통해 순서를 강제하는 것은 연산자의 순서를 1,2,3이라 할 때 (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)의 6가지 경우가 있는데 이 중 (3,1,2)는 괄호를 통해서도 만들어낼 수 없는 경우이기 때문에 5가지 연산을 하게 만들면 된다.

4가지 숫자를 점차 커지는 순서로 만들고, 생성된 숫자 4개를 순열을 통해 다양한 순서를 만들고, 각 순서에 4가지 연산자 조합에 대해 5가지 연산을 해서, 결과가 양의 정수일 때 결과에 더하고, 모은 결과를 집합, 정렬을 통해 순서대로 배열해서 1부터 가장 긴 연속된 숫자가 있는 4가지 숫자 조합을 찾으면 된다.

위 경우 중 4가지 숫자를 커지는 순서로 만드는 데 반복문 4회, 순열 생성에 반복문 1회, 연산자를 3자리에 배열하는 데 반복문 3회를 해서 들여쓰기를 많이 하는 구조가 되었다.

그리고, 0으로 나누는 경우가 발생할 수 있으므로 exception을 사용하여 예외처리했는데, 개발툴인 Visual Studio Code가 익숙하지 않아서 exception을 무시하도록 설정하지 않아 처음에는 계속 F5를 눌러야 했다. 나중에 보니 Raised Exceptions을 Breakpoints로 설정하지 않도록 하는 옵션이 있어 결과를 빨리 볼 수 있었다.

A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before.

For example,

44 → 32 → 13 → 10 → 1 → 1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.

How many starting numbers below ten million will arrive at 89?

숫자 체인은 각 자릿수를 더하여 새로운 숫자를 구하는 것을 끝날때까지 반복하면서 생성된다.

예를 들면 다음과 같다.

44 → 32 → 13 → 10 → 1 → 1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

따라서, 어떤 체인이든 1 또는 89가 되면 무한반복되면서 정체된다. 가장 놀라운 것은 모든 숫자는 결국 1 또는 89에 이른다는 것이다.

1천만 이하의 숫자 중에 89가 되는 숫자는 몇 개인가?

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

10자리수 이상은 자릿수별로 쪼개어서 제곱하고 더하는 과정을 반복하면서 89가 나오는 경우의 수를 더하도록 하면 되는 문제이다. 다만, 1천만 까지 계산하기를 요구했기 때문에 시간은 생각보다 엄청 많이 필요하게 된다.

그래도, 이 방법이 가장 정확한 방법이라 생각하고 속도를 조금 개선해보기 위해 제곱수를 매번 계산하지 않고 리스트를 만들어서 참조하게 했다. 그렇게 해서 256초가 245초로 조금 개선될 수 있었다.

문제를 해결한 후에, 인터넷을 검색해보니 동일한 순열(4666777과 6466777, 7664776)에 대해서는 한 번 계산한 결과를 이용하여 모든 체인을 계산하지 않도록 성능 개선이 가능하다고 되어 있다. 정말 세상은 넓고 해결방안은 다양하다는 것을 새삼 느끼게 된다.

A spider, S, sits in one corner of a cuboid room, measuring 6 by 5 by 3, and a fly, F, sits in the opposite corner. By travelling on the surfaces of the room the shortest "straight line" distance from S to F is 10 and the path is shown on the diagram.

However, there are up to three "shortest" path candidates for any given cuboid and the shortest route doesn't always have integer length.

It can be shown that there are exactly 2060 distinct cuboids, ignoring rotations, with integer dimensions, up to a maximum size of M by M by M, for which the shortest route has integer length when M = 100. This is the least value of M for which the number of solutions first exceeds two thousand; the number of solutions when M = 99 is 1975.

Find the least value of M such that the number of solutions first exceeds one million.

S라는 거미가 가로 6, 세로 5, 높이 3인 육면체 방의 구석에 있고, 반대쪽 코너에는 파리 F가 있다. 방 표면을 따라 S에서 F로 가는 가장 짧은 "직선" 거리는 10이고, 경로는 다음 그림과 같다.

그러나, 육면체 방에서는 3개의 최단 경로 후보가 있으며, 최단 경로는 정수길이가 아닐 수 있다.

회전을 무시하고, M=100일때 최대 가로 M(이하), 세로 M(이하), 높이 M(이하)이고 최단 경로가 정수인 육면체는 2060개가 있다. 이것은 M이 99일 때, 최단 경로가 정수인 육면체는 1975개 이며, 100일 때 처음으로 육면체의 수가 2천을 넘는다.

최단 경로가 정수인 육면체의 숫자가 1백만을 넘는 첫 M을 구하시오.

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

문제에서 회전을 무시한다고 했으므로, 경우의 수를 줄여서 계산해야 한다.

육면체에서 면의 길이 순서대로 a, b, c라고 한다면, 1<=a<=b<=c<=M이 된다. 이 조건에서, c**2+(a+b)**2의 제곱근이 자연수인 경우를 찾으면 된다.

a, b, c에 대한 3번의 반복문이 있어 실행시간이 필요하지만, 반복문을 구성할 때 위 조건에 따라 잘 정리한다면(b는 a값부터 반복문을 시작하고, a, b의 최대값은 c) 그렇게 어렵지 않게 구현 가능하다.

By counting carefully it can be seen that a rectangular grid measuring 3 by 2 contains eighteen rectangles:

Although there exists no rectangular grid that contains exactly two million rectangles, find the area of the grid with the nearest solution.

3x2 그리드에서 볼 수 있는 사각형을 주의깊게 세어 보면 18개가 나온다:

정확하게 2백만 개 사각형이 있는 그리드는 없지만, 2백만에 가장 가까운 그리드를 구하시오.

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

가로 세로로 나눠 생각해보면, 크기 3인 면(3x1 그리드)에 크기 1의 사각형은 3개, 크기 2의 사각형은 2개, 크기 3의 사각형은 1개 들어간다. 즉, (크기-사각형 크기+1)의 합계가 된다. 여기에 세로 길이를 고려하여 갯수를 구하면(가로x세로) 전체 사각형 갯수가 나온다.

이 문제에서는 2백만에 가장 가까운 그리드를 요구했는데, 2백만 보다 큰 지 작은 지 정확히 나오지 않아 두 경우를 모두 고려해야 했다.

그리고, 가로, 세로 크기에 한계를 정하지 않은 상태여서 그 부분을 미리 유추해야 할 필요가 있다. 가만히 보면 가로 합계x세로 합계가 형태이므로, (x(x+1)/2)*(y(y+1)/2)의 공식이 나오게 된다. 즉, x²*y²이므로 가로 세로가 100일 때 천만 이상의 사각형이 나오게 되므로, 여유를 주고 반복문을 통해 2백만에 근접한 값을 구하게 했다.

공식을 생각하기 전에 사각형 갯수를 구하는 반복문을 만들어서 그대로 썼는데, 간단한 공식으로 구할 것을 사각형 크기별로 합계를 모두 구하게 해서, 실행 속도를 손해보게 된 것 같다.

NOTE: This problem is a more challenging version of Problem 81.

The minimal path sum in the 5 by 5 matrix below, by starting in any cell in the left column and finishing in any cell in the right column, and only moving up, down, and right, is indicated in red and bold; the sum is equal to 994.

Find the minimal path sum from the left column to the right column in matrix.txt (right click and "Save Link/Target As..."), a 31K text file containing an 80 by 80 matrix.

주의: 이 문제는 문제81 보다 더 어렵다.

첫번째 열의 원소에서 시작해서 마지막 열에서 끝나며 위, 아래, 오른쪽으로만 움직일 때 아래의 5x5 행렬에서 최소 경로는 붉은 색으로 굵게 표시되어 있으며 합계는 994이다.

80x80 행렬이 있는 31K 텍스트 파일 matrix.txt (우클릭 하고 "다른 이름으로 링크 저장")의 첫번째 열에서 마지막 열까지 이동할 때 최소 경로의 합계를 구하시오.

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

81번 문제를 해결한 방법을 그대로 사용할 수는 없었지만, 그 방법을 가져와서 반복을 통해 해결했다. 81번 문제에서는 답을 구할 자리가 행렬 전체의 마지막 자리(80, 80)이지만, 이번 문제에서는 마지막 열(x,80) 모두가 답이 되는 후보이기 때문에 마지막 열 각 행을 기준으로 최소 경로의 값을 구하는 방식으로 접근했다..

위 예시를 기준으로 예를 들면, 2번째 열, 2번째 행의 최소값 후보는 1번째 열 각 행에서 시작한 5개 경로의 값 900(131+673+96), 297(201+96), 1529(630+803+96), 2135(537+699+83+96), 3135(805+732+699+803+96) 중 가장 작은 297이 된다. 이 예시에서 131다음에 201로는 왜 안가고 673으로만 가는지 의문이 들 수 있는데, 이 경우 201에서 시작한 경우보다는 무조건 크기 때문에 최소값이 될 수 없다고 생각해서 배제했다.

이런 식으로 각 열의 최소값을 2번째 열부터 마지막 열까지 구하고, 마지막 열 각 행의 최소 경로 값 중에서 제일 작은 값을 찾으면 된다. 그런데, 다중 반복문을 실행하느라 시간이 7초 이상 걸리는 것을 보면 좀 더 빠른 방식으로 해결하는 방법이 있을 것 같다.

In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated in bold red and is equal to 2427.

Find the minimal path sum from the top left to the bottom right by only moving right and down in matrix.txt (right click and "Save Link/Target As..."), a 31K text file containing an 80 by 80 matrix.

아래의 5x5 행렬에서, 오른쪽과 아래로만 갈 수 있을 때 왼쪽 위부터 오른쪽 아래까지 가는 최소 경로값은 굵은 붉은색으로 표시된 것과 같으며 2427이다.

80x80 행렬이 있는 31K 텍스트 파일 matrix.txt (우클릭하고 "다른 이름으로 링크 저장")을 오른쪽과 아래로만 갈 수 있을 때 , 왼쪽 위부터 오른쪽 아래까지 가는 최소경로 합계를 구하시오.

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

파일을 다루는 것에 익숙하지 않아서 파일을 열고, 내용을 읽고, 쉼표로 분리하고, 문자열을 숫자로 바꾸는 과정 하나하나를 다시 기억을 살려가며 해야 했다.

처음에는 단순하게 갈 수 있는 두 경우 중 작은 경우로 가는 것을 0,0과 79,79에서 시작하도록 해봤는데 오답이었다.

그래서, 생각해보니 방향이 제한적이기 때문에 조금은 단순하게 접근 가능할 것 같았다. 0,0부터 시작해서 차례로 이전과의 합계를 기록해 나가는 방식으로 하면, 79,79에 전체 합계가 기록되는 것이다. 각 자리에서는 자신에게 올 수 있는 2가지 경우의 합계 중 작은 것을 선택해 나가는 방식으로 하는 것이다.

이후 문제에까지 확장하여 적용하는 것은 쉽지 않을 것 같았는데, 일단 이 문제는 이 방식으로 해결 가능했다.

It is well known that if the square root of a natural number is not an integer, then it is irrational. The decimal expansion of such square roots is infinite without any repeating pattern at all.

The square root of two is 1.41421356237309504880⋯, and the digital sum of the first one hundred decimal digits is 475.

For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits for all the irrational square roots.

자연수의 제곱근이 정수가 아니면, 무리수가 된다. 이러한 제곱근의 소숫점은 반복되지 않으면서 무한하게 확장된다.

2의 제곱근은 1.41421356237309504880⋯이며, 소숫점 처음 100자리 숫자의 합은 475이다. 

100까지 자연수 중에서 제곱근이 무리수인 숫자의 소숫점 처음 100자리 숫자의 총합은 얼마인가?

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

처음에는 연분수 문제(문제 64)를 응용해서 간단하게 해결하려 했는데, 제곱근을 직접 계산하지 않으면 소숫점 이하에서 오차가 발생하는 문제가 있어, 제곱근을 손으로 계산하는 방법을 찾아 알고리즘으로 구현했다.

위 링크의 방법2에 왠만한 설명보다 자세하게 나와있기 때문에 코딩하는 데 그리 어렵지 않을 것이다. 프로그램으로 만드는 과정에서 break를 뺀다든지 하는 몇가지 오류가 있어 수정하는 데 시간은 좀 걸렸지만 재미있게 해결 가능한 문제였다.

The points P (x1, y1) and Q (x2, y2) are plotted at integer co-ordinates and are joined to the origin, O(0,0), to form ΔOPQ.

There are exactly fourteen triangles containing a right angle that can be formed when each co-ordinate lies between 0 and 2 inclusive; that is,
0 ≤ x1, y1, x2, y2 ≤ 2.

Given that 0 ≤ x1, y1, x2, y2 ≤ 50, how many right triangles can be formed?

좌표 P (x1, y1)과 Q (x2, y2)은 정수 좌표에 있으며, 시작점인 O(0, 0)과 연결되어 삼각형 ΔOPQ를 만든다.

좌표가 0과 2 사이일 때, 정확히 14개의 직각삼각형을 구할 수 있다.

0 ≤ x1, y1, x2, y2 ≤ 2.

0과 50 사이(0 ≤ x1, y1, x2, y2 ≤ 50)일 때 몇 개의 직각삼각형이 있는가?

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

O, P, Q 간의 관계를 잘 설정하면 반복문을 통해 만들어지는 삼각형을 피타고라스 정리(a²+b²=c²)를 이용해 직각삼각형인지 판단하면 되는 문제로 파악되었다.

O를 기준으로 P는 오른쪽, Q는 위쪽에 있는 좌표로 계산하기로 설정하였고, 반복문을 통해 P, Q가 가능한 모든 좌표에 대해 OP, OQ, PQ 거리를 구해서 피타고라스 정리를 만족하는 삼각형의 갯수를 구하였다.

P, Q의 한계를 조금 더 세밀하게 설정하면 속도가 더 빨라질 것 같았지만, 크게 늦지 않게 답을 구할 수 있어 만족하기로 했다.

Let p(n) represent the number of different ways in which n coins can be separated into piles. For example, five coins can be separated into piles in exactly seven different ways, so p(5)=7.

    OOOOO
    OOOO   O
    OOO   OO
    OOO   O   O
    OO   OO   O
    OO   O   O   O
    O   O   O   O   O

Find the least value of n for which p(n) is divisible by one million.

n개의 동전을 서로 다른 방법으로 묶는 방법을 p(n)이라 하자. 예를 들어, 5개의 동전은 일곱 가지 다른 방법으로 묶을 수 있다. 따라서 p(5)=7이다.

    OOOOO
    OOOO   O
    OOO   OO
    OOO   O   O
    OO   OO   O
    OO   O   O   O
    O   O   O   O   O

p(n)이 1백만인 n의 최소값을 찾으시오.

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

동전으로 변형되어 있지만 문제 자체는 76번 문제과 동일한 알고리즘으로 해결 가능하다. 즉, 오일러의 오각수 정리 공식을 적용하면 된다. 76번과 차이점은, 76번은 2개 이상의 조합을 요구했기 때문에 전체 숫자에 해당하는 1을 빼야하지만(위 예시에서 동전 5개 묶음을 제외하므로 76번에서 p(5)=6), 이번 문제에서는 그 과정이 필요없다는 것이다.

한가지 고려할 사항은 동전 숫자에 상한선이 없으므로 76번 문제에서 적용했던 방법을 조금 변형시킬 필요가 있었다. 처음에는 상한선을 1만으로 했는데 답이 나오지 않아, 10만으로 바꾸고 나서 답을 구할 수 있었다.

It is possible to write ten as the sum of primes in exactly five different ways:

7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2

What is the first value which can be written as the sum of primes in over five thousand different ways?

10을 소수의 합으로 나타내는 데에는 다음과 같이 5가지 방법이 있다:

7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2

소수의 합으로 5천가지 이상의 방법으로 표현 가능한 첫 숫자는 무엇인가?

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

31번 문제, 76번 문제를 조금 변형시켜 만들어진 문제이지만, 슬프게도 31번 문제, 76번 문제를 해결하는데 사용한 방법을 적용할 수 없었다. 31번 문제는 동전 숫자를 알아서 반복문을 중첩시켜 해결했고, 76번 문제는 정수론에 있는 분할수 공식을 이용해서 구했는데 이 두가지와는 성격이 달라 그대로 적용할 수 없었다.

영문 위키 Partition(Number Theory) 항목의 Restrcted partition을 잘 이해하면 적용 가능할 것 같은데 이제는 중학교 수준 이하의 실력을 가진 상황에 그 부분을 이해하고 프로그래밍 하는 것이 쉽지 않았다.

그래서, 31번, 76번 문제 모두에 적용가능했던 동적 프로그래밍 방법을 가져와 소수에 맞게 조금 응용해서 해결했다. 정답을 맞췄지만 내 것으로 소화한 것이 아니어서 찝찝함이 남는다.

It is possible to write five as a sum in exactly six different ways:

    4 + 1
    3 + 2
    3 + 1 + 1
    2 + 2 + 1
    2 + 1 + 1 + 1
    1 + 1 + 1 + 1 + 1

How many different ways can one hundred be written as a sum of at least two positive integers?

합계로 5를 나타내는 방법은 다음과 같이 6가지가 있다:

    4 + 1
    3 + 2
    3 + 1 + 1
    2 + 2 + 1
    2 + 1 + 1 + 1
    1 + 1 + 1 + 1 + 1

100을 2개 이상 숫자의 합으로 표시하는 데에는 몇가지 방법이 있는가?

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

예시를 제외하면 문제는 2줄 밖에 안되지만, 막상 구현하려 하면 간단한 것이 아니었다. 문제31의 변형이어서 그 때 사용한 방법을 적용하려 보니 31번에서는 8종류의 동전을 이용하는 8중 반복문을 이용해서 구현했는데, 이 문제는 그 경우 99종류의 동전이 있기 때문에 99중 반복문을 구현해야 가능한 것이었다. 그렇게 해결할 수도 있겠지만 문제에서 원하는 방법이 그것이 아니어서 고민을 많이 했는데 해결책이 떠오르지 않아 많이 애를 먹었다.

가장 간단하게 해결하는 것은 동적 프로그래밍을 이용하는 것인데, 다른 사람이 해결한 코드를 보면 간단하지만 왜 그렇게 답이 나오는지 이해가 되지 않아 많이 난감했다.

그래서 관련 내용을 추가로 찾아보니 이 문제는 정수론(number theory)이나 이산수학(Discrete Mathematics)에서 다루는 분할수(Partition Number) 문제라고 한다. 답을 구하는 방법으로 오일러의 오각수 정리, 하디-라마누잔-라데마커 공식과 같은 것이 있는데 오일러의 오각수 정리를 이용해서 답을 구했다. 위키피디아 보다는 나무위키의 분할수 항목에 프로그램으로 구현 가능하도록 공식이 나와 있어 그것을 이용했다.

Each of the six faces on a cube has a different digit (0 to 9) written on it; the same is done to a second cube. By placing the two cubes side-by-side in different positions we can form a variety of 2-digit numbers.

For example, the square number 64 could be formed:

In fact, by carefully choosing the digits on both cubes it is possible to display all of the square numbers below one-hundred: 01, 04, 09, 16, 25, 36, 49, 64, and 81.

For example, one way this can be achieved is by placing {0, 5, 6, 7, 8, 9} on one cube and {1, 2, 3, 4, 8, 9} on the other cube.

However, for this problem we shall allow the 6 or 9 to be turned upside-down so that an arrangement like {0, 5, 6, 7, 8, 9} and {1, 2, 3, 4, 6, 7} allows for all nine square numbers to be displayed; otherwise it would be impossible to obtain 09.

In determining a distinct arrangement we are interested in the digits on each cube, not the order.

{1, 2, 3, 4, 5, 6} is equivalent to {3, 6, 4, 1, 2, 5}
{1, 2, 3, 4, 5, 6} is distinct from {1, 2, 3, 4, 5, 9}

But because we are allowing 6 and 9 to be reversed, the two distinct sets in the last example both represent the extended set {1, 2, 3, 4, 5, 6, 9} for the purpose of forming 2-digit numbers.

How many distinct arrangements of the two cubes allow for all of the square numbers to be displayed?

두 개의 육면체의 각 면에 0~9 사이의 글자가 있는 경우, 두 육면체를 나란히 두면 다양한 2자리 숫자를 만들 수 있다.

예를 들어, 제곱수인 64는 아래와 같이 만들어진다:

실제로, 두 육면체의 숫자를 잘 정하면 100 이하의 모든 제곱수를(01, 04, 09, 16, 25, 36, 49, 64, 81) 표시할 수 있다.

예를 들어, 한 육면체에 {0, 5, 6, 7, 8, 9}, 다른 육면체에 {1, 2, 3, 4, 8, 9}가 있으면 모든 제곱수를 표시하는 한 방법이 된다.

그러나, {0, 5, 6, 7, 8, 9}와 {1, 2, 3, 4, 6, 7}가 9개 제곱수를 모두 표현하기 위해서는 6, 9는 아래위가 뒤집힌 경우를 허용해야 한다. 그렇지 않으면 09를 만들 수 없다. 유일한 배열을 결정하기 위해 각 육면체의 배열은 중요하지만 순서는 아니다.

{1, 2, 3, 4, 5, 6}과 {3, 6, 4, 1, 2, 5}은 동일하다.
{1, 2, 3, 4, 5, 6}과 {1, 2, 3, 4, 5, 9}은 서로 다르다.

그러나, 6과 9가 뒤집어지는 것을 허용했으므로, 마지막 예시 두 가지 모두 2자리 수를 만들기 위한 확장된 집합인 {1, 2, 3, 4, 5, 6, 9}를 나타내고 있다.

제곱수를 표시할 수 있는 서로 다른 육면체 배열은 몇 개 있는가?

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

문제 지문이 긴데, 두 수를 조합해서 제곱수(01, 04, 09, 16, 25, 36, 49, 64, 81)을 만들어낼 수 있는 주사위 번호 조합이 몇가지 만들 수 있는지에 대한 질문이다. 처음에 하나는 10의 자리, 다른 하나는 1의 자리를 두는 조합을 생각했는데, 문제에서 요구하는 것은 주사위가 특정 자리에 고정되지 않고 제곱수를 만들어 낼 수 있는 조합을 요구하기 때문에 조금 더 고민을 해야 되었다.

순서가 다르더라도 동일하다고 했으므로 10개의 숫자(0~9)에서 6개 숫자를 뽑는 조합으로 리스트를 만들고, 두 조합 리스트(주사위 2개)에서 제곱수가 만들어지는 경우를 확인할 수 있도록 했다. ₁₀C₆에 해당하는 조합 크기가 210이어서 생각보다 크지 않고, 이 문제를 해결하기 위한 새로운 알고리즘이 있을 것 같지는 않아서 반복문 2개를 이용하는 전수조사(라고 좋게 표현했지만 brute force) 방식으로 해결하기로 했다.

6, 9를 동일한 경우로 판정하는 것은 어렵지 않았는데 오답으로 판정되어 문제의 원인을 찾느라 여러가지 방법을 적용해보느라 해결하는데 시간이 많이 걸다. 실제 문제가 된 것은 두 주사위를 독립사건으로 보고 210x210의 전수 대상으로 조사했지만 이 경우 문제에서 예시로 제시한 {0,5,6,7,8,9}, {1,2,3,4,8,9}와 {1,2,3,4,8,9}, {0,5,6,7,8,9}를 두 번 계산하기 때문에 결과값이 크게 나오고 있었고, 이 부분이 중복되지 않도록 조정하고 나서 정답을 구할 수 있었다.

문제 요구조건을 잘못 이해해서 시간이 많이 걸렸어도 복잡한 알고리즘을 요구하는 문제는 아니었는데, 나중에 확인해보니 처음으로 해결한 40% 난이도의 문제였다.

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 21 elements in this set.

How many elements would be contained in the set of reduced proper fractions for d ≤ 1,000,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

이 집합에는 21개 원소가 있는 것을 알 수 있다.

d가 1,000,000 이하일 때, 약분된 진분수에는 몇 개의 원소가 있는가?

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

71번 문제에서 몇글자 다른데 전혀 다른 문제가 되어 있다. 71번과 마찬가지로 분자가 분모보다 작고, 분자와 분모의 최대공약수가 1이 되는 분수 집합을 전제로 하고, 이번 문제에서는 그런 약분된 진분수가 분모가 1,000,000 이하인 경우 몇 개 있는지 물어보고 있다.

71번 문제에서는 전체 분수 값이 정렬된 상태를 요구했지만, 이번 문제는 정렬하는 과정 없이 답을 구할 수 있으므로 조금 더 쉽게 접근이 가능할 것 같다. 특정 분모 숫자에 대한 공약수가 1인 분자의 갯수는 69번 문제, 70번 문제를 해결할 때 사용했던 Φ(n)을 구하는 것과 동일하다. 다만, 69, 70번은 특정 조건을 만족하는 소수를 대상으로 계산하면 되었지만, 이번 문제는 가능한 분모 전체를 대상으로 구해야 하기 때문에 시간을 더 많이 요구하고 있다.

기존 문제에 사용한 방법을 이용해서 계산해봤지만, 1만개 계산에 6분 이상 소요되면서 전체를 계산하려면 최소 10시간 이상이 필요할 것으로 전망되어 다시 난감함을 느끼게 되었다. 특정 숫자에 대한 파이값을 계산하는 공식을 구글링을 통해 찾아 적용했는데(예를 들어 3과 5가 약수인 Φ(75)=75*(1-1/3)*(1-1/5)), 그래도 생각보다 시간이 많이 소요되었다. 몇가지 최적화를 해서 2시간 이상 실행 끝에 오답을 구했다.

각 숫자를 소인수분해 해서 공식을 적용했는데 프로그램을 잘 못 구성했는지 오답이 나왔고, 발상의 전환을 해서 소수가 나오면 해당 수(i)의 모든 배수를 대상으로 미리 (i-1/i)를 곱하는 형태로 구현했더니 기존 시간에 비해 터무니없이 빠르게 정답을 구할 수 있었다.

51번 이후에는 문제들은 이해되고 해결방안을 구현 가능하지만 극심한 성능문제가 발생하는 경우가 많이 나오고 있다. 단순 알고리즘 구현보다는 정수론 같은 수학을 이해하고 그것을 기반으로 효율적인 알고리즘 구현이 필요한 상황이 나오고 있어서, 수학공부까지 하면서 파이썬 공부를 위해 오일러 프로젝트를 계속 할 것인지 고민하는 상황이 계속 나오고 있는 것 같다.

Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of positive numbers less than or equal to n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6.
The number 1 is considered to be relatively prime to every positive number, so φ(1)=1.

Interestingly, φ(87109)=79180, and it can be seen that 87109 is a permutation of 79180.

Find the value of n, 1 < n < 10⁷, for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum.

(파이 함수라고도 부르는) 오일러의 토션트 함수 φ(n)은 n에 대해 상대적으로 소수인 n보다 작거나 같은 양의 정수를 결정하는 함수이다. 예를 들어, 1, 2, 4, 5, 7, 8은 9보다 작으면서 9에 대해서는 소수이므로 φ(9)=6이다.

1은 모든 양의 정수에 대해 상대적으로 소수이므로, φ(1)=1이다.

흥미롭게도 φ(87109)=79180이며, 87109는 79180의 순열이다.

n이 1보다 크고 10⁷보다 작을때, φ(n)이 n의 순열이며, n/φ(n)이 최소인 n을 구하시오.

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

문제가 그렇게 까다롭게 보이지는 않았는데, 50번 이후 문제 대부분이 그렇듯이 1~1천만까지 있는 숫자 중에서 답을 구해야 되는 덕분에 실행시간이 많이 필요하므로, 통상적인 방법으로 시간을 들여 답을 구하거나, 숨어 있는 수학이론을 찾아 빠른 시간 내에 답을 구해야 한다는 것이 실제 문제였다.

69번 문제를 생각해보면, n/φ(n)가 최대인 경우는 n이 크면서, φ(n)이 작은 경우를 구하기 위해, 소수인 약수가 가장 많은 경우를 구해서 해결했다. 70번 문제는 정반대인 n/φ(n)이 최소인 경우를 묻고 있으므로, n이 작으면서 φ(n)이 큰 경우이며, 이 경우를 충족하려면 2개의 소수가 약수인 경우가 될 것이다 (자신이 소수인 경우는 1 작은 수가 순열이 되지 않아 제외). 2개의 소수가 편차가 작을수록 값이 작아질 것이기 때문에 √10000000(천만, 10⁷)인 3300 전후의 두 숫자가 조건을 만족할 것으로 추정되었는데, 자신이 없어서 천~만 사이의 두 소수를 곱해서 나오는 값(n)의 φ(n)이 n의 순열이 되면서 n/φ(n)이 최소인 값을 구하는 과정을 통해 답을 구할 수 있었다.

처음에는 φ(n)을 구하면 순열을 만들어서 n이 있는지 확인했는데, n과 φ(n)을 리스트로 만들어 정렬해서 두 값이 같은지 비교하는 것이 훨씬 빠르게 순열 여부를 확인할 수 있었다.

Euler's Totient function, Φ(n) [sometimes called the phi function], is defined as the number of positive integers not exceeding n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than or equal to nine and relatively prime to nine, Φ(9)=6.

It can be seen that n=6 produces a maximum n/Φ(n) for n≤10.

Find the value of n≤1000000 for which n/Φ(n) is a maximum.

오일러의 파이 함수(Totient function)인 Φ(n)은 n보다 크지 않고, n에 대해 상대적으로 소수인 양의 정수로 정의된다. 예를 들어, 1, 2, 4, 5, 7, 8은 9보다 작고, 9에 대해 상대적으로 소수이므로 Φ(9)=6이다.

위 표에서 보듯이 n이 10이하일 때, n/Φ(n)이 최대값인 것은 n=6인 경우이다.

n이 1백만 이하일 때, n/Φ(n)이 최대가 되는 값을 구하시오.

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

상대적으로 소수(relative prime)라는 표현이 재밌었는데, n을 (1일 제외하고) 나눌 수 없는 수로 이해했다. 8의 경우를 보면 8을 나눌 수 있는 2와, 2의 배수인 4, 6을 제외하고, 10의 경우에는 2의 배수인 2, 4, 6, 8과 5를 제외한 수가 된다.

처음에는 소수의 경우에는 n에서 1을 뺀 값(자신을 제외한 모든 수가 나눌 수 없으므로), 소수가 아닌 경우에는1~n-1까지 숫자 중 n을 나눌 수 있으면, 그 수의 배수까지 카운트해서 n에서 카운트한 값을 빼는 형태로 Φ(n)을 구했는데, 8에서 앞의 표가 다르게 Φ(n)=3이 나왔다. 원인을 찾아보니 2의 배수로 3을 카운트했는데(2, 4, 6), 1씩 더하면서 확인할 때 4도 8을 나눌 수 있는 숫자이므로 2번 카운트 된 것으로 분석되었다.

중복 계산되는 경우를 막기 위해, 간단하게 카운트를 통해 계산하는 방법을 포기하고, 매번 1~n-1까지 리스트를 만들고, n을 나눌 수 있는 숫자와 그 수의 배수를 리스트에서 삭제해 나가는 느리지만 정확하게 계산할 수 있는 방법으로 구현했다. 이번에도 처리속도가 문제였다. 짝수면 홀수만으로 리스트를 만드는 식으로 성능개선을 했지만, 큰 수가 나오면 느리긴 마찬가지였다.

가만히 관찰해보니 (자신을 제외하고 나눌 수 있는 수가 없으므로)  소수의 경우 Φ(n)이 커지고, n/Φ(n)은 작아지게 되어 있고, 해당되는 수의 (소수인) 약수가 많아질수록 n/Φ(n)이 커지고 있었다. 실행시간이 너무 길어져서 중간에 포기했지만, 최고값을 경신하는 경우는 2, 6, 30, 210, 2310, 30030이었는데 이것을 다시 보면 2, 2x3, 6x5, 30x7, 210x11, 2310x13으로 소수를 차례로 곱해가는 경우였다.

그래서, 백만보다 크지 않은, 연속된 소수의 곱을 구하니 답이 되었다.

For a number written in Roman numerals to be considered valid there are basic rules which must be followed. Even though the rules allow some numbers to be expressed in more than one way there is always a "best" way of writing a particular number.

For example, it would appear that there are at least six ways of writing the number sixteen:

    IIIIIIIIIIIIIIII
    VIIIIIIIIIII
    VVIIIIII
    XIIIIII
    VVVI
    XVI

However, according to the rules only XIIIIII and XVI are valid, and the last example is considered to be the most efficient, as it uses the least number of numerals.

The 11K text file, roman.txt (right click and 'Save Link/Target As...'), contains one thousand numbers written in valid, but not necessarily minimal, Roman numerals; see About... Roman Numerals for the definitive rules for this problem.

Find the number of characters saved by writing each of these in their minimal form.

Note: You can assume that all the Roman numerals in the file contain no more than four consecutive identical units.

로마 숫자로 쓰인 숫자는 기초 규칙만 지키면 유효하다고 고려된다. 아래 규칙은 어떤 숫자는 한 가지 이상 방법으로 표현될 수 있지만, 특정 숫자를 나타나는 "가장 좋은" 방법은 늘 존재한다.

예를 들어, 16을 표현하는 데 다음과 같이, 적어도 6가지 방법은 있다.

    IIIIIIIIIIIIIIII
    VIIIIIIIIIII
    VVIIIIII
    XIIIIII
    VVVI
    XVI

그러나, 규칙에 의해 XIIIIII와 XVI만 유효하고, XVI가 가장 적은 숫자를 사용하므로 가장 효율적인 것으로 고려된다.

11K 텍스트 파일 roman.txt (우클릭하고 "다른 이름으로 링크 저장")에는 1천개의 유효한 로마 숫자가 있지만, 가장 적은 숫자는 아니다; 구체적인 규칙을 위해서는 About... Roman Numerals 를 참조하라.

최소화 된 형태 바꾸었을때 줄어든 글자의 갯수를 구하시오.

주의: 파일에 있는 로마 숫자는 4개 이상 연속된 숫자가 없다고 가정할 수 있다.

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

자주 보면서도 몰랐던 로마 숫자인데 그것을 응용하는 문제가 나왔다. 참조를 보면 I=1, V=5, X=10, L=50, C=100, D=500, M=1000이며, ①큰 수에서 작은 수로 쓰여지고, ②M, C, X는 동일한 작은 수로 표현되지 않으며, ③D, L, V는 한 번만 나오는 것이 규칙으로 되어 있다. 예시 설명에서, XIX(19)는 맞지만 IXX(9, 10)은 안되고(①위반) VVVIIII 안되며(③위반), XIIIIIIIII, XVIIII보다는 XIX를 선호(최소화)하는 것으로 되어 있으며, 4는 IIII보다는 IV, 9는 VIIII보다는 IX, 40은 XXXX보다는 XL, 90은 LXXXX보다는 XC, 400은 CCCC보다는 CD, 900은 DCCCC보다는 CM형태가 최소화되므로 선호하는 것으로 되어 있다.

문제에서는 roman.txt에 있는 로마 숫자를 최적화하고, 그 과정에서 몇 글자나 줄었는지 구하라고 요구하고 있는데, 영어가 짧은 덕에 2가지를 잘못 전제하고 시작했다. 모든 roman.txt의 숫자가 최적화되지 않은 상태에 있으므로, 최적화시킨 단어 갯수를 구하라고 이해했던 것이다.

모든 roman.txt 숫자가 최적화되지 않았다고 생각했기 때문에 단순하게 읽히는 로마 숫자를 아라비아 숫자로 단순변환시켜 로마숫자로 최적화고, 바뀐 단어수를 구했는데 오답이 나왔다. 아무래도 문제를 잘 못 이해해서 엉뚱하게 풀었던 것 같아서 찾아보니 위와 같은 답을 요구하고 있었다.

그 말은, 복잡하게 아라비아 숫자로 변환할 필요 없이 (문제 마지막에서 같은 문자가 4개 이상 없다고 전제했으므로) 900, 400, 90, 40, 9, 4에 해당하는 로마 숫자를 최적화시키고 그 과정에서 몇 글자나 줄어들었는지만 구하면 되는 문제였다. 수학 지식보다는 문자열 조작만 잘 하면 되는 것이어서 문제에서 제시한 난이도보다는 쉽게 해결 가능했다.

Consider quadratic Diophantine equations of the form:

    x² – Dy² = 1

For example, when D=13, the minimal solution in x is 649² – 13×180² = 1.

It can be assumed that there are no solutions in positive integers when D is square.

By finding minimal solutions in x for D = {2, 3, 5, 6, 7}, we obtain the following:

    3² – 2×2² = 1
    2² – 3×1² = 1
    9² – 5×4² = 1
    5² – 6×2² = 1
    8² – 7×3² = 1

Hence, by considering minimal solutions in x for D ≤ 7, the largest x is obtained when D=5.

Find the value of D ≤ 1000 in minimal solutions of x for which the largest value of x is obtained.

다음 형태의 디오판토스 방정식을 생각해 보자:

    x² – Dy² = 1

예를 들어, D=13일 때, x가 최소가 되는 답안은 649² – 13×180² = 1이다..

D가 제곱수일 때 양의 정수에서 답안이 없다는 것은 예상 가능하다.

D={2, 3, 5, 6, 7}일 때 x의 최소 답안을 찾으면 다음과 같다:

    3² – 2×2² = 1
    2² – 3×1² = 1
    9² – 5×4² = 1
    5² – 6×2² = 1
    8² – 7×3² = 1

즉, D가 7보다 작거나 같은 경우 x의 최소값 답안에서, 가장 큰 x 값은 D=5일 때 구해진다.

D ≤ 1000일 때 x의 최소값 답안에서 가장 큰 x 값을 구하시오.

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

위키피디아에서는 디오판토스 방정식(Diophantine equation)을 2개 이상의 미지수와 정수 계수가 있는 다항식으로 설명하고 있다. 디오판토스 방정식 자체는 일반적인 방정식을 이야기하는데, 이 문제에서는 좀 더 특수한 경우를 설명하고 있고, 이것을 펠 방정식(Pell's equation)이라 부른다고 한다.

처음에는 x=(1+Dy²)**0.5를 이용해 계산했으나 실수부분 오차로 오답을 계산해내서, 정확한 계산을 위해 x²과 1+Dy²을 바로 비교했고, y를 1부터 시작하지 않고 x/√d 부터 시작하게 해서 계산 시간을 줄였다. 그렇게 해도 x가 17억 이상이 되는 d=61인 경우에는 시간이 6000초 이상 걸리는 등 많은 시간이 필요했지만, 이전보다는 좀 더 빠르게 동작했다.

그래도, 시간이 너무 많이 걸려서 검색해 보니 정답을 구하기 위해서는 x값을 16x10³⁶ 넘게 계산해야 된다고 한다. 위키피디아 문서를 보면 펠 방정식에 해결을 위한 4가지 방법(연분수(fundamental solution via continued fractions), 연분수에서 나온 추가 방법(additional solutions from fundamental solution), 빠른 알고리즘(concise representation and faster algorithms), 퀀텀 알고리즘(quantum algorithm))을 제시하고 있는데, 이 방법을 적용하지 않고 통상적인 방법으로는 답을 구할 수 없는 것을 확인하고, 연분수의 이해를 돕는 64번, 65번 문제를 해결한 이후에 다시 풀어보았다.

문제를 D를 기준으로 다시 보면 √D=√(x²-1)/y가 되고, 이는 연분수의 형태와 비슷하게 된다. 그래서, D를 기준으로 1000까지 반복하면서 연분수로 나오는 숫자(x, y)를 대입해서 공식(x²-Dy²=1)을 충족하는 경우를 찾았더니 몇 시간을 기다려도 답을 구하지 못하던 것을 0.5초도 되지 않아 구할 수 있었다.

다만, 연분수 계산을 위해 2번째 이전 x, y값을 알고 있어야 되어서 프로그램이 길어지게 되었는데, 파이썬 특성을 잘 살리면 좀 더 간결하게 프로그래밍 가능했을 것 같다.

모든 제곱근은 연분수로 나타낼 때 주기적이며, 위 형태로 나타낼 수 있다:

예를 들어, √23을 생각해 보자:

이것을 반복하면 위와 같은 확장을 구하게 된다:

이 과정은 위와 같이 요약될 수 있다:

이 순서가 반복되는 것을 볼 수 있다. 간결함을 위해, (1,3,1,8)이 무한히 반복하는 것을 나타내도록 √23=[4; (1,3,1,8)]로 표기한다.

처음 10개의 (무리수인) 제곱근을 연분수로 나타내면:

    √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

    √6=[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이 1만 이하일 때 주기가 홀수인 연분수는 몇 개인가?

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

뒤에 나오는 여러 문제에서 연분수 개념을 응용해야 빨리 풀 수 있기 때문에 해결의 필요성을 많이 느끼고 있던 것이다. 다시 이 문제를 풀면서도 어렵게 느껴지는 것이, 신기하게도 수기로 연분수의 반복을 계산하면 따라가지는데, 그것을 프로그램에 반영하려 하면 이상하게 논리가 꼬이는 것이다. 몇 시간을 들여다보고 다른 방법으로 접근하는데도 이상하게도 논리가 꼬이면서 진행이 되지 않는다.

논리가 꼬이게 된 이유 중 하나는, 위 √23 예시 a₁의 3번째에서 7과 14를 약분하는 것과 4번째에서 그냥 계산하면 나오는 1+(√23+1)/2를 음수로 바꿀 때 2+(√23-1)/2가 아니고 3+(√23-3)/2이 되는가였는데, 아무리 고민해도 해결되지 않아 인터넷의 힘을 빌리기로 했다.

문제를 해결했던 다른 사람이 이용한 앞 숫자, 분모, 분자를 구하는 공식을 이용해서 해결할 수 있었다. 다만, 연분수 문제가 뒤에도 많이 연관되어 있는데 이해하지 못하고 기계적으로 해결을 해야할 상황이 되어서 조금 슬펐다.

Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers are all figurate (polygonal) numbers and are generated by the following formulae:

The ordered set of three 4-digit numbers: 8128, 2882, 8281, has three interesting properties.

1. The set is cyclic, in that the last two digits of each number is the first two digits of the next number (including the last number with the first).
2. Each polygonal type: triangle (P_3,127=8128), square (P_4,91=8281), and pentagonal (P_5,44=2882), is represented by a different number in the set.
3. This is the only set of 4-digit numbers with this property.

Find the sum of the only ordered set of six cyclic 4-digit numbers for which each polygonal type: triangle, square, pentagonal, hexagonal, heptagonal, and octagonal, is represented by a different number in the set.

삼각수, 사각수, 오각수, 육각수, 칠각수, 팔각수는 모두 다각수(figurate numbers, polygonal numbers)이고, 다음 공식에 따라 만들어진다:

순서가 있는 3개의 네 자릿수 8128, 2882, 8281은 다음의 흥미로운 속성을 가지고 있다.

1. (마지막 숫자와 첫 숫자를 포함하여) 각 숫자의 마지막 두 자리가 다음 숫자의 처음 두 자리가 되는 형태로 순환한다.
2. 각 다각 형태인 삼각수(P_3,127=8128), 사각수(P_4,91=8281), 오각수(P_5,44=2882)는 집합의 서로 다른 숫자로 표현된다.
3. 이러한 속성을 가지는 유일한 네 자리 숫자이다.

6개 네 자리 숫자가 서로 다르고 각 숫자가 다각 형태인 삼각수, 사각수, 오각수, 육각수, 칠각수, 팔각수인 순서가 있는 네 자리 숫자의 합을 구하시오.

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

다각수(삼각수,사각수,오각수,육각수,칠각수,팔각수) 값이 순환하는 경우를 찾으라고 되어 있지만, 다각수의 순서가 정해져 있지 않다. 각 다각수의 네 자릿수 갯수는 96, 68, 56, 48, 43, 40개인데 이 조합만 해도 매우 큰데, 거기에 순서까지 생각하면 경우의 수가 매우 많아진다.

그러다 보니, 전체 순서 반복문에, 다각수 각각의 반복문이 중첩되어 7번 중첩되는 반복문 형태로 구성되었는데, 요즘 컴퓨터의 연산속도가 빨라서인지 생각보다 빠르게 답을 구할 수 있었다. map과 갈은 파이썬 고유 코드를 잘 활용하면 훨씬 간결한 코드로도 가능했을 것 같지만, for, if의 조합 만으로도 해결 가능했다.