책 이야기

이항계수 (n k)는 위 그림과 같이 파스칼 삼각형이라 불리는 삼각형 형태로 나타낼 수 있다.

파스칼 삼각형의 첫 8줄은 12개의 서로 다른 수로 구성된다: 1, 2, 3, 4, 5, 6, 7, 10, 15, 20, 21, 35.

n이 제곱수로 나눠지지 않으면 양의 정수 n을 squarefree라 부른다. 파스칼 삼각형 첫 8줄의 서로 다른 12개 숫자 중에서 4와 20을 제외하고는 squarefree이다. 첫 8줄에서 sqarefree인 숫자의 합계는 105이다.

파스칼 삼각형 첫 51줄의 서로 다른 squarefree 숫자의 합을 구하시오.

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

생각가능한 몇 개의 단계로 나눠 답을 구했는데 그래도 25초 내외 시간 안에 답을 구할 수 있었다.

처음에는 파스칼 삼각형 모양의 리스트를 만들어가면서 서로 다른 숫자의 리스트를 구했다. 파스칼 삼각형 자체를 만들려고 했는데, 그것이 뒤에 다시 쓰이지 않기 때문에 파스칼 삼각형의 현재 행을 구하면서 서로 다른 숫자는 별도 리스트에 추가하는 형태로 했다.

서로 다른 숫자 리스트를 정렬하고, 그 최대값 이하의 제곱수 리스트를 만들었다. 서로 다른 숫자 리스트의 각 숫자에 대해 제곱수 리스트 숫자로 모듈러 연산(%)을 수행하고, 나머지가 0인 경우는 sqaurefree가 아니므로 해당하는 숫자의 리스트를 만들었다.

마지막으로, 서로 다른 숫자 리스트에서 squarefree가 아닌 숫자를 제외한 숫자를 모두 더해서 합계를 구했다.

그렇게까지 까다로운 문제는 아니었는데 2가지 오류때문에 해결하는데 시간이 좀 걸렸다. 하나는 51줄을 55줄로 잘못 설정해서 발생한 것이었는데 문제를 다시 읽고 해결할 수 있었다. 다른 하나는 2번째 단계에서 처음에는 나머지가 0인 경우에 서로 다른 숫자 리스트에서 해당하는 숫자를 삭제하는 형태로 해서 바로 결과를 구하도록 구성했는데, for문 대상 리스트에서 숫자가 삭제되면서 인덱스 값이 모두 바뀌어서 엉뚱한 연산을 하는 상황이 생겼다. 상황을 보고도 어떤 문제 때문에 생기는 것인지 빨리 인지하지 못해서 오류를 해결하는 데 많은 시간이 걸렸다.

회문인 숫자 595는 다음과 같이 연속된 제곱수의 합계로 나타낼 수 있다는 점에서 흥미롭다.

6²+7²+8²+9²+10²+11²+12²

천 이하에는 연속된 제곱수 합계로 나타낼 수 있는 회문이 11개 있고, 이들의 합계는 4164이다. 주의할 것은 1=0²+1²이지만 양의 정수의 합계를 고려하고 있으므로 해당하지 않는다.

10⁸(1억) 이하의 숫자 중에 회문이면서 연속된 제곱수의 합계로 나타낼 수 있는 숫자의 합을 구하시오.

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

회문은 4번 문제에서 처음 나온 이후에 오일러 프로젝트에 몇 번 나온 문제이고 여기까지 풀었으면 함수로도 가지고 있을 것이다.

일단 문제에서 요구한 대로 구현해 봤다. 1은 제외한다고 했으므로 2에서 1억까지 올라가면서 회문에 해당하는 숫자를 대상으로, 각 숫자가 연속된 제곱수의 합계로 나타낼 수 있는지 판별하는 것이다. 이를 위해 제곱수의 목록을 만들어두고 시작하는 자리를 이동해가면서 차례로 합해나가는 과정을 반복하도록 하고, 제곱수가 비교할 숫자보다 크면 그 수에 대해서는 검증을 중단하도록 했다.

실행해보니 처음에는 빠르지만 천만이 넘어가면서 실행속도가 엄청나게 느려지는 것이 보였다. 하지만 조금 기다려주면 끝이 나는 수준이어서 이렇게 해결하기로 했는데, 제곱수를 1억까지 만들었다가 그것이 넘는 경우가 필요해지면서 거의 마지막에 리스트의 인덱스 에러가 생기고 결과를 확인하지 못했다. 제곱수 리스트를 조금 더 크게 만든 후에 답을 구할 수 있었다.

하지만, 다른 사람은 어떻게 접근했는지 확인했을 때, 정반대로 접근하는 것이 있었는데 빠른 해결을 위해서는 좋은 방법 같아서 아이디어를 적는다. 접근을 반대로 해서, 1만의 제곱이 10억이므로, 1만 이하의 제곱수 목록을 만들고 각 숫자를  연속해서 나오는 결과 목록을 생성한 후에, 이 중 회문인 것만 답으로 선택하는 방법이다. 실험삼아 구현해봤는데, 결과 목록을 만드는 데 생각보다 많은 시간이 걸려 큰 차이가 나지 않을 것 같았다.

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

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값을 알고 있어야 되어서 프로그램이 길어지게 되었는데, 파이썬 특성을 잘 살리면 좀 더 간결하게 프로그래밍 가능했을 것 같다.

The 5-digit number, 16807=7⁵, is also a fifth power. Similarly, the 9-digit number, 134217728=8⁹, is a ninth power.

How many n-digit positive integers exist which are also an nth power?

5자리 수인 16807은 또한 5제곱 수이기도(7⁵) 하다. 비슷하게, 9자리 수인 134217728은 9제곱 수이다(8⁹).

n자리 제곱수이기도 한 n자리 양의 자연수는 몇 개 있는가?

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

숫자에서 범위를 명확하게 얘기하지 않아 고민하는 시간이 필요했다. 답을 구하는 알고리즘 자체는 각 숫자의 제곱수를 구해서(5의 경우 5, 25, 125, 625, ...), 각 숫자가 각 자리의 제곱수에 해당하는지 확인하면 된다. 예로 든 5의 경우 5의 1제곱은 5이므로 1자리 수, 5의 2제곱은 25로 2자리 수, 5의 3제곱은 125로 3자리 수이지만, 5의 4제곱은 625로 4자리 수가 아니다.

처음에는 n자리를 한자리 수로 생각해서 9의 9제곱까지만 구했는데 정답이 아니었다. 곰곰히 생각해 보니 상한을 두지 말고 구해야 하는 것이었고, 밑에 해당하는 숫자는 10의 1승은 2자리 수(10)이므로 9까지만 계산하면 되는 것이었다. 그렇게 코드를 수정하고 나서 정답을 구할 수 있었다.

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13 ≈ 62%.

If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

1에서 시작해서 반시계 방향으로 회전하는 정사각형을 구하면 한 변의 길이가 7인 것은 다음과 같다.

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

흥미롭게도 오른쪽 아래쪽 대각선에는 제곱수가 놓이고, 더욱 흥미있는 것은 두 대각선에 있는 13개 숫자 중 소수는 8개이며, 비율은 8/13≈ 62%이다.

회전하면서 둘러싸는 새로운 층을 만들면, 한 변의 길이가 9인 정사각형을 만든다. 이 과정이 계속될 때, 두 대각선에 있는 숫자 중 소수의 비율이 10% 이하가 되는 것은 언제인가?

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

1에서 오른쪽 아래에 대각선 방향에 있는 9, 25, 49, ... 는 제곱수이므로 소수가 아니다. 사각형이 커질 때마다 새롭게 검증 대상이 되는 숫자는 처음의 3, 5, 7, 두번째 13, 17, 21의 세 숫자씩이 된다.

대각선에 추가로 포함되는 3개 숫자 중 소수를 판별하고, 대각선 숫자 중 소수의 비율을 구하면 되므로 그렇게 까다롭지 않게 해결 가능하다.

It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

    9 = 7 + 2×1²
    15 = 7 + 2×2²
    21 = 3 + 2×3²
    25 = 7 + 2×3²
    27 = 19 + 2×2²
    33 = 31 + 2×1²

It turns out that the conjecture was false.

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

크리스티안 골드바흐는 모든 홀수 합성수는 소수와 제곱수를 2배한 수를 합하여 구할 수 있다고 제안하였다.

    9 = 7 + 2×1²
    15 = 7 + 2×2²
    21 = 3 + 2×3²
    25 = 7 + 2×3²
    27 = 19 + 2×2²
    33 = 31 + 2×1²

이 추측은 틀린 것으로 드러났다.

소수와 제곱수를 2배한 수의 합이 되지 않는 가장 작은 홀수 합성수는 무엇인가?

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

합성수를 이해하는 것이 필요한데, 1보다 크며 소수가 아닌 자연수를 합성수라고 한다. 다르게 이야기하면 소수는 약수가 2개이므로, 약수가 3개 이상인 자연수를 말하는 것이다.

홀수이면서 소수가 아닌 수(합성수)를 대상으로, 그 수보다 작은 제곱수의 2배(2, 8, 18, 32, ...)를 차례대로 빼고 남은 수가 소수인지 판별하는 과정을 반복해서 수행하면 된다. 다음 합성수를 찾을 때 중간에 발견되는 소수는 소수 리스트에 추가하고, 해당 합성수보다 작은 제곱수의 2배도 리스트로 만드는 형태로 해서 조금 더 효율적으로 수행하도록 했다.

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이 되는 특성을 활용하여 답을 구할수도 있을 것이다.