소수 계량 함수 π(x) 근사 계산기

x 이하 소수의 개수 π(x)가 x/ln x에 점점 가까워진다는 정리입니다. 1896년 아다마르와 드 라 발레 푸생이 각각 증명했습니다. 다만 「가까워진다」는 것은 두 값의 비가 1로 간다는 뜻이지 차이가 0으로 간다는 뜻이 아니어서, 개수의 차이 자체는 계속 커집니다.

생각보다 많이 어긋납니다. x = 100만에서 실제 78,498개인데 72,382개로 나와 7.8% 모자랍니다. x = 10억에서도 5.1% 모자랍니다. 상대오차가 대략 1/ln x 규모로만 줄어들기 때문에 x를 10배로 키워도 오차가 몇 %포인트밖에 나아지지 않습니다.

소수의 밀도가 구간마다 다르다는 것을 반영하기 때문입니다. x/ln x는 밀도를 맨 끝의 값 하나로 대표하는데, 앞쪽 구간은 소수가 더 촘촘해서 그만큼이 통째로 빠집니다. li(x) = ∫dt/ln t는 구간 내내 변하는 밀도를 쌓으므로 그 손실이 없습니다. x = 100만에서 x/ln x는 6,116개 모자라지만 li(x)는 130개 넘칠 뿐입니다.

li(x)를 뫼비우스 함수로 다듬은 근사로 R(x) = Σ μ(n)/n · li(x^(1/n))입니다. li(x)가 소수의 거듭제곱까지 센 것에 가깝기 때문에 제곱수·세제곱수 몫을 덜어 내면 소수만 남는다는 발상입니다. x = 100만에서 오차가 29개로 li(x)의 130개보다 훨씬 작습니다.

아닙니다. 사람이 계산해 본 범위에서는 늘 크지만, 리틀우드가 1914년에 li(x) − π(x)의 부호가 무한히 자주 바뀐다는 것을 증명했습니다. 처음 뒤집히는 자리(스큐스 수)는 10의 316제곱 아래 어딘가로만 알려져 있어 실제로 볼 수는 없습니다. 「지금까지 늘 그랬으니 앞으로도 그렇다」가 왜 증명이 아닌지 보여 주는 유명한 예입니다.

π(x) ≈ x/ln x를 뒤집으면 n번째 소수 ≈ n·ln n이 나오지만 늘 크게 모자랍니다. 한 단계 더 풀어 n(ln n + ln ln n − 1)을 쓰면 훨씬 낫습니다. n = 10만에서 앞엣것은 8% 넘게 모자라고 뒤엣것은 1% 안에 듭니다.

브라우저 안에서 도는 계산기이기 때문입니다. 홀수만 담는 에라토스테네스의 체라도 1천만이면 5MB를 잡고 3천만 번쯤 훑어야 합니다. 그 위는 근사값만 냅니다. 실제로 π(x)를 큰 x에서 구하려면 메이셀–레머 같은 다른 방법이 필요하고, 이 계산기의 범위 밖입니다.

전송되지 않습니다. 체도 근사식도 모두 브라우저 안에서 계산하고 넣은 값은 이 기기에만 남습니다.