1. 개요
素數 沙漠 / prime desert한 소수와 그로부터 가장 가까운 소수 사이의 구간, 즉 소수를 작은 것부터 차례로 나열했을 때 이웃해 있는 두 소수 사이의 구간을 가리키는 말. 이때 '이 구간 사이의 합성수의 개수'를 '소수 사막의 길이'라고 한다. 소수와 다른 소수 사이의 간격이 불규칙하므로 소수 사막의 길이도 불규칙하다. 하지만 유클리드가 소수는 무한하다는 것을 증명했으므로 모든 소수 사막의 길이는 유한하다.
2. 특징
- (2, 3)을 제외하고는 이웃해 있는 두 소수 사이에 반드시 길이가 1 이상인 소수 사막이 반드시 존재한다.
- 이때 그 길이가 1이면 쌍둥이 소수이다.
- 모든 소수 사막의 길이는 홀수이며, 소수 사막 내의 첫 번째 수와 마지막 수는 모두 짝수이다.
- 2를 제외한 모든 소수는 홀수이므로, 3 이상의 모든 소수에 대해 그 직전과 직후의 정수는 모두 짝수이기 때문이다.
- 3으로 나누었을 때의 나머지는 0, 1, 2 모두 가능하다. 즉 [math(3n, 3n+1, 3n+2)] 꼴의 길이의 소수 사막이 모두 가능하다. 이때 이웃한 두 소수의 순서쌍은 다음과 같다.
- [math(3n)] 꼴 : [math((6k-1, 6(k+1)-1), (6k+1, 6(k+1)+1))] 등
- [math(3n+1)] 꼴 : [math((6k+1, 6k+5))] 등
- [math(3n+2)] 꼴 : [math((6k-1, 6k+1), (6k-1, 6(k+1)+1))] 등
3. 소수 사막의 길이
상술했듯이 소수 사막의 길이는 모두 홀수이다. 이 중 길이가 1인 경우는 쌍둥이 소수 문서 참고.자세히 살펴보면 소수 사막의 길이가 (소인수가 많은 수) - 1인 경우가 다른 경우보다 많다는 것을 알 수 있다. 대표적으로는 [math(6-1=5, 12-1=11, 30-1=29)]를 예로 들 수 있다. 반면 예를 들어 [math(2^n-1)]과 같은 경우, [math(2^n)]의 소인수는 2뿐이므로 해당 길이의 소수 사막은 다른 경우에 비해 그리 많지 않다.
이는 소수 사막의 길이가 n이라는 것은 두 소수 사이의 간격이 n+1이라는 것, 즉 두 소수가 각각 [math(p)]와 [math(p+(n+1))]로 나타내어질 수 있다는 것을 의미하는데, [math(p)]가 소수일 때 n+1이 가지고 있는 소인수가 많을수록 [math(p+(n+1))] 역시 소수일 확률이 높아지기 때문이다. 예를 들어 소인수가 2, 3, 5, 7뿐이라고 가정한다면, n+1이 가지고 있는 소인수에 따라서 소수 [math(p)]에 대해서 [math(p+(n+1))]이 역시 소수일 확률을 구하면 다음과 같다. n+1의 소인수를 제외한 나머지 소인수 각각에 대해 모두 나누어떨어지지 않아야 하므로[1] 그 확률을 모두 곱하면 되는데, 이때 어떤 소인수 [math(p')]로 나누어떨어지지 않을 확률은 [math(p)]가 소수이므로 [math(\displaystyle\frac{p'-1}{p'})]가 아니라 [math(\displaystyle\frac{p'-2}{p'-1})]임에 주의한다.
- n+1의 소인수가 [math(2)]뿐일 때, [math(\displaystyle\frac{1}{2}\times\frac{3}{4}\times\frac{5}{6}=\frac{5}{16})]
- n+1의 소인수가 [math(2, 3)]일 때, [math(\displaystyle\frac{3}{4}\times\frac{5}{6}=\frac{5}{8})]
- n+1의 소인수가 [math(2, 5)]일 때, [math(\displaystyle\frac{1}{2}\times\frac{5}{6}=\frac{5}{12})]
- n+1의 소인수가 [math(2, 7)]일 때, [math(\displaystyle\frac{1}{2}\times\frac{3}{4}=\frac{3}{8})]
- n+1의 소인수가 [math(2, 3, 5)]일 때, [math(\displaystyle\frac{5}{6})]
- n+1의 소인수가 [math(2, 3, 5, 7)]일 때, [math(1)]
여기서는 소인수가 2, 3, 5뿐만이라고 가정하고, 이들의 최소공배수인 30을 단위로 하여 [math((30k+a, 30k+b))] 꼴로 이웃한 두 소수를 나타낸다. 이에 따라 각 길이에 해당하는 소수 사막의 경우의 수를 정리하면 다음과 같다. 길이가 5(=[math(2\times3-1)]), 11(=[math(2^2\times3-1)])인 경우가 다른 경우보다 많은 것을 알 수 있다.
- 길이가 3인 경우 (3): [math((30k+7, 30k+11), (30k+13, 30k+17), (30k+19, 30k+23))]
- 길이가 5인 경우 (6): [math((30k+1, 30k+7), (30k+7, 30k+13), (30k+11, 30k+17), (30k+13, 30k+19), (30k+17, 30k+23), (30k+23, 30k+29))]
- 길이가 7인 경우 (3): [math((30k+11, 30k+19), (30k+23, 30k+31), (30k+29, 30k+37))]
- 길이가 9인 경우 (4): [math((30k+1, 30k+11), (30k+7, 30k+17), (30k+13, 30k+23), (30k+19, 30k+29))]
- 길이가 11인 경우 (6): [math((30k+1, 30k+13), (30k+7, 30k+19), (30k+11, 30k+23), (30k+17, 30k+29), (30k+19, 30k+31), (30k+29, 30k+41))]
- 길이가 13인 경우 (3): [math((30k+17, 30k+31), (30k+23, 30k+37), (30k+29, 30k+43))]
- 길이가 15 이상인 경우, 즉 이웃한 두 소수 사이의 간격이 16 이상인 경우는, 길이가 [math(x)]라고 할 때 길이가 [math(30-2-x=28-x)]인 경우에서 각 순서쌍의 순서를 서로 바꾼 후 뒤쪽에 30을 더하면 된다. 즉 대칭 계산. 예를 들어 길이가 19인 경우는 길이가 [math(28-19=9)]인 경우이므로 [math((30k+11, 30k+1+30)=(30k+11, 30k+31))] 등이 된다.
4. 연속된 합성수
3 이상의 임의의 자연수 n 에 대해서, n 이상의 길이를 가지는 소수 사막(연속된 합성수)가 항상 존재한다.2 ~ n+1까지의 최소공배수([math({\rm lcm})])를 구해서 그 값을 [math(L)]이라고 두자.
- [math(L+2)]는 2의 배수이므로 합성수이다.
- [math(L+3)]은 3의 배수이므로 합성수이다.
... - [math(L+n)]은 n의 배수이므로 합성수이다.
- [math(L+(n+1))]은 n+1의 배수이므로 합성수이다.
최소공배수처럼 2, 3, ..., n+1의 모든 소인수로 나누어떨어진다는 점이 같으므로 최소공배수 대신 이보다 작은 2 ~ n+1까지의 모든 소인수의 곱[2]을 [math(L)]이라고 할 수도 있는데, 이때는 다음과 같으며, n의 값은 4 이상이어야 한다.
- [math(L+2)]는 2의 모든 소인수인 2의 곱인 2의 배수이므로 합성수이다.
- [math(L+3)]은 3의 모든 소인수인 3의 곱인 3의 배수이므로 합성수이다.
- [math(L+4)]는 4(=[math(2^2)])의 모든 소인수인 2의 곱인 2의 배수이므로 합성수이다.
- [math(L+5)]은 5의 모든 소인수인 5의 곱인 5의 배수이므로 합성수이다.
- [math(L+6)]은 6(=[math(2\times3)])의 모든 소인수인 2와 3의 곱인 6의 배수이므로 합성수이다.
... - [math(L+n)]은 n의 모든 소인수의 곱의 배수이므로 합성수이다.
- [math(L+(n+1))]은 n+1의 모든 소인수의 곱의 배수이므로 합성수이다.
즉, [math(L+2)]부터 [math(L+(n+1))]까지, 그리고 [math(L-2)]부터 [math(L-(n+1))]까지는 n개의 연속된 합성수이다. [math(2L, 3L)]등에 대해서도 모두 동일하게 성립하므로 n 개의 연속된 합성수는 무한히 존재한다. 즉 1 이상의 정수 k에 대하여 [math(kL+2)]부터 [math(kL+(n+1))]까지, 그리고 [math(kL-2)]부터 [math(kL-(n+1))]까지는 길이가 n 이상인 소수 사막의 전체 또는 일부이다.
이때 [math(L={\rm lcm}\,(2,3,...,n+1)\leq(n+1)!)]이므로 [math((n+1)!)] 이하의 자연수 범위에서 길이가 n 이상인 소수 사막이 반드시 존재한다.
예를 들어 [math(n = 5)]라고 하면, [math({\rm lcm}\,(2,3,4,5,6) = 60)]이며 이들의 소인수 2, 3, 5의 곱은 30이므로, 소인수의 곱을 이용한 [math(L)] 기준의 24,25,26,27,28과 32,33,34,35,36, 그리고 최소공배수를 이용한 [math(L)] 기준의 54,55,56,57,58과 62,63,64,65,66은 각각 5개의 연속된 합성수이다. 또한, 114,115,116,117,118과 122,123,124,125,126, 그리고 174,175,176,177,178과 182,183,184,185,186 역시 각각 5개의 연속된 합성수이다.
이때 [math(L-(n+1), L-1, L+1, L+(n+1))] 중 하나 이상이 합성수이면 소수 사막의 길이가 n보다 커진다. 예를 들어 [math(n=7)]또는 [math(n=8)]일 때 [math(L=840)]인데, 이때 [math(L+1=841=29^2)]부터 [math(L+(7+1)=848, L+(7+2)=L+(8+1)=849, L+(7+3)=L+(8+2)=850, L+(7+4)=L+(8+3)=851, L+(7+5)=L+(8+4)=852)]가 모두 합성수이므로 소수 사막의 길이는 13=7+6=8+5이다. n+2가 합성수이면 [math(L)]은 n+2의 어떤 소인수의 배수일 수밖에 없으므로 [math(L+(n+2), L-(n+2))] 역시 합성수이기 때문에 반드시 이런 현상이 나타난다. 또한 [math((n+1)+k, k=1,2,...,t, t\leq n+1)]가 모두 합성수이면 [math(L)]은 마찬가지로 이들의 어떤 소인수의 배수가 되므로 [math(L+(n+2), L+(n+3), ..., L+(n+1+t), L-(n+2), L-(n+3), ..., L-(n+1+t))]가 모두 합성수가 되어서 소수 사막이 더 길어진다.
n이 2 이하인 경우에는 다음과 같이 예외가 된다.
- [math(n=1)]일 때, [math(L=2, L-2=0, L+2=4)]가 되는데 0은 합성수가 아니다.
- [math(n=2)]일 때, [math(L=6, L-3=3, L-2=4, L+2=8, L+3=9)]가 되는데 3은 소수이다.
5. 분포
5.1. 길이가 n 이상인 소수 사막
길이가 n 이상인 소수 사막이 등장하는 시점은 다음과 같다. (최초부터 길이가 n+1 이상인 소수 사막이 등장하기 전까지). 이 중 '연속된 합성수' 문단에서 언급한 [math(L)]에 대해 [math([L-(n+1), L-2])] 또는 [math([L+2, L+(n+1)])] 구간을 포함하는 경우는 [math(L)]이 최소공배수인 경우 볼드체, 모든 소인수의 곱인 경우 밑줄 처리한다.| 길이 | 이웃한 두 소수의 순서쌍 |
| 1 | (3, 5), (5, 7) |
| 3 | (7, 11), (13, 17), (19, 23) |
| 5 | (23, 29), (31, 37), (47, 53), (53, 59), (61, 67), (73, 79), (83, 89) |
| 7 | (89, 97) |
| 13 | (113, 127), (293, 307), (317, 331) |
| 17 | (523, 541) |
| 19 | (887, 907) |
| 21 | (1129, 1151) |
| 33 | (1327, 1361), (8467, 8501) |
| 35 | (9551, 9587), (12853, 12889), (14107, 14143) |
| 43 | (15683, 15727) |
| 51 | (19609, 19661), (25471, 25523) |
| 71 | (31397, 31469) |
| 85 | (155921, 156007), (338033, 338119) |
| 95 | (360653, 360749) |
| 111 | (370261, 370373) |
| 113 | (492113, 492227) |
| 117 | (1349533, 1349651) |
| 131 | (1357201, 1357333), (1561919, 1562051) |
| 147 | (2010733, 2010881) |
| 153 | (4652353, 4652507) |
5.2. 소수 사막의 길이의 분포
각 자연수 구간(소수 사막이 시작되는 지점 기준)에서 소수 사막의 길이 분포는 다음과 같다.| 범위 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 20~49 | 50~99 | 100 이상 |
| 1 ~ 20 | 4 | 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 21 ~ 50 | 2 | 2 | 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 51 ~ 100 | 2 | 3 | 4 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 101 ~ 200 | 7 | 5 | 5 | 0 | 2 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 201 ~ 300 | 4 | 3 | 5 | 0 | 2 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 301 ~ 400 | 2 | 5 | 5 | 2 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 401 ~ 500 | 3 | 5 | 2 | 4 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 501 ~ 600 | 3 | 0 | 7 | 0 | 2 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 601 ~ 700 | 3 | 3 | 5 | 1 | 2 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 701 ~ 800 | 0 | 3 | 3 | 4 | 2 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 801 ~ 900 | 5 | 5 | 0 | 0 | 2 | 0 | 2 | 0 | 0 | 1 | 0 | 0 | 0 |
| 901 ~ 1,000 | 0 | 3 | 5 | 3 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 ~ 1,000 | 35 | 40 | 44 | 15 | 16 | 8 | 7 | 0 | 1 | 1 | 0 | 0 | 0 |
| ~2,000 | 26 | 24 | 35 | 11 | 13 | 11 | 3 | 2 | 5 | 1 | 4 | 0 | 0 |
| ~3,000 | 21 | 22 | 29 | 14 | 12 | 9 | 7 | 5 | 3 | 0 | 5 | 0 | 0 |
| ~4,000 | 21 | 21 | 23 | 10 | 11 | 12 | 6 | 5 | 2 | 3 | 6 | 0 | 0 |
| ~5,000 | 23 | 14 | 31 | 5 | 14 | 10 | 5 | 4 | 7 | 0 | 6 | 0 | 0 |
| ~6,000 | 17 | 19 | 31 | 8 | 8 | 8 | 5 | 4 | 3 | 3 | 8 | 0 | 0 |
| ~7,000 | 19 | 13 | 29 | 13 | 18 | 6 | 2 | 4 | 6 | 1 | 6 | 0 | 0 |
| ~8,000 | 13 | 17 | 23 | 8 | 8 | 13 | 7 | 3 | 7 | 1 | 7 | 0 | 0 |
| ~9,000 | 15 | 17 | 25 | 10 | 12 | 10 | 6 | 2 | 2 | 4 | 7 | 0 | 0 |
| ~10,000 | 15 | 15 | 29 | 7 | 7 | 18 | 6 | 4 | 4 | 1 | 6 | 0 | 0 |
| 1 ~ 10,000 | 205 | 202 | 299 | 101 | 119 | 105 | 54 | 33 | 40 | 15 | 55 | 0 | 0 |
| ~20,000 | 137 | 141 | 226 | 85 | 92 | 109 | 54 | 36 | 44 | 25 | 83 | 1 | 0 |
| ~50,000 | 363 | 349 | 573 | 231 | 278 | 320 | 136 | 106 | 177 | 66 | 261 | 11 | 0 |
| ~100,000 | 519 | 523 | 842 | 356 | 427 | 431 | 240 | 164 | 253 | 132 | 564 | 8 | 0 |
| ~200,000 | 936 | 920 | 1,515 | 618 | 789 | 856 | 475 | 298 | 521 | 233 | 1,189 | 42 | 0 |
| ~500,000 | 2,405 | 2,423 | 4,019 | 1,690 | 2,137 | 2,416 | 1,322 | 875 | 1,477 | 743 | 3,878 | 167 | 2 |
| ~1,000,000 | 3,604 | 3,585 | 6,075 | 2,488 | 3,237 | 3,768 | 1,952 | 1,369 | 2,397 | 1,188 | 6,910 | 387 | 0 |
| 합계 | 8,169 | 8,143 | 13,549 | 5,569 | 7,079 | 8,005 | 4,233 | 2,881 | 4,909 | 2,402 | 12,940 | 616 | 2 |