소수 공식 - 공식이 만능은 아냐 (navercast)

어제 게시된 네이버캐스트의 수학산책 주제는 소수를 만드는 공식.

보통 사람들에게는 아마도 "수학=공식"으로 인식되어서인지 "소수를 만드는 공식만 있으면 리만 가설도 해결할 수 있고, 어떤 암호도 다 풀 수 있다"는 식의 주장을 가끔 볼 수 있다.

당연히 말도 안 되는 생각이어서, 이번 글에서는 아예 n을 대입하면 n번째 소수가 나오는 공식에 대해 소개하였다. 그냥 소수를 만들어내는 공식이라고 해도 놀랄 판에, 정확히 n번째 소수를 만드는 공식이라고 하면  꽤 흥미로운 주제가 될 것 같았다. (zariski 님도 같은 내용을 소개한 적이 있다. 주소는 http://zariski.egloos.com/2541383 )

실은 처음에 네이버에 보냈던 원고는 더 길었는데, 수식이 너무 많다고 두 번째 공식에 대한 이야기는 잘렸다. 블로그에서는 그 두 번째 공식을 간단히 소개할까 한다.

네이버캐스트에 올린 (첫 번째) 공식은 소수 판정법을 억지로 하나의 공식으로 만든 형태인 반면, 아래에 소개할 공식은 소수 전체를 모아 하나의 수를 만든 다음, 적절하게 정보를 추출하는 방식이다.

먼저, 소수 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...을 이용하여 다음과 같은 수 a를 만든다.

a = 0.02030005000000070000000000000011000...

이 수는 n번째 소수 \(p_n\)에 \(10^{-2^n}\)을 곱해서 모두 더한 것이다. 일반적으로 n번째 소수는 \(2^n\)보다 작기 때문에, \(10^{-2^n}\)을 곱하면 a의 소수점 아래에 소수들이 겹치지 않게 나열할 수 있다.

이제 n번째 소수를 만들어내려면, \(10^{2^n}a\)를 계산한 다음 앞뒤 불필요한 부분을 날려버리면 된다. 그래서
\[ f(n) = \lfloor 10^{2^n}a \rfloor - 10^{2^{n-1}}\lfloor 10^{2^{n-1}}a \rfloor \]
로 정의하면, f(n)이 n번째 소수가 된다.

정말로 n번째 소수를 만들어내는 공식이기는 한데, 참 황당하기 짝이 없다. 이 방법으로 n번째 소수를 만들어내려면 일단 n번째 소수가 무엇인지를 알아야 하니까, 보통 생각하는 "공식"과는 전혀 다르다.

공식이라는 것은 어떤 알고리듬에 따른 최종 결과를 정리한 것에 불과하기 때문에, 결국 중요한 것은 공식이 아니라 알고리듬 쪽이라 할 수 있다. 그러니 소수를 만드는 (좋은) 공식이 없다는 말은 사실 소수를 만드는 (좋은) 알고리듬이 없다는 것과 마찬가지이다. 그럼에도 수학을 잘 모르는 사람들은 알고리듬이 아니라 공식만을 찾아 헤매곤 한다. 공식만 발견하면 모든 난제가 해결될 것처럼 생각하면서.

PS. (8/3 19:30) 그러니까 소수를 만드는 공식만 찾으면 필즈 메달을 받을 수 있다는 이상한 소리를 아직도 믿고 있는 사람들은 인류 역사에 길이 남을 위대한 초초초초초천재 double d 님처럼 이런 종류의 공식이 무의미하다는 걸 깨달아야 한다는 게 결론.