유해수

유해수(有害數, Pernicious number)는 수론에서 이진법 표현의 해밍 무게가 소수인 양의 정수이다. 즉, 이진수로 표기했을 때 1의 개수가 소수인 수이다.

예시

첫 번째 유해수는 3인데, 3 = 11₂이고 1 + 1 = 2는 소수이기 때문이다. 다음 유해수는 5이며 5 = 101₂이고, 그 다음은 6 (110₂), 7 (111₂), 9 (1001₂)이다. 유해수의 수열은 다음과 같다.

3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 24, ... (OEIS의 수열 A052294).

특징

2의 거듭제곱은 유해수가 아니다. 이것은 자명하게 사실인데, 이진법으로 표현된 2의 거듭제곱은 1 뒤에 0이 붙는 형태이기 때문이다. 따라서 모든 2의 거듭제곱은 해밍 무게가 1이며, 1은 소수로 간주되지 않는다. 반면에, $n>1$인 $2^{n}+1$ 형태의 모든 수(모든 페르마 수 포함)는 유해수이다. 이는 이진법으로 표기했을 때 자릿수의 합이 2로 소수이기 때문이다.

메르센 수 $2^{n}-1$은 $n$개의 1로 구성된 이진 표현을 가지며, $n$이 소수일 때 유해수이다. 모든 메르센 소수는 소수 $n$에 대한 메르센 수이므로 유해수이다. 에우클레이데스-오일러 정리에 따라, 짝수 완전수는 메르센 소수 $2^{n}-1$에 대해 $2^{n-1}(2^{n}-1)$의 형태를 갖는다. 이러한 수의 이진 표현은 $n$개의 1과 그 뒤에 $n-1$개의 0으로 구성된다. 따라서 모든 짝수 완전수는 유해수이다.

관련 수

• 기피수는 이진 전개에서 1이 홀수 개 있는 수이다 ( A000069).
• 악수는 이진 전개에서 1이 짝수 개 있는 수이다 ( A001969).