1. 메르센 수
\(2^n-1\) 의 꼴의 수를 메르센 수라고 합니다.
메르센 수를 이진수로 나타내면 모든 자리가 1인 수입니다.
2. 하노이의 탑
\(n\)층의 하노이의 탑을 옮기는 횟수를 \(f(n)\)이라고 했을 때, 1층인 하노이의 탑을 옮기는 것은 1회이므로 \(f(1) = 1\)입니다.
\(n\)층의 하노이의 탑을 옮기려면 다음과 같은 과정을 거칩니다.
맨 밑의 한 개를 제외하고 \(n-1\)층을 일단 옮겨놓습니다. (\(f(n-1)\))
맨 밑의 한 개를 옮깁니다. (\(f(1)\))
다시 그 위에 \(n-1\)층을 옮겨놓으면 됩니다. (\(f(n-1)\))
이 식을 정리하면 다음과 같습니다.
\[
\begin{aligned}
f(n) &= f(n-1) \times 2 + 1 \\
&= \big(f(n-2) \times 2 + 1\big) \times 2 + 1 = f(n-2) \times 2^2 + 2 + 1 \\
&\;\;\vdots \\
&= f(1) \times 2^{n-1} + 2^{n-2} + \cdots + 2^1 + 2^0 \\
&= 2^n - 1
\end{aligned}
\]
이를 통해 하노이의 탑을 옮기는 횟수는 메르센 수라는 것을 알 수 있습니다.
3. 메르센 소수
메르센 수 중에서 소수인 메르센 수를 메르센 소수라고 합니다.
메르센 수의 2의 지수 \(n\)이 \(a\)와 \(b\)의 합성수라고 하면,
\[
2^{a \cdot b} - 1 = (2^a - 1) \cdot \left(2^{a(b-1)} + 2^{a(b-2)} + \cdots + 2^a + 1\right)
\]
위와 같이 인수분해되므로 메르센 수도 합성수가 됩니다.
따라서 메르센 소수일 때 2의 지수는 항상 소수입니다.
그러나 지수가 소수라고 메르센 소수가 되는 것은 아닙니다.(\(2^{11}-1 = 2047 = 23 \times 89\))
간단하게 \(n\)이 31까지 메르센 소수를 찾는 코드는 다음과 같습니다.
def is_prime(n):
for i in range(2, int(n**0.5)+1):
if n % i == 0:
return False
return True
for i in range(2, 32):
if is_prime(i) and is_prime(2**i -1):
print(f"(2^{i})-1 = {2**i - 1}")
# (2^2)-1 = 3
# (2^3)-1 = 7
# (2^5)-1 = 31
# (2^7)-1 = 127
# (2^13)-1 = 8191
# (2^17)-1 = 131071
# (2^19)-1 = 524287
# (2^31)-1 = 2147483647
