책 이야기

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