책 이야기

이항계수 (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문 대상 리스트에서 숫자가 삭제되면서 인덱스 값이 모두 바뀌어서 엉뚱한 연산을 하는 상황이 생겼다. 상황을 보고도 어떤 문제 때문에 생기는 것인지 빨리 인지하지 못해서 오류를 해결하는 데 많은 시간이 걸렸다.

적어도 2개의 소수를 약수로 가지고 있는 수를 합성수라 한다. 예를 들어, 15=3x5, 9=3x3, 12=2x2x3이다.

(서로 다를 필요가 없는) 2개의 소수로 구성된 합성수는 30이하에 10개가 있다:

4, 6, 9, 10, 14, 15, 21, 22, 25, 26

10⁸보다 작은 n에 대해, (서로 다를 필요가 없는) 2개의 소수로 구성된 합성수는 몇 개인가?

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

1억 이하의 숫자 중에 2개 이상의 소수의 곱으로 구성된 합성수가 몇 개인지 묻는 문제이다. 문제에서 (서로 다를 필요가 없는)으로 설명된 부분은 동일한 소수로 곱해도 된다는 뜻이므로, 예시와 같이 9=3x3을 허용하게 구현하면 된다.

빠른 계산을 위해서 1억 이하의 소수 목록을 구하고, 2중 반복문에서 소수끼리 서로 곱하게 해서 목록을 구하고, 파이썬의 집합을 이용해서 중복을 제거해서 구했다. 1억 이하의 소수가 5백만 개 이상 나오더니 목록을 구하면서 메모리 에러가 발생했다. 생각보다 리스트가 커져서 문제가 생긴 것 같았다.

그래서, 결과값 리스트를 만들지 않고, 생성되는 합성수의 갯수를 구하도록 바꿔서 답을 구할 수 있었다. 소수 2개의 곱을 구하는 것이어서 다른 약수가 있을 수 없기 때문에 중복을 제거하는 과정이 필요없었다.

2⁷=128은 "12"로 시작하는 첫번째 2의 거듭제곱수이며, "12"로 시작하는 다음 2의 거듭제곱수는 2⁸⁰ 이다.

p(L,n)을 L로 시작하는 십진수 중 2^j가 n번째 가장 작은 j를 나타낸다고 정의하면, p(12,1)=7이고 p(12,2)=80이다.

또한 p(123,45)=70이다.

p(123,678910)을 구하시오.
--------------------------------------------------------------------------

문제에서 요구하는 대로 구성하면 프로그램의 구조는 간단하다. 2를 계속 곱해가면서 L로 시작되는 n번째 숫자를 찾아 거듭제곱수를 알려주면 된다.

이렇게 구현하면 예시로 나와있는 p(12,1), p(12,2), p(123,45)는 어렵지 않게 구할 수 있다. 하지만, 2의 거듭제곱수 중에서 123으로 시작하는 678910번째 숫자가 2의 몇 거듭제곱인지 찾는 것은 데이터 허용범위가 넓은 파이썬으로도 어려운 일이었다. (이번에는 4300자릿수 이상을 넘을 수 없다는 에러메시지를 봤던 것 같다)

프로젝트 오일러의 높은 번호 문제는 난이도가 낮아도, 간단히 해결 가능한 것이 아니라 (주로 상상도 못한 크기의 숫자로) 한계가 숨어 있고, 이것을 어떻게 해결해내는 것인지가 추가로 포함되어 있는 것 같다.

이번 문제에서는 앞의 3자리만 동일하면 되기 때문에, 일정크기 이상으로 커지면 앞의 3자리에 영향을 미치지 않을 아랫쪽 수를 10000으로 나눠 없애는 형태로 계산했는데, 정확한 숫자를 구하는 것이 아니어서 살짝 걱정되었지만 맞출 수 있었다.

0~9 사이의 숫자 d로 채워지는 4x4 크기의 격자가 있다.

그 격자는 위와 같이 나타낼 수 있으며, 예시에서 각 열과 행의 합은 12이고, 대각선의 합 또한 12이다.

0~9 사이의 숫자 d로 구성되는 4x4  격자에서 각 행, 열, 두 대각선의 합계가 동일한 경우는 몇가지가 있는가?

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

처음에는 기계적으로 중복순열을 만들어서 해결하려 했으나, 10¹⁶크기의 중복순열을 만들면서 메모리 에러가 발생했다.

그래서 격자의 (0,0)에서 (4,4)까지 a부터 p까지 자리기호를 매기고, (16차) 반복문으로 생성되는 숫자를 기준으로 첫 행의 가로 합계(sum=a+b+c+d)가 나머지 가로 합계(e+f+g+h, i+j+k+l, m+n+o+p), 세로 합계(a+e+i+m, b+f+j+n, c+g+k+o, d+h+l+p), 대각선(a+f+k+p, d+g+j+m)과 동일한 지 확인하도록 구성을 했는데, 10¹⁶ 크기만큼 반복을 하면서 시간이 대책없이 오래 걸리는 문제가 발생했다.

그래서, 고민을 하다 다른 사람이 해결한 방법을 검색해 봤는데, 변수 갯수를 줄이는 형태로 접근해서 실행시간을 개선하는 방법을 제시한 것이 있어 그 방법을 적용해 봤다. 앞 문단에서 설명한 것과 마찬가지 상황에서 sum=a+b+c+d로 했을 때,  가로 세로 합계 공식을 바꿔, h=sum-e-f-g, l=sum-i-j-k, p=sum-m-n-o, m=sum-a-e-i, n=sum-b-f-j, o=sum-c-g-k를 구할 수 있고, 대각선 공식을 이용하면 j=sum-d-g-m이 된다.

a, b, c, d, e, f, g, i, k에 대해 반복문을 구성하여, h, o는 반복문의 값으로 구하고, m을 먼저 구해서 j를 구하고, 그 값을 이용해서 l, p, n를 구할 수 있다. 대각선의 합계가 맞는지 확인하고(sum=a+f+k+p), 연산에 의해 구해진 값(h,j,l,m,n,o,p)이 0~9 사이의 값인 경우에 문제의 조건을 만족하는 경우가 된다.

이것을 반복문을 활용해서 계속 구해나가면 복잡도가 10¹⁶에서 10⁹로 1/10⁷이 줄어들어, 이전보다는 훨씬 빠르지만 그래도 답을 구하는 데는 시간이 좀 필요했다. 다만, 스스로 생각해서 끌까지 해결하지 못하고 다른 사람의 아이디어를 봐야 해결가능하다는 것이 씁쓸했다.

분자가 분모보다 작은 양의 분수를 진분수(proper fraction)라 한다.

어떤 분모 d에 대해 d-1개의 진분수가 있다. 예를 들어, d=12일때 진분수는 다음과 같다.
1/12,2/12,3/12,4/12,5/12,6/12,7/12,8/12,9/12,10/12,11/12.

약분되지 않는 분수를 탄력분수(resilient fraction)이라 부르자.

특정 분모 d에 대해 약분되지 않는 분자의 비율을 R(d)라 정의한다. 예를 들어, R(12)=4/11이다.

실제로, d=12는 R(d)<4/10인 가장 작은 분모이다.

R(d)<15499<94744인 가장 작은 분모 d를 구하시오.

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

약분되지 않는 분수를 학교에서는 기약분수(inreducible fraction)로 배웠는데, 여기에서는 무슨 차이가 있는지 모르겠지만 탄력분수로 정의하고 있다.

처음에는 모든 숫자를 대입해서 계산을 시도했는데, 시간이 너무 많이 걸렸다. 기약분수가 적은 경우를 찾는 형태여서 생각해보니 69번 문제를 변형한 문제처럼 보였다.

일단 많이 나눠주는 수의 곱으로 분모가 되어야 작아질 것이기 때문에 처음에는 짝수를 대상으로 시도했는데, 결과값 패턴을 보니 2와 3의 공배수인 6의 배수가 값이 작은 것이 보였다. 가만히 생각해보니 작은 소수의 곱으로 구성되는 숫자일수록 나눠지는 숫자가 많아 정답에 근접하게 나오게 되는 패턴을 찾았다.

그래서, 일단은 2에서 시작해서 나오는 소수의 곱을 대상으로, 배수를 5번씩 계산해서 정답보다 낮은 경우를 찾도록 했다.(예를 들어, 2의 경우 2,4,6,8,10, 2와3의 곱인 6의 경우 6,12,18,24,30, 2와3과5의 곱인 30의 경우 30,60,90,120,150 등을 계산하도록 했다)

소수의 곱은 생각보다 기하급수로 커졌고, 그 덕분에 정답 또한 생각했던 것 보다는 엄청 큰 값이었고, 답에 근접한 값만 계산하게 했어도 상당한 시간이 필요했다.