절단 가능 소수

절단 가능 소수(Truncatable prime)는 특정 기수법에서 왼쪽이나 오른쪽 자리를 잘라도 항상 소수가 되는 소수를 말한다. 자르는 방향이나 진법에 따라 종류가 정해진다.

왼편 절단 가능 소수

어떤 소수가 주어졌을 때, 어느 자리에도 숫자 0을 포함하지 않고, 왼쪽(큰 자리)을 잘라냈을 때 여전히 소수이면 이를 왼편 절단 가능 소수(left-truncatable prime)라 부른다.

이를테면 1223에서 왼쪽 자리를 차례대로 잘라내면 223, 23, 3인데, 이들 수 역시 모두 소수이므로 1223은 왼편 절단 가능 소수이다.

어떤 자연수 [math]\displaystyle{ N }[/math]이 [math]\displaystyle{ n }[/math]자리수라 하고, 이 수의 맨 왼쪽에 한 자리 자연수를 붙인다. 그러면 [math]\displaystyle{ N'=a \cdot 10^n+N }[/math] 꼴의 [math]\displaystyle{ n+1 }[/math]자리 자연수를 불러올 수 있다. [math]\displaystyle{ N' }[/math]이 왼편 절단 가능 소수이기 위한 필요조건은 [math]\displaystyle{ N }[/math]도 왼편 절단 가능 소수인 것이다.

따라서 이러한 소수를 찾고자 한다면 먼저 한 자리 소수에서 시작해서 왼쪽에다 1~9를 붙여보고 두 자리 소수를 찾고, 다시 왼쪽에다 숫자를 붙이고 소수 찾기를 반복하면 된다.

• 한 자리 소수는 십진법에서 2, 3, 5, 7이다.
• 2, 5의 경우 왼쪽에다 숫자를 붙이면 자동으로 합성수가 된다. 그러므로 2, 5는 한 자리에서 끝난다.
• 3 앞에 숫자 하나를 붙이고 소수를 찾는다: 13, 23, 43, 53, 73, 83
  • 위 두 자리 수에다 숫자 하나를 또 붙이고 소수를 찾는다: 113, 313, 613 / 523, 823 / 443, 643, 743 / 353, 653, 853, 953 / 173, 373, 673, 773 / 283, 383, 683, 883, 983
• 7 앞에 숫자 하나를 붙이고 소수를 찾는다: 17, 37, 47, 67, 97
  • 위 두 자리 수에다 숫자 하나를 또 붙이고 소수를 찾는다: 317, 617 / 137, 337, 937 / 347, 547, 647, 947 / 167, 367, 467, 967 / 197, 397, 797, 997
• 위 방식대로 자릿수를 늘려가면서 소수가 더 이상 나오지 않을 때까지 추적하면, 4260개가 나온다. (OEIS의 수열 A024785)

십진법에서 가장 큰 왼편 절단 가능 소수는 357686312646216567629137이다.

오른편 절단 가능 소수

위 문단과는 반대로 소수에서 오른쪽(작은 자리)을 잘라내어도 여전히 소수이면 그 수는 오른편 절단 가능 소수(right-truncatable prime)이다. 따라서 십진법에서는 가장 큰 자리가 2, 3, 5, 7이어야 한다.

2939의 경우 오른쪽 자리를 잘라내면 293, 29, 2이다. 이들 수는 모두 소수이므로, 2939는 오른편 절단 가능 소수이다.

두 자리 이상의 소수는 일의 자리가 무조건 1, 3, 7, 9중 하나이다. 그렇기에 소수를 찾을 때, 오른쪽에 붙일 수 있는 숫자도 이들 네 종류 뿐이라 개수도 왼편보다 훨씬 적다.

특히, 십진법의 특성 상 3의 배수가 아니려면 각 자리의 합이 3의 배수가 아니어야 한다. 가령 3이 아닌 소수 [math]\displaystyle{ N }[/math]에 대해 이 자연수의 각 자리의 합 [math]\displaystyle{ \sigma(N) }[/math]은 3으로 나눈 나머지가 1 또는 2이다. 이때 각 경우에 따라 붙일 수 있는 숫자가 달라진다.

• [math]\displaystyle{ \sigma(N) \equiv 1 \pmod 3 }[/math]이면 오른쪽에 1, 3, 7, 9를 붙일 수 있다. 3이나 9를 붙이면 [math]\displaystyle{ \sigma(10N+3) \equiv \sigma(10N+9) \equiv 1 \pmod 3 }[/math]이므로 첫째 경우로 돌아온다. 1이나 7을 붙이면 [math]\displaystyle{ \sigma(10N+1) \equiv \sigma(10N+7) \equiv 2 \pmod 3 }[/math]이므로 둘째 경우로 넘어간다.
• [math]\displaystyle{ \sigma(N) \equiv 2 \pmod 3 }[/math]이면 오른쪽에는 3과 9밖에 붙일 수 없다. [math]\displaystyle{ \sigma(10N+3) \equiv \sigma(10N+9) \equiv 2 \pmod 3 }[/math]이므로 둘째 경우로 돌아온다.

따라서 오른편 절단 가능 소수는 맨 왼쪽 자리가 2 또는 5이면 그 뒤로는 3과 9로만 이루어진다. 그밖의 경우, 1과 7 합해서 하나 아니면 두 개만 들어갈 수 있고, 나머지는 모조리 3과 9로만 채워진다.

십진법 오른편 절단 가능 소수는 총 83개이고, 가장 큰 수는 73939133이다. (OEIS의 수열 A024770)

왼쪽과 오른쪽으로 절단이 모두 가능한 소수를 양면 소수(two-sided prime)라 하며, 십진법에서는 총 15개 존재한다.

• 2, 3, 5, 7, 23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797, 739397

다른 진법

[math]\displaystyle{ b }[/math]진법에서는 자릿수 하나가 늘어날 때마다 왼쪽으로는 [math]\displaystyle{ b-1 }[/math]개, 오른쪽으로는 [math]\displaystyle{ \varphi(b) }[/math](오일러 피 함수)개 붙일 수 있다. 일반적으로 진법의 밑이 클수록 절단 가능 소수도 많아지는 경향을 보인다.

이진법의 경우 한 자리 수는 1 뿐인데 1은 소수가 아니므로, 절단 가능 소수는 전혀 없다. 다만 절단의 한계를 한 자리 대신 두 자리로 바꾸면, 왼편 절단 가능 소수는 이진법으로 10, 11, 111로 3개, 오른편 절단 가능 소수는 10, 11, 101, 111, 1011, 10111, 101111로 7개 존재한다.

같이 보기

• Prime Glossary: Left-truncatable prime
• Prime Glossary: Right-truncatable prime
• 회문 소수
• 단위 반복 소수
• 재배열 가능 소수