윌런스의 공식

1964년 수학자 윌런스(C. P. Willans)가 제안한 공식으로, $n$에 자연수를 대입하면 $n$번째 소수로 만드는 공식이다. 식은 다음과 같다.

난해하게 생긴 것에 비해 의외로 유도 과정에서 크게 어려운 부분은 없다. 관련된 개념만 알고 있다면 이해하기 어렵지 않다.

$\displaystyle\frac{(j-1)!+1}{j}$는 어떤 자연수가 소수인지를 판별하는 역할이다. 윌슨의 정리에 따르면 $(j-1)!+1$는 $j$가 1이거나 소수일 때는 나누어떨어지고, $j$가 합성수일 때는 나누어떨어지지 않는다. 따라서 $\displaystyle\frac{(j-1)!+1}{j}$가 정수인지 아닌지를 확인함으로서 $j$가 소수인지를 판별할 수 있다.

그 다음으로 정수를 1, 정수가 아닌 수를 0으로 변환하기 위해 삼각함수를 이용한다. 만약 $\displaystyle\frac{(j-1)!+1}{j}$에 $\pi$를 곱하고 코사인 함수에 대입한다면, $j$가 1이나 소수일 경우에는 1이나 -1이 되고, 합성수라면 그 사이의 수가 될 것이다. 이 수를 제곱해서 음수를 모두 양수로 만듦과 동시에 -1을 1로 변환하고 여기에 최대 정수 함수를 적용하면 1을 제외한 모든 값들은 0이 된다. 따라서 $\displaystyle\left \lfloor\cos^2\pi\frac{(j-1)!+1}{j}\right \rfloor$는 $j$가 1 혹은 소수라면 1이고, 아니라면 0이다.

이를 이용해서 $i$까지의 소수의 개수를 구하는 것이 가능하다. $i$까지 소수가 $n$개가 존재한다고 가정하면 $\displaystyle\left \lfloor\cos^2\pi\frac{(j-1)!+1}{j}\right \rfloor$에 1부터 $i$까지 모든 자연수를 대입했을 때 결과가 1인 경우는 $j$가 소수인 경우의 수는 $n$회와 1인 경우 1회까지 $n+1$이 된다. 따라서 $\displaystyle \sum_{j=1}^{i}\left \lfloor\cos^2\pi\frac{(j-1)!+1}{j}\right \rfloor$는 $i$까지의 소수의 수에 1을 더한 것임을 알 수 있다.

특정 수 이하의 소수의 수가 $n$ 미만이 아닌 경우가 나오게 하는 첫 번째 수는 $n$번째 소수이다. 3번째 소수를 예로 들면 자기 자신 이하의 소수의 수가 3 이상인 첫 번째 수는 3번째 소수인 5이다. $\displaystyle\left \lfloor(\frac{n}{a+1})^{\frac{1}{n}}\right \rfloor$는 $n\geq a+1$일 때 1과 2 사이이고 아니라면 0과 1 사이이므로 여기에 최대 정수 함수를 적용하면 각각 1과 0으로 변환된다. 그러므로 여기서 $a+1$를 $i$까지의 소수의 수보다 1 큰 수, 즉 $\displaystyle \sum_{j=1}^{i}\left \lfloor\cos^2\pi\frac{(j-1)!+1}{j}\right \rfloor$라고 생각하면 위 식은 $i$ 이하의 소수의 수보다 $n$이 (1 이상)더 크다면, 즉 $n$번째 소수가 $i$보다 크면 1이고 그렇지 않다면 0이다.

이제 이것을 시그마에 집어넣어 1부터 $2^{n}$[1]까지 계산해 보면, $n$번째 소수보다 1 작은 값까지 계속 1을 더하다가 $n$번째 소수부터는 0을 더하기 시작할 것이다. n이 3이라고 하면 8까지 확인해 보면 될 것이다. 자기 자신 이하의 소수의 수가 3 미만인 1~4까지는 1, 5~8까지는 0이므로 계산하면 $\displaystyle \sum_{i=1}^{2^{3}}\left \lfloor(\frac{3}{\sum_{j=1}^{i}\left \lfloor\cos^2\pi\frac{(j-1)!+1}{j}\right \rfloor})^{\frac{1}{3}}\right \rfloor=1+1+1+1+0+0+0+0=4$로, 3번째 소수보다 1 작다. 그러므로 윌런스의 공식에서 1을 뺀 값은 $n$번째 소수보다 1 작다. 여기에 1을 더하면 $n$번째 소수가 된다.

엄청나게 비효율적이다. 100번째 소수를 구하는 데만 해도 무려 시그마 안에 팩토리얼까지 들어 있는 $2^{100}$[2]개의 항을 계산해야 한다. 코딩을 해서 공식을 돌려도 시간이 매우 오래 걸린다. 사실상 모든 자연수 $n$에 대해 수작업으로 계산하는 것이 더 빠를 정도이며, 실용성이 전혀 없다고 볼 수 있다.

그렇기에 소수를 탐색하기 위한 목적보다는 일종의 수학 유머에 더 가까우며, 공식으로 만들었다는 것 자체에 의의를 두는 쪽에 가까운 셈이다.