책 이야기

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

The nth term of the sequence of triangle numbers is given by, t_n = ½n(n+1); so the first ten triangle numbers are:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t₁₀. If the word value is a triangle number then we shall call the word a triangle word.

Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words?

삼각수 수열의 n번째 항은 t_n = ½n(n+1)이다. 따라서, 처음부터 열번째까지 삼각수는 다음과 같다:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

단어에 있는 각 글자를 알파벳 순서대로 번호를 매겨 값을 더하여 단어값을 구하게 된다. 예를 들어, SKY의 단어값은 19+11+25=55=t₁₀이다.단어값이 삼각수이면 그런 단어를 삼각 단어라 부른다. 

If the word value is a triangle number then we shall call the word a triangle word.

거의 2천개 영어단어가 있는 16K 크기의 문서 파일인 words.txt (우클릭하고 "(으)로 링크 저장")에는, 몇 개의 삼각수가 있는가?

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

파일을 읽어, 단어로 리스트를 구성하고, 각 단어를 읽어서 그 단어가 삼각수이면 카운트를 1씩 추가하는 것이 중심 알고리즘이다. 참고로, 삼각수는 12번 문제에서 한 번 나왔던 개념이다.

이를 구현하기 위해서는 파일을 열어 읽은 내용을 따옴표를 제외하고 문자열을 만드는 것이 첫번째이고, 딕셔너리를 이용해서 각 단어의 단어값을 구하는 것이 두번째이다. 삼각수 여부를 검증하는 것이 필요한데, 가장 긴 단어에 단어길이x26(Z의 값)까지 삼각수를 구한 다음에 각 단어의 단어값이 삼각수 리스트에 있는지 비교하는 방법으로 구현하였다.

삼각수 여부 검증하는 것을 달리 생각해보면 근의 공식을 활용하여 구할 수도 있다. n번째 항을 구하는 공식을 n을 기준으로 근의 공식을 적용하면 n=(-1+(1+8t_n)**0.5)/2가 된다. 원래는 +-이지만 이미 -1이 있는데 또 빼면 음수가 되므로 +인 경우만 계산하면 된다. 이렇게 해서 나오는 n이 자연수인 경우 그 단어는 삼각 단어가 되는 것이다.

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

 1: 1

 3: 1,3

 6: 1,2,3,6

10: 1,2,5,10

15: 1,3,5,15

21: 1,3,7,21

28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

삼각수 수열은 자연수를 더하면서 생성된다. 따라서, 7번째 삼각수는 1+2+3+4+5+6+7=28이다. 처음 10개 요소는 다음과 같다.

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

처음 일곱 개 삼각수의 인수를 나열해 보면,

 1: 1

 3: 1,3

 6: 1,2,3,6

10: 1,2,5,10

15: 1,3,5,15

21: 1,3,7,21
28: 1,2,4,7,14,28

28은 처음으로 5개가 넘는 약수를 가지는 수임을 알 수 있다. 500개 약수를 가지는 첫 삼각수는 무엇인가?

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

삼각수라는 단어가 익숙하지 않았는데, 1부터 시작하는 연속된 자연수의 합을 뜻한다고 한다. 인수를 구하는 함수를 작성하고, 반복문을 통해 인수가 처음으로 500개 이상인 삼각수를 구하면 된다.

좀 더 효율적으로 구하려면, 소수인 인수의 곱으로 나타내고, 제곱수를 이용하면 된다. 5번 문제와 연관있는 부분이기도 한데, 예를 들어 28은 2²x7¹이므로 제곱수는 각각 2, 1이며, 약수의 갯수는 (2+1)(1+1)=6이 되는 특성을 활용하여 답을 구할수도 있을 것이다.