[목차] == 개요 == {{{+1 [[素]][[數]] [[沙]][[漠]] / prime desert}}} 한 [[소수(수론)|소수]]와 그로부터 가장 가까운 소수 사이의 구간, 즉 소수를 작은 것부터 차례로 나열했을 때 이웃해 있는 두 소수 사이의 구간을 가리키는 말. 이때 '이 구간 사이의 [[합성수]]의 개수'를 '소수 사막의 길이'라고 한다. 소수와 다른 소수 사이의 간격이 불규칙하므로 소수 사막의 길이도 불규칙하다. 하지만 [[유클리드]]가 소수는 무한하다는 것을 증명했으므로 모든 소수 사막의 길이는 유한하다. == 특징 == * (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))] 등 == 소수 사막의 길이 == 상술했듯이 소수 사막의 길이는 모두 홀수이다. 이 중 길이가 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의 소인수를 제외한 나머지 소인수 각각에 대해 모두 나누어떨어지지 않아야 하므로[* 예를 들어 n+1의 소인수가 2, 3일 때는 나머지 소인수 5, 7, ... 등으로 모두 나누어떨어지지 않아야 한다.] 그 확률을 모두 곱하면 되는데, 이때 어떤 소인수 [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)] 위 결과를 분석해 보면, 소인수의 개수가 많을수록, 소인수의 개수가 같은 경우에는 그 소인수가 작을수록 [math(p+(n+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))] 등이 된다. == 연속된 합성수 == 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까지의 모든 소인수의 곱[* 예를 들어 1부터 10까지의 최소공배수는 2,520이지만 모든 소인수 2, 3, 5, 7의 곱은 210으로 1/12로 작아진다.]을 [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은 소수이다. == 분포 == === 길이가 n 이상인 소수 사막 === 길이가 n 이상인 소수 사막이 등장하는 시점은 다음과 같다. (최초부터 길이가 n+1 이상인 소수 사막이 등장하기 전까지). 이 중 '연속된 합성수' 문단에서 언급한 [math(L)]에 대해 [math([L-(n+1), L-2])] 또는 [math([L+2, L+(n+1)])] 구간을 포함하는 경우는 [math(L)]이 최소공배수인 경우 볼드체, 모든 소인수의 곱인 경우 밑줄 처리한다. || {{{#white 길이}}} || {{{#white 이웃한 두 소수의 순서쌍}}} || || 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) || === 소수 사막의 길이의 분포 === 각 자연수 구간(소수 사막이 시작되는 지점 기준)에서 소수 사막의 길이 분포는 다음과 같다. || {{{#white 범위}}} || {{{#white 1}}} || {{{#white 3}}} || {{{#white 5}}} || {{{#white 7}}} || {{{#white 9}}} || {{{#white 11}}} || {{{#white 13}}} || {{{#white 15}}} || {{{#white 17}}} || {{{#white 19}}} || {{{#white 20~49}}} || {{{#white 50~99}}} || {{{#white 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''' || 자세히 살펴보면 길이가 5, 11, 17과 같이 [math(6k+5)] 꼴인 소수 사막은 비슷한 길이([math(6k+1, 6k+3)])의 소수 사막보다 유난히 많은 것을 볼 수 있는데, 이는 두 소수 간의 차이가 6=2×3의 배수인 경우가 많기 때문이다. == 관련 문서 == * [[쌍둥이 소수]] [[분류:소수(수론)]][[분류:수학 용어]][[분류:한자어]]