책 이야기

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가 제시되어 있으니, 그 이후로 값을 찾으면 실행시간을 좀 더 줄일 수 있을 것이다.