10. 열 번째 수업: 여러 가지 소수 (Various Primes)

우주에 흩어진 수많은 소수(Prime)들 중에는 유독 기묘한 형태와 패턴을 띠며 그룹을 지어 다니는 놈들이 있습니다. 쌍둥이처럼 꼭 붙어 다니는 놈들부터, 크기가 어마어마해서 발견될 때마다 전 세계 뉴스에 보도되는 괴물 소수들까지 다양합니다.

학습 목표

  • 서로의 차이가 겨우 $2$밖에 나지 않는 귀여운 ‘쌍둥이 소수(Twin Primes)’의 개념을 이해합니다.
  • $2^n - 1$ 이라는 강력한 거듭제곱 공식을 입고 나타나는 ‘메르센 소수(Mersenne Primes)’를 배웁니다.
  • 파이썬의 연산 루프를 이용해 직접 수학자들처럼 거대 소수 사냥꾼(Prime Hunter)이 되어 특정 패턴의 소수를 발굴해 봅니다.

1. 지독하게 붙어 다니는 ‘쌍둥이 소수’

$3$과 $5$, $5$와 $7$, 그리고 $11$과 $13$. 이 소수들은 모두 그 차이가 딱 $\mathbf{2}$밖에 나지 않습니다. 마치 거리가 너무 좁아 쌍둥이처럼 꼭 붙어 다니는 것 같다고 해서 수학자들은 이들을 ‘쌍둥이 소수(Twin Primes)’라고 불렀습니다.

그런데 쌍둥이 소수들은 숫자가 수백만, 수천만으로 커질수록 점점 발견되기가 어려워집니다. 소수들 자체가 드물어지는데, 그 사이 간격이 딱 $2$인 놈들은 사막에서 같은 무늬의 모래알 두 개를 찾는 것만큼 어렵습니다. 쌍둥이 소수가 우주의 끝까지 영원히 무한하게 나타날 것인지는 아직도 완벽히 증명되지 않은 [쌍둥이 소수 추측(Twin Prime Conjecture)]이라는 수학계의 최고 난제 중 하나입니다.

2. 뉴스에 나오는 괴물 보스 통, ‘메르센 소수’

인터넷 뉴스에서 가끔 “인류 역사상 가장 긴 4천만 자리의 새로운 소수가 발견되었다!” 라는 기사를 본 적 있나요? 그런 거대 소수들의 $99\%$는 바로 메르센 소수(Mersenne Primes)입니다.

17세기 프랑스의 수도승 마랭 메르센은 $2$를 계속 곱한 거듭제곱($2^n$)에서 $1$을 빼면 아주 높은 확률로 아름다운 소수가 탄생한다는 엄청난 공식을 눈치챘습니다.

메르센 소수 공식: $M_n = 2^n - 1$ (단, 지수 $n$도 소수여야 함)

  • $n=2$ 일 때: $2^2 - 1 = \mathbf{3}$ (소수 맞음!)
  • $n=3$ 일 때: $2^3 - 1 = \mathbf{7}$ (소수 맞음!)
  • $n=5$ 일 때: $2^5 - 1 = \mathbf{31}$ (소수 맞음!)
  • $n=7$ 일 때: $2^7 - 1 = \mathbf{127}$ (소수 맞음!)

이 공식이 위대한 이유는, 사람들이 엉뚱한 숫자를 찔러가며 소수를 찾는 헛수고를 할 필요 없이 $2$의 거듭제곱 - $1$이라는 특정 빌드 트리(Build Tree)만 미친 듯이 파고들면 가장 거대한 보스 소수들을 캐낼 수 있기 때문입니다.

3. Python 소수 사냥꾼: 메르센 헌터 봇

우주 최고의 메르센 소수 사냥 프로젝트인 GIMPS(Great Internet Mersenne Prime Search)처럼 우리도 파이썬으로 꼬마 사냥꾼 봇을 가동해 봅시다.

# 파이썬으로 가동하는 거대 [메르센 소수] 사냥 봇

import math

def is_prime(num):
    """기본 소수 판별기. 이전 수업에서 배운 내용입니다."""
    if num < 2: return False
    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0:
            return False
    return True

print("🏹 메르센 소수 사냥 봇 가동 시작 (초기 지수 n=2부터 n=19까지 탐색합니다)")

# 지수 n 역시 소수(Prime)여야 메르센 소수가 탄생할 후보 자격이 생깁니다.
prime_exponents = [2, 3, 5, 7, 11, 13, 17, 19]

for n in prime_exponents:
    
    # 1. 일단 메르센 거대 괴물로 뻥튀기 조립을 합니다. (2^n - 1)
    mersenne_candidate = (2 ** n) - 1
    
    # 2. 이 뻥튀기된 괴물이 진짜 다이아몬드 소수인지 필터링(해체) 검사를 시작합니다.
    if is_prime(mersenne_candidate):
        print(f"🌟 [발견] {n}번 째 메르센 소수! => 2^{n} - 1 = {mersenne_candidate}")
    else:
        print(f"❌ [실패] 2^{n} - 1 = {mersenne_candidate} (은)는 아쉽게도 합성수(부서짐)입니다.")

여러분의 컴퓨터가 2의 11승 - 1 인 $2047$이 아쉽게도 합성수임을 즉시 눈치채고 버리는 것을 볼 수 있습니다 ($2047 = 23 \times 89$). 파이썬의 거듭제곱 연산자(**)와 is_prime 필터를 결합하면 누구나 집에서 전 세계 수학계를 흔들 거대 소수 발굴 작업에 참여할 수 있습니다.

학습 정리

  1. 쌍둥이 소수 (Twin Primes): $11$과 $13$, $41$과 $43$처럼 두 소수의 차이가 딱 $2$인 친한 소수 쌍.
  2. 메르센 소수 (Mersenne Primes): $2^n - 1$ 꼴로 만들어진 거대 소수. 규칙적인 방정식 모양을 띠고 있어서 전 세계 슈퍼컴퓨터들이 새로운 거대 소수를 갱신할 때 이 공식을 주로 판다.
  3. 파이썬의 거듭제곱 연산자(**)는 컴퓨터가 지수 연산을 하드웨어 차원에서 최적화하여 십만 자리, 백만 자리 숫자를 순식간에 메모리에 띄우게 해준다. 수학자 페르마가 일주일을 고생해야 풀던 계산을 Python 루프는 단 한 줄의 코드로 우주 끝까지 쏘아 올린다.
서브목차