윌런스의 공식

• 상위 항목: 수학 관련 정보, 정수론

1 개요

1964년에 수학자 윌런스(C.P.Willans)가 발표한 공식이다. 이 공식에 n을 대입하면 n번째 소수가 되는 공식이다. 공식은 다음과 같다.

[math]\displaystyle P_n=1+\sum_{m=1}^{2^n}\lfloor\sqrt[n]{n}\left(\sum_{x=1}^{m}\left\lfloor\cos^2\pi\frac{\left(x-1\right)!+1}{x}\right\rfloor)^{-\frac{1}{n}}\right\rfloor[/math]

굉장히 복잡해 보이지만 사실은 수학자의 재능낭비이다. 특히 n번째 소수를 찾는다는 것에서 대단해 보이지만 이 역시... 자세한건 결론 참조.

2 공식 제작 과정

윌런스의 공식에서 가장 핵심적인 부분은 윌슨의 정리이다. 윌슨의 정리를 살짝 변형하면 아래와 같은 정리를 얻는다.

1보다 큰 자연수 [math]x[/math]가 소수라는 것과 [math]\left(x-1\right)!+1[/math]이 [math]x[/math]의 배수라는 것은 동치이다.

윌슨의 정리에 의해 [math]\frac{\left(x-1\right)!+1}{x}[/math]라는 식은 [math]x[/math]가 1이거나 소수일 때는 정수, 그 외의 경우는 모두 정수가 아니다. 여기서 이 값에 [math]\pi[/math]를 곱하고 코사인값을 구하면, [math]x[/math]가 1이거나 소수일 때는 1 또는 -1이 되고, [math]x[/math]가 합성수인 경우에는 절댓값이 1보다 작은 수가 된다. 결국 [math]\cos\pi\frac{\left(x-1\right)!+1}{x}[/math]는 [math]x[/math]가 1이나 소수일 때만 -1 혹은 1이다.

이제 이 값을 제곱한 다음 가우스 기호를 붙인 함수를 [math]F\left(x\right)[/math]라 하면, [math]x[/math]가 1이거나 소수일 때 [math]F\left(x\right)=1[/math], [math]x[/math]가 합성수일 때 [math]F\left(x\right)=0[/math]이 된다. 즉, [math]\lfloor\cos^2\pi\frac{\left(x-1\right)!+1}{x}\rfloor[/math]는 [math]x[/math]가 1이거나 소수일 때만 1이 되고, 그렇지 않으면 0이 된다.

여기서 함수 [math]F\left(x\right)[/math]의 값을 [math]x=1[/math]부터 [math]x=m[/math]까지 차례대로 구해서 더하면, 그 값은 [math]m[/math]보다 작거나 같은 자연수 가운데 1과 소수의 개수가 된다. 따라서 [math]\pi\left(m\right)=-1+\sum_{x=1}^{m}F\left(x\right)[/math]와 같이 정의된 함수 [math]\pi\left(m\right)[/math]는 [math]m[/math]보다 작거나 같은 자연수 가운데 소수가 몇 개인지 세는 함수가 된다.

이제 [math]\pi\left(m\right)[/math]을 이용하여 [math]n[/math]번째 소수를 만드는 방법을 찾아야 한다. [math]m=1,2,3,\cdots[/math]에 대하여, [math]\pi\left(m\right)[/math]값이 [math]n[/math]이 되기 전까지는 1씩 더하고, [math]\pi\left(m\right)=n[/math]일 때부터 0을 더하면 [math]n-1[/math]값이 된다. 따라서 다음과 같은 함수를 정의한다.
[math]A_n\left(a\right)=\lfloor\sqrt[n]{\frac{n}{1+a}}\rfloor[/math]
이 함수는 [math]a[/math]가 [math]n[/math]보다 작을 때 1이 되고, 그렇지 않을 때는 0이 된다.

따라서 [math]P_n=1+\sum_{m=1}^{\infty}A_n\left(\pi\left(m\right)\right)[/math]를 계산하면 [math]1+1+1+\cdots+1+0+0+0+\cdots[/math]이므로 함수값은 [math]n[/math]번째 소수가 된다. 그런데 여기서 마지막에 0을 무한 번 더할 필요는 없으므로, 적당히 끊어줘야 한다. [math]n[/math]번째 소수가 [math]2^n[/math]보다 작다는 사실은 이미 알려진 사실이므로 식을 최종적으로 정리하면 다음과 같다.

[math]P_n=1+\sum_{m=1}^{2^n}\lfloor\sqrt[n]{n}\left(\sum_{x=1}^{m}\lfloor\cos^2\pi\frac{\left(x-1\right)!+1}{x}\rfloor\right)^{-\frac{1}{n}}\rfloor[/math]

3 결론

윌런스의 공식은 그 자체만 보면 신기할 수 있지만 공식을 계산하는 과정에서 결국 1부터 n까지 모든 수를 소수인지 아닌지 따져 보는 것과 같아서 에라토스테네스의 체보다도 비효율적이다. 게다가 이 공식은 소수에 관한 아주 간단한 성질조차 증명할 수 없을 정도로 무의미하기 때문에, 그냥 재미로 알아두기만 해도 된다. 안습

라고 하지만, 이 경우에 재능낭비라는 말은 잘못된 기대에서 비롯된 것인데, '소수를 찾는 공식이라길래 매우 효율적으로, 노가다없이 찾아주는 대단한 공식일 줄 알았는데, 그건 아니구나' 에서 비롯된 실망감에서 나온말이다. 하지만 이 공식은 소수를 비교적 짧은 수식으로 표현했다는 것만으로도 의의가 있는 것이다. 소수 뿐 아니라 이 세상의 어떠한 현상이나 사건을 수치화 하는 것 자체는 그것만으로도 수학적으로나 프로그램적으로 큰 의미가 있다. 아주아주 쉬운 예를 들어보자면, 어떤 응용문제를 마주쳤을 때, 이걸 대체 무엇을 x로 잡고 무엇을 어떻게 수식화하고 배열해야 내가 원하는 값을 얻어낼 수 있지? 라는 생각을 해본 적 있을 텐데, 그 이유는 애당초 세상의 일을 수식화를 먼저 해야 그걸 풀건 말건 할 수가 있기 때문이다. 소수의 경우에는 그 특유의 하나하나를 찾아내는 규칙은 없지만, 누구나 공유할 수 있는 규칙 덕분에 암호, 보안에 큰 도움이 될수 있는 개념 중 하나인데, 프로그램화가 가능한 공식을 만드는 것은 기술의 발달과 더불어 의미가 분명히 있는 것이다.

4 관련 항목

• 소수
• 에라토스테네스의 체
• 윌슨의 정리
• 재능낭비