10^20의 partition number를 계산하다

partition number는 주어진 수를 덧셈의 합으로 표현하는 경우의 수를 말한다.(up to order) 예를 들어 4의 경우 1+1+1+1, 1+1+2, 1+3, 2+2, 4의 다섯 가지가 있으므로 p(4)=5 가 된다.

그런데 문제는 주어진 값이 커지면 이 partition number를 계산하는 것이 녹록치 않게 되는데, Fredrik Johansson이라는 symbolic computation을 연구하는 친구가 p(1020)의 값을 정확히 계산한 모양[1]이다. 개인적으로 partition number는 그리 흥미가 많지 않았기 때문에, 이 친구의 포스팅에서 본인이 몰랐던 사실이 꽤 많이 나왔다. ㅎㅎ

p(1020)의 값은 물론 숫자 하나이지만, 이 친구에 따르면 그 데이터 크기는 무려 4.6GB에 달한다고 한다. 맨땅에 헤딩하듯이 그냥 컴퓨터를 돌린다면 우주가 멸망할 때까지 계산해도 모자란다. 이걸 대체 어떻게 계산했을까?

다행히 위키피디아에 따르면 p(n)에 수렴하는 하디-라마누전의 공식이 알려져 있다고 한다.

\displaystyle p(n)=\frac{1}{2 \sqrt{2}} \sum_{k=1}^v \sqrt{k} A_k(n) \frac{d}{dn} \exp \left({ \pi\sqrt{\frac23} \frac{\sqrt{n-\frac{1} {24}}}{k} } \right)

여기서

\displaystyle A_k(n) = \sum_{\substack{0 \le m < k \\ (m, k) = 1}} e^{ \pi i \left[ s(m,\, k) - \frac{1}{k} 2 nm \right]}

이고 S(m, k)는 Dedekind sum이라고 한다. 아씨 열라게 복잡하구만.

더욱이 Hans Rademacher는 1937년에 이 공식을 개량해서 다음과 같은 공식을 만들었다고 한다.

\displaystyle p(n)=\frac{1}{\pi \sqrt{2}} \sum_{k=1}^\infty \sqrt{k} A_k(n) \frac{d}{dn} \left({ \frac {1} {\sqrt{n-\frac{1}{24}}} \sinh \left[ {\frac{\pi}{k} \sqrt{\frac{2}{3}\left(n-\frac{1}{24}\right)}}\right] }\right)

사실 어디가 개량되었는지는 본인도 잘 모르는데-_- 아마 수렴 속도가 더 빨라진게 아닌가 싶다.

여하간 위 계산은 원주율 등 높은 정확도의 실수 연산과 더불어 큰 정수들의 modular arithmetic, 인수분해, GCD 등등 상당히 다양한 종류의 계산을 포함하고 있어 computational number theory의 스트레스 테스트나 벤치마킹에 꽤나 유용한 모양이다. 위 블로그 주인장은 이 공식을 이용하여 계산하였다고 한다.

재미있게도 Maple 12까지는 11269 이상의 몇몇 수에서 partition number가 위 공식의 반올림 근사 에러로 인해 부정확한 결과가 나왔던 모양인데, 이 sequence가 OEIS에 등록[2]되어 있다. Maple의 흑역사가 아닐까 ㅋㅋ

위 계산을 위해 110시간동안 130GB의 메모리를 사용했다고 하는데, 수의 사이즈 치고는 생각만큼 많이 들지는 않는 듯. 이 친구는 다음으로 1021에 도전할 모양이다. 켁.

 


[1] New partition function record: p(1020) computed by Fredrik Johansson
[2] http://oeis.org/A110375

Advertisements

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

%s에 연결하는 중