Go 로 읽는 SICP Part 2: 프로시저는 재귀인데 프로세스는 반복이다

이 글은 Claude Opus 5 를 이용해 초안이 작성되었으며, 이후 퇴고를 거쳤습니다.

Part 1에서 책과 저자를 소개하고, Go 로 이 책을 읽을 때 부딪히는 마찰 세 곳을 예고했습니다. 이번 편에서 그중 첫 번째와 정면으로 만납니다.

1장의 제목은 Building Abstractions with Procedures 입니다. 다루는 내용은 두 덩어리입니다. 앞쪽(1.1)은 프로시저를 어떻게 만들고 이름 뒤에 감추는가, 뒤쪽(1.2)은 그 프로시저가 실행될 때 어떤 모양의 프로세스가 생기는가 입니다.

이 두 번째가 이 책의 첫 번째 큰 아이디어입니다. 그리고 Go 로 옮기면 그 아이디어가 성립하지 않습니다. 성립하지 않는 이유가 오히려 아이디어를 선명하게 만듭니다.

1. 먼저 지난 편의 빚을 갚습니다#

Part 1 에서 뉴턴법 제곱근을 Go 로 옮겼고, 두 곳에서 부서졌습니다. 0.0001 은 답이 3배 넘게 틀렸고, 1e13 은 아예 수렴하지 않았습니다. 원인은 goodEnough 가 고정된 절대 오차 를 쓴 것이었습니다.

func goodEnough(guess, x float64) bool { return abs(guess*guess-x) < 0.001 }

0.001 이라는 숫자가 문제입니다. 답이 0.01 인 문제에서 이 자는 너무 굵고, 답이 300만인 문제에서는 부동소수점이 표현할 수 있는 간격보다 좁습니다. 같은 자로 개미와 코끼리를 재려 한 것입니다.

원서의 연습문제 1.7 이 제시하는 해법은 추측값의 변화량 을 보는 것입니다. 이번 추측과 다음 추측의 차이가 추측값 자체에 비해 아주 작아지면 멈춥니다.

func sqrtGood(x float64) (float64, int) {
	guess := 1.0
	for i := 0; ; i++ {
		next := (guess + x/guess) / 2
		if abs(next-guess) < abs(guess)*1e-12 { // 절대량이 아니라 비율
			return next, i
		}
		guess = next
	}
}

실행 결과입니다.

sqrtGood(9)     = 3                    (6회 반복)
sqrtGood(0.0001)= 0.01                 (11회 반복)
sqrtGood(1e+13) = 3162277.6601683795   (26회 반복)

세 경우 모두 맞습니다. 고친 것은 알고리즘이 아니라 판정 기준 입니다. 뉴턴법 자체는 한 글자도 안 바꿨습니다.

여기에 1장 전체를 관통하는 교훈이 들어 있습니다. goodEnough 는 처음부터 잘못 그어진 추상화 경계 였습니다. “충분히 좋은가” 라는 질문은 문제 규모와 무관할 수 없는데, 원래 코드는 무관한 척했습니다. 추상화가 감춰야 할 것과 감추면 안 되는 것을 잘못 고른 사례입니다.

2. 1.1 — 프로그래밍 언어에 있어야 하는 세 가지#

원서는 1.1 을 이 문장으로 엽니다. 강력한 언어라면 원시 요소, 조합 수단, 추상화 수단 세 가지를 제공한다는 것입니다.

원서의 분류	Scheme	Go
원시 식(primitive expressions)	`42`, `+`, `car`	`42`, `+`, 내장 타입과 연산자
조합 수단(means of combination)	`(op a b)` 하나뿐	연산자 식, 함수 호출, 복합 리터럴, 제어문
추상화 수단(means of abstraction)	`define`, `lambda`	`func`, 함수 리터럴, `type`

이 표에서 벌써 두 언어의 성격이 드러납니다. Scheme 은 조합 수단이 하나 입니다. 괄호로 감싸는 것뿐입니다. if 도, define 도, 함수 호출도 전부 같은 모양입니다. Go 는 조합 수단이 여럿이고, 각각 문법이 다릅니다. 함수 호출과 if 문과 for 문은 서로 다르게 생겼고 서로 자리를 바꿀 수 없습니다.

이 차이가 4장에서 청구서로 돌아옵니다. 조합 수단이 하나면 파서가 필요 없습니다.

치환 모델#

1.1.5 에서 원서는 프로시저 호출이 무엇을 하는지 설명하는 첫 번째 모델을 내놓습니다. 치환 모델(substitution model) 입니다. 규칙은 하나입니다. 프로시저 호출을 만나면, 프로시저 본문에서 형식 인자를 실인자로 바꿔치기한 것으로 대체합니다.

func square(x int) int    { return x * x }
func sumOfSquares(x, y int) int { return square(x) + square(y) }
func f(a int) int         { return sumOfSquares(a+1, a*2) }

f(5) 를 치환 모델로 전개하면 이렇습니다.

f(5)
sumOfSquares(5+1, 5*2)
sumOfSquares(6, 10)
square(6) + square(10)
6*6 + 10*10
36 + 100
136

Go 에서도 그대로 맞습니다. 그런데 원서는 이 모델을 소개하자마자 유효기간을 붙입니다. 3장에서 대입을 도입하면 이 모델은 무너집니다. 같은 이름이 시점에 따라 다른 값을 가리키게 되면, “바꿔치기” 라는 설명 자체가 성립하지 않기 때문입니다. 그래서 3장에서 환경 모델로 갈아탑니다.

교재가 자기가 가르친 모델의 폐기 시점을 미리 알려 주는 건 흔한 일이 아닙니다. 이 책은 이걸 자주 합니다.

블랙박스 추상화와 내부 정의#

1.1.8 의 요점은 프로시저를 블랙박스로 쓸 수 있어야 한다 는 것입니다. sqrt 를 쓰는 쪽은 goodEnough 나 improve 라는 이름을 알 필요가 없고, 알아서도 안 됩니다. 그 이름들이 바깥으로 새어 나오면 이름 공간이 오염됩니다.

Scheme 은 프로시저 안에 프로시저를 정의해서 해결합니다. Go 에도 같은 것이 있습니다. 함수 리터럴입니다.

func sqrt(x float64) float64 {
	goodEnough := func(guess, next float64) bool {
		return abs(next-guess) < abs(guess)*1e-12
	}
	improve := func(guess float64) float64 {
		return (guess + x/guess) / 2 // x 를 인자로 안 받아도 된다
	}
	guess := 1.0
	for {
		next := improve(guess)
		if goodEnough(guess, next) {
			return next
		}
		guess = next
	}
}

improve 가 x 를 인자로 받지 않는 데 주목할 만합니다. 바깥 스코프의 x 를 그냥 씁니다. 원서가 “어휘 유효범위(lexical scoping)” 라고 부르는 것이고, Go 의 함수 리터럴도 똑같이 동작합니다. 여기까지는 Go 가 원서를 그대로 따라갑니다.

3. 1.2 — 코드의 모양과 실행의 모양은 다릅니다#

이제 이 책의 첫 번째 큰 아이디어입니다.

계승(factorial)을 두 가지로 쓸 수 있습니다.

// (a) 곱셈을 나중으로 미룬다
func factRec(n int) int {
	if n == 1 {
		return 1
	}
	return n * factRec(n-1)
}

// (b) 곱셈을 그때그때 끝낸다
func factIter(n int) int {
	product, counter := 1, 1
	for counter <= n {
		product, counter = counter*product, counter+1
	}
	return product
}

둘 다 6에 대해 720 을 냅니다. 호출 횟수도 6회로 같습니다.

factRec(6)  = 720   호출 횟수: 6
factIter(6) = 720   루프 횟수: 6

같은 답, 같은 횟수. 그런데 원서는 이 둘이 근본적으로 다른 프로세스 라고 말합니다. 차이는 시간이 아니라 공간 입니다.

flowchart TD
    subgraph ITER["(b) 반복 프로세스 — 상태 변수 두 개면 끝"]
        direction TB
        I1["product=1<br/>counter=1"] --> I2["product=1<br/>counter=2"]
        I2 --> I3["product=2<br/>counter=3"]
        I3 --> I4["…"]
        I4 --> I5["product=720<br/>counter=7"]
    end
    subgraph REC["(a) 재귀 프로세스 — 미룬 연산이 쌓인다"]
        direction TB
        R1["fact(6)"] --> R2["6 × fact(5)"]
        R2 --> R3["6 × (5 × fact(4))"]
        R3 --> R4["6 × (5 × (4 × (3 × (2 × 1))))<br/>여기가 최대 폭"]
        R4 --> R5["720<br/>되감으며 곱한다"]
    end
    style R4 fill:#FF9999,color:#000000
    style I5 fill:#90EE90,color:#000000

(a)는 n 이 커질수록 대기 중인 곱셈이 늘어납니다. 처리기는 그걸 어딘가에 기억해 둬야 하므로 공간이 O(n) 입니다. (b)는 무엇을 기억하든 변수 두 개면 충분하므로 공간이 O(1) 입니다.

원서가 강조하는 것은 여기서 한 걸음 더 나갑니다. (b)를 재귀적으로 써도 여전히 반복 프로세스 라는 것입니다.

// (c) 생긴 건 재귀, Scheme 에서라면 프로세스는 반복
func factTail(product, counter, n int) int {
	if counter > n {
		return product
	}
	return factTail(counter*product, counter+1, n)
}

factTail 은 마지막 동작이 자기 호출뿐입니다. 호출에서 돌아온 뒤 할 일이 없습니다. 그렇다면 돌아올 자리를 기억해 둘 이유가 없고, 처리기는 지금 프레임을 재활용하면 됩니다. Scheme 표준(R7RS)은 이것을 보장 합니다. 그래서 factTail 은 Scheme 에서 상수 공간으로 돕니다.

재귀적으로 생긴 프로시저 와 재귀적으로 동작하는 프로세스 는 다르다.

이게 1.2.1 의 결론이고, 이 책에서 가장 많이 인용되는 구분 중 하나입니다.

4. 마찰 하나 — Go 에서는 이 구분이 지워집니다#

그럼 Go 는 어떨까요. 재 보았습니다.

n = 1,000,000 에 대해 1부터 n 까지 더하는 세 버전 — 비꼬리 재귀, 꼬리 재귀, 루프 — 을 각각 별도 고루틴에서 돌리고 그 고루틴이 끝나는 시점의 runtime.MemStats.StackInuse 를 읽었습니다. go1.26.0 darwin/arm64 입니다.

n = 1000000, 결과 일치 = true
(a) 재귀 프로세스(비꼬리) StackInuse =   16.25 MB
(b) 꼬리 재귀            StackInuse =   16.25 MB
(c) 루프                 StackInuse =    0.25 MB

(a)와 (b)가 소수점까지 같습니다.

Go 는 꼬리 호출을 알아보지 않습니다. return factTail(...) 은 그냥 함수 호출이고, 호출한 만큼 프레임이 쌓입니다. Scheme 에서 (b)를 (c)로 만들어 주던 것은 언어가 해 주던 일 이었고, Go 에는 그 일을 하는 사람이 없습니다.

그래서 SICP 1.2.1 의 결론을 Go 로 번역하면 이렇게 됩니다.

Go 에서 재귀적으로 생긴 프로시저는 항상 재귀 프로세스를 만든다. 반복 프로세스를 원하면 반복문으로 써야 한다.

깊이를 더 밀면 죽습니다. 최대 스택을 16 MB 로 낮추고 1억 번 꼬리 재귀를 돌리면 이렇게 끝납니다.

runtime: goroutine stack exceeds 16777216-byte limit
fatal error: stack overflow

64비트 기본 상한은 1 GB 입니다. 넉넉해 보이지만 상한은 상한입니다.

왜 Go 는 안 해 주는가#

Go 팀이 게을러서가 아닙니다. 이유가 몇 가지 겹칩니다.

스택 트레이스. Go 는 패닉이 났을 때 호출 경로 전체를 보여 줍니다. 프레임을 재활용해 버리면 그 경로가 사라집니다. 디버깅 가능성을 언어의 기본값으로 삼은 언어에서는 큰 손실입니다.

defer 와의 상호작용. Go 의 defer 는 함수가 반환할 때 실행됩니다. 꼬리 호출을 프레임 재활용으로 구현하면 “이 함수가 반환하는 시점” 의 의미가 흐려집니다.

이동식 스택. Go 의 고루틴 스택은 작게 시작해서 필요하면 복사·확장됩니다. 그래서 재귀 깊이 한계가 다른 언어보다 훨씬 관대합니다. 위 측정에서 100만 깊이가 그냥 돌아간 것이 그 덕분입니다. 꼬리 호출 제거의 실익이 상대적으로 작습니다.

철학. Go 는 “무엇이 실행되는지가 코드에 그대로 보여야 한다” 는 쪽입니다. 컴파일러가 재귀를 조용히 루프로 바꾸는 것은 그 방향과 반대입니다.

그래서 어떻게 하나#

이 시리즈의 방침은 이렇습니다.

반복 프로세스가 필요하면 반복문으로 씁니다. 꼬리 재귀로 써 놓고 최적화되기를 바라지 않습니다.
깊이가 입력 크기에 비례하는 재귀는 명시적 스택으로 바꿉니다. 슬라이스 하나를 스택으로 쓰면 됩니다. 5장에서 이 변환의 원리가 나옵니다.
깊이가 로그인 재귀는 그냥 씁니다. log₂(10^18) 은 60 입니다. 문제가 되지 않습니다.

3번이 중요합니다. 재귀가 나쁘다는 이야기가 아닙니다. 트리 순회, 분할 정복, 파서처럼 깊이가 데이터 구조의 높이에 묶이는 재귀는 Go 에서도 아무 문제가 없습니다. 위험한 것은 깊이가 입력 개수에 비례하는 재귀뿐입니다.

그리고 예고편 하나. 5장의 명시적 제어 평가기가 다루는 주제가 정확히 “꼬리 호출을 어떻게 상수 공간으로 만드는가” 입니다. 지금 Go 가 안 해 주는 그 일을, 우리가 만든 평가기 안에서는 직접 구현합니다. 1장에서 손해 본 걸 5장에서 되찾습니다.

5. 1.2.2 트리 재귀 — 값을 두 번 부르면 벌어지는 일#

피보나치를 정의 그대로 옮기면 이렇게 됩니다.

func fib(n int) int {
	switch {
	case n == 0:
		return 0
	case n == 1:
		return 1
	default:
		return fib(n-1) + fib(n-2)
	}
}

호출 횟수를 세어 보면 이렇습니다.

fib(10) = 55       호출 횟수 = 177
fib(20) = 6765     호출 횟수 = 21891
fib(30) = 832040   호출 횟수 = 2692537

n 이 10 늘 때마다 호출이 120배 씩 늘어납니다. 정확히는 호출 횟수가 2·fib(n+1) − 1 이고, fib(n) 자체가 φⁿ 에 비례하므로 지수 시간 입니다.

원인은 단순합니다. fib(30) 은 fib(28) 을 두 번 계산합니다. fib(27) 은 세 번, fib(26) 은 다섯 번. 같은 답을 몇 번이고 다시 구합니다.

원서가 여기서 짚는 것은 “재귀는 느리다” 가 아닙니다. 트리 재귀의 비용은 트리의 노드 수이고, 공간은 트리의 깊이 라는 것입니다. 시간은 지수인데 공간은 O(n) 입니다. 두 자원이 따로 논다는 사실 자체가 요점입니다.

Go 로 옮길 때 유용한 지점이 여기 있습니다. fib 는 깊이가 n 이므로 4절의 분류에서 “위험한 재귀” 에 해당합니다. 그런데 실무에서 이걸 고치는 방법은 스택을 손으로 만드는 게 아니라 반복으로 바꾸는 것 입니다.

func fibIter(n int) int {
	a, b := 1, 0 // a=fib(1), b=fib(0)
	for i := 0; i < n; i++ {
		a, b = a+b, a
	}
	return b
}

선형 시간, 상수 공간. 변환의 요령은 4절과 같습니다. 무엇을 기억해야 하는지 알아내서 그것만 변수로 들고 도는 것 입니다. 여기서는 연속한 두 항이면 충분합니다.

6. 1.2.4 거듭제곱 — 절반으로 접기#

b^n 을 구하는 뻔한 방법은 b 를 n 번 곱하는 것입니다. Θ(n) 입니다.

원서는 여기서 관찰 하나로 지수를 로그로 떨어뜨립니다. n 이 짝수면 b^n = (b^(n/2))² 이므로, 한 번 제곱하는 것으로 지수가 반이 됩니다.

func fastExpt(b, n int) int {
	switch {
	case n == 0:
		return 1
	case n%2 == 0:
		h := fastExpt(b, n/2)
		return h * h // 한 번의 제곱으로 지수가 절반
	default:
		return b * fastExpt(b, n-1)
	}
}

측정입니다.

2^16     단순 곱셈 16회   | fast-expt 호출 6회
2^1000   단순 곱셈 1000회 | fast-expt 호출 16회

지수가 62배 커졌는데 일은 2.7배만 늘었습니다. Θ(log n) 입니다.

주의할 점은 h := fastExpt(b, n/2) 로 한 번만 부르고 변수에 담은 것 입니다. return fastExpt(b, n/2) * fastExpt(b, n/2) 로 쓰면 두 번 계산하게 되어 로그가 다시 선형이 됩니다. 원서 연습문제 1.16 언저리가 이 함정을 다룹니다.

그리고 이 재귀는 깊이가 log₂ n 입니다. 4절 분류의 3번, 그냥 써도 되는 재귀 입니다. Go 에서 아무 문제 없습니다.

7. 1.2.5 유클리드 호제법 — 그리고 피보나치가 다시 나오는 이유#

최대공약수입니다.

func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

원서는 재귀로 쓰지만 꼬리 재귀이므로 Go 에서는 루프가 정답입니다. 4절의 방침 1번을 적용한 것입니다.

나머지 연산 횟수를 세어 보면 재미있는 게 나옵니다.

gcd(206, 40)         = 2    나머지 연산 4회
gcd(1071, 462)       = 21   나머지 연산 3회
gcd(121393, 75025)   = 1    나머지 연산 24회

마지막 줄의 두 수가 연속한 피보나치 수 입니다. 121393 = fib(26), 75025 = fib(25). 그리고 이 조합이 유클리드 호제법의 최악의 경우 입니다.

이게 라메(Lamé)의 정리입니다. 유클리드 호제법이 k 단계를 필요로 하려면 작은 쪽 수가 최소한 fib(k) 이상이어야 합니다. 뒤집으면, n 에 대한 단계 수는 log_φ(n) 에 비례합니다. 원서 1.2.5 절이 이 증명을 다룹니다.

같은 절 안에서 트리 재귀의 원흉이던 피보나치가 이번엔 복잡도 하한의 증인으로 돌아옵니다. 이런 배치가 우연이 아니라는 것이 이 책을 읽는 재미 중 하나입니다.

8. 1.2.6 소수 판정 — 그리고 알고리즘이 틀릴 수도 있다는 발상#

1장의 마지막 예제가 가장 흥미롭습니다.

가장 단순한 소수 판정은 2부터 √n 까지 나눠 보는 것입니다. Θ(√n) 입니다. 원서는 여기서 완전히 다른 접근을 꺼냅니다. 페르마의 소정리 입니다.

n 이 소수이면, n 보다 작은 모든 a 에 대해 aⁿ ≡ a (mod n) 이다.

이 명제의 역은 참이 아닙니다. 그런데 원서는 그걸 알면서도 역방향으로 씁니다. a 를 무작위로 뽑아 시험해서 통과하면 “아마 소수” 라고 답합니다. 여러 번 통과하면 확신이 커집니다.

핵심 부품은 expmod 입니다. b^e mod m 을 큰 수를 만들지 않고 구합니다.

func expmod(base, exp, m int) int {
	switch {
	case exp == 0:
		return 1
	case exp%2 == 0:
		h := expmod(base, exp/2, m)
		return (h * h) % m
	default:
		return (base * expmod(base, exp-1, m)) % m
	}
}

6절의 fastExpt 와 구조가 같습니다. 다른 점은 매 단계마다 mod m 을 한다 는 것뿐입니다. 이 한 줄 덕분에 중간값이 절대 커지지 않습니다. 2^1000 mod 561 을 구하는 데 1000자리 정수가 필요 없습니다.

원서가 이 알고리즘을 넣은 이유는 속도가 아닙니다. “확률적으로 맞는 알고리즘” 이라는 범주가 존재한다 는 것을 보여 주려는 것입니다. 항상 맞는 대신 느린 것과, 아주 드물게 틀리는 대신 빠른 것 중에서 고를 수 있다는 발상은 1985년 입문 교재에 나오기에는 상당히 앞서 있었습니다.

카마이클 수 — 전수 검증했습니다#

그리고 원서는 바로 다음 연습문제(1.27)에서 이 알고리즘의 급소를 찌릅니다. 페르마 시험을 완전히 속이는 합성수가 존재합니다.

561, 1105, 1729, 2465, 2821, 6601. 이들을 카마이클 수라고 부릅니다. 실제로 그런지 전수 검증해 봤습니다. 각 n 에 대해 1 ≤ a < n 인 모든 a 를 시험했습니다.

n       소수인가   a<n 전부에 대해 a^n≡a (mod n) 인가
561     false      true
1105    false      true
1729    false      true
2465    false      true
2821    false      true
6601    false      true
-- 대조군 --
15      false      false
91      false      false
563     true       true

전부 합성수인데 모든 a 를 통과합니다. 561 = 3 × 11 × 17 입니다. 무작위로 a 를 몇 개 뽑든, 100개를 뽑든, 561은 언제나 소수라고 답합니다. 확률로 방어할 수 없습니다.

대조군을 보면 대비가 분명합니다. 15와 91은 합성수답게 걸립니다. 563은 진짜 소수라서 통과합니다.

이 연습문제가 알려 주는 것은 “페르마 시험을 쓰지 말라” 가 아닙니다. 확률적 알고리즘의 실패 확률은 입력에 대한 가정 위에서만 계산된다 는 것입니다. 그 가정이 깨지는 입력이 존재하면 확률 논증이 통째로 무효가 됩니다. 실무에서 밀러-라빈(Miller–Rabin)을 쓰는 이유가 여기 있습니다. 밀러-라빈에는 카마이클 수 같은 보편 통과 합성수가 없습니다.

9. 이번 편의 정리#

1장 전반부에서 Go 로 얻은 결론입니다.

SICP 의 주장	Go 에서
프로시저를 이름 뒤에 감춰라	그대로 성립. 함수 리터럴로 내부 정의까지 동일
치환 모델로 호출을 이해하라	그대로 성립 (3장에서 함께 폐기됨)
재귀 프로시저 ≠ 재귀 프로세스	성립하지 않음. Go 에서 재귀 프로시저는 항상 재귀 프로세스
반복 프로세스는 상수 공간	반복문으로 쓸 때만 성립
Θ(log n) 알고리즘의 위력	그대로 성립. 로그 깊이 재귀는 Go 에서도 안전
확률적 알고리즘이라는 범주	그대로 성립. 카마이클 수도 그대로 재현됨

세 번째 줄이 이번 편의 요지입니다. 잃어버린 것은 언어 기능 하나지만, 잃어보고 나서야 그게 무엇이었는지 알게 됩니다. Scheme 으로 읽었다면 “꼬리 재귀는 상수 공간” 이라는 문장을 그냥 외우고 넘어갔을 것입니다. Go 로 읽으면 16.25 MB 라는 숫자를 보게 됩니다.

다음 편은 1장 후반부, 프로시저를 값으로 다루기 입니다. 함수를 인자로 넘기고 함수를 반환하는 그 이야기인데, Go 로 하면 원서보다 오히려 재미있는 구석이 있습니다. 타입이 있기 때문입니다. func(float64) float64 를 인자로 받는 함수를 쓰다 보면, 원서가 동적 타입 뒤에 감춰 두었던 추상화의 실제 모양 이 타입 시그니처로 드러납니다.

References#

1차 자료

Abelson, H., Sussman, G. J., with Sussman, J. Structure and Interpretation of Computer Programs, 2nd ed. MIT Press, 1996. CC BY-SA 4.0. 1장 전문 — https://sarabander.github.io/sicp/html/1_002e1.xhtml , https://sarabander.github.io/sicp/html/1_002e2.xhtml
연습문제 1.7 (제곱근 판정 기준), 1.16 (반복적 fast-expt), 1.27 (카마이클 수)는 위 원문의 해당 절에 있습니다.
R7RS Scheme 표준의 꼬리 호출 보장 — Scheme 은 꼬리 위치의 호출이 상수 공간에서 실행됨을 언어 차원에서 요구합니다.

본문의 실측 데이터

스택 사용량, 호출 횟수, 곱셈 횟수, 나머지 연산 횟수는 모두 go version go1.26.0 darwin/arm64 에서 직접 실행해 얻은 값입니다.
카마이클 수 6개는 각각 1 ≤ a < n 인 모든 a 에 대해 전수 검증했습니다. 대조군(15, 91, 563)도 같은 방법으로 확인했습니다.

시리즈

Part 1: 마법사 책은 왜 아직도 살아 있나