재배열 가능 소수

재배열 가능 소수(Permutable prime)는 특정 기수법에서 각 자리 숫자의 순서를 바꾸어도 언제나 소수가 되는 소수를 말한다. 모든 자리 숫자가 1인 단위 반복 소수는 재배열 가능 소수의 특수한 경우이다.

특징

한 자리 소수인 2, 3, 5, 7은 그 자체로 재배열 가능 소수이다. 십진법에서 10보다 큰 소수는 일의 자리가 반드시 1, 3, 7, 9 중 하나이며, 이 때문에 두 자리 이상의 재배열 가능 소수는 모든 자리가 오직 1, 3, 7, 9로만 이루어져 있다.

십진법 재배열 가능 소수로 아래 값들이 있다.

• 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 113, 131, 199, 311, 337, 373, 733, 919, 991, … (OEIS의 수열 A003459)

단위 반복 소수가 아닌 재배열 가능 소수는 위 목록에 쓴 수들 외에는 더 알려지지 않았다. 단위 반복 소수를 포함하면 알려진 가장 큰 재배열 가능 소수는 [math]\displaystyle{ \frac{10^{49081}-1}{9} }[/math]이다.

[math]\displaystyle{ n }[/math]자리 자연수가 1, 3, 7, 9로만 이루어져 있을 때, 각 숫자가 [math]\displaystyle{ a, b, c, d (a+b+c+d=n) }[/math]개 들어가 있다면 이들 숫자를 순열하는 방법은 총 [math]\displaystyle{ \binom{n}{a, b, c}=\frac{n!}{a!b!c!d!} }[/math]가지가 있다. 이 가짓수가 늘어날수록 재배열 가능 소수의 조건을 충족하기 어려워진다. 단위 반복 소수는 모든 숫자가 1이며 순열 가짓수가 단 하나이기에 재배열 가능 소수의 조건이 가장 쉽다. 그 외에는 십진법에서 살펴본 13, 17, 19, 37, 79, 113, 199, 337과 같이 숫자 하나만 다른 경우들을 찾을 수 있다.

다른 진법

이진법에서는 숫자를 0과 1만 사용한다. 숫자 0이 들어가 있으면 재배열 시 일의 자리가 0, 즉 짝수인 경우가 나오게 되는데, 2 이외의 짝수는 모두 합성수이므로 재배열 가능 소수가 될 수 없다. 2의 경우 이진법으로 "10"으로 써지는데, 숫자를 맞바꾸면 "01", 즉 이마저도 소수가 되지 않는다. 따라서 이진법 재배열 가능 소수는 전부 단위 반복 소수이며, 이는 메르센 소수와 같다.

자릿수가 작을 때, 진법의 밑이 클수록 대체로 재배열 가능 소수를 더 많이 찾을 수 있다.

원형 소수

원형 소수(Circular prime)는 숫자의 재배열을 오직 '앞자리 숫자들을 떼어서 뒤에 붙이는' 경우만으로 한정할 때 여전히 소수가 되는 소수들을 말한다. 원형 소수는 재배열 가능 소수의 약한 조건이므로 재배열 가능 소수는 원형 소수의 부분집합이다.

예를 들어 1193의 숫자들을 원형으로 {-- 1, 1, 9, 3, --}과 같이 배치하고 이를 돌려보면 1931, 9311, 3119와 같은 수들이 나온다. 이때 원래 수와 숫자를 변형한 소수 모두 소수이므로, 1193은 원형 소수이다.

십진법에서 재배열 가능 소수를 제외한 원형 소수들로 197, 1193, 3779, 11939, 19937, 193939, 199933이 알려져 있다.

같이 보기

• Prime Pages: Permutable prime
• Prime Pages: Circular prime
• 회문 소수
• 단위 반복 소수
• 절단 가능 소수