책 이야기

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의 조합 만으로도 해결 가능했다.

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

It can be verified that T₂₈₅ = P₁₆₅ = H₁₄₃ = 40755.

Find the next triangle number that is also pentagonal and hexagonal.

삼각수, 오각수, 육각수는 다음 공식에 따라 생성된다:

T₂₈₅ = P₁₆₅ = H₁₄₃ = 40755임을 알 수 있다.

삼각수이면서, 오각수, 육각수인 다음 숫자를 구하시오.

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

이 문제를 해결할 때에는 근의 공식을 생각하지 못해서, n번째 생성되는 삼각수와 같은 오각수, 육각수는 n보다 작다는 속성을 이용해서 풀었다(15를 보면, 삼각수에서는 n=5일때지만, 육각수는 n=3일 경우 15임).

즉, n번째 삼각수, 오각수, 육각수 리스트를 만들면 삼각수와 같은 값이 오각수, 육각수에 있는지 찾는 것을 반복하는 것이다.

앞문제에서 근의 공식을 적용했던 것을 생각해 보면, n 기준으로 오각수는 n=(1+(1+24Pn)**0.5)/6, 육각수는 n=(-1+(1+8Hn)**0.5)/4가 되므로 삼각수를 구하고, 해당 값을 오각수, 육각수 공식에 대입해 결과가 자연수가 나오는지 확인하는 것이 좀 더 빠른 해결방법이 될 것 같다. 그리고, 285번째 삼각수인 4075가 제시되어 있으니, 그 이후로 값을 찾으면 실행시간을 좀 더 줄일 수 있을 것이다.

Pentagonal numbers are generated by the formula, P_n=n(3n−1)/2. The first ten pentagonal numbers are:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

It can be seen that P₄ + P₇ = 22 + 70 = 92 = P₈. However, their difference, 70 − 22 = 48, is not pentagonal.

Find the pair of pentagonal numbers, P_j and P_k, for which their sum and difference are pentagonal and D = |P_k − P_j| is minimised; what is the value of D?

오각수는 P_n=n(3n−1)/2 공식에 따라 생성된다. 처음 10개 오각수는 다음과 같다:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

P₄ + P₇ = 22 + 70 = 92 = P₈임을 알 수 있다. 그러나, 둘의 차이인 70 − 22 = 48은 오각수가 아니다.

두 수의 합과 차이가 모두 오각수이고 D = |P_k − P_j| 가 최소화되는 두 오각수 P_j and P_k를 찾으시오. D의 값은 얼마인가?

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

이 문제는 신기하게도 어렵지 않게 해결했는지 방법은 기억이 나지 않으면서, 어떻게 접근해야 할 지 난감한 것을 보니 상상하지 못할 단순하고 비효율적인 방법으로 해결했던 것 같다.

가능한 접근으로는, 오각수 리스트를 만들면서 새로운 오각수를 추가하면 기존 리스트의 숫자와 차이를 비교해 오각수가 되는 경우를 찾고 해당 경우에 합이 오각수인지 판별해 나가는 방법으로 답을 찾는 것이다. 예를 들면, (1, 5)가 있는 오각수 리스트에 다음 오각수인 12를 추가하고, 기존 오각수와 차이 11(12-1), 7(12-5)을 차례로 오각수인지 확인하고 만약 오각수인 경우 두 수의 합이 오각수인지 검증한다.

많이 비효율적이지만 답을 구했던 것 같고, 오각수인지 판별하는 것에는 33번 문제를 해결할 때 잠깐 언급했던 근의 공식을 이용해서 오각수 공식 P_n=n(3n−1)/2을 n 기준으로 바꾸면, n=(1+(1+24p)**0.5)/6이 된다. 이것을 활용하여 간단하게 확인 가능하다.