호프스태터 G수열 계산기

G(n)=n-G(G(n-1)) 점화식으로 호프스태터 G수열의 n번째 항을 계산하고, 황금비로 바로 구해지는 닫힌 식 ⌊(n+1)/φ⌋과 대조합니다.

몇 번째 항

번째

G(0)=0부터 셉니다.

G(20)

20 − G(G(19)) = 20 − G(12) = 20 − 8 = 12

닫힌 식 ⌊(n+1)/φ⌋12

재귀식과 일치하는가일치

n	G(n)
8	5
9	6
10	6
11	7
12	8
13	8
14	9
15	9
16	10
17	11
18	11
19	12
20	12

G(n-1)의 값을 다시 G의 인자로 넣는 재귀입니다. G(n)=n−G(G(n−1))에서 안쪽 G(n−1)을 먼저 구하고, 그 결과를 다시 바깥쪽 G에 넣어야 값이 나옵니다 — 재귀 호출의 결과가 재귀 호출의 인자가 되는 셈입니다.

닫힌 식 G(n) = ⌊(n+1)/φ⌋로 바로 구해집니다 (φ ≈ 1.6180339887). 재귀로 계산한 값과 닫힌 식이 모든 n에서 정확히 일치합니다. 더 유명한 호프스태터 Q수열은 일부 n에서 계산 도중 정의역을 벗어날 수 있는지가 아직 완전히 밝혀지지 않았지만, G수열은 모든 n에서 well-defined임이 증명되어 있어 이 계산기가 다루는 대상으로 골랐습니다.

재귀를 메모이제이션 없이 그대로 구현하면 계산이 지수적으로 느려지므로, G(0)부터 순서대로 채워 올라가는 반복(DP) 방식으로 계산합니다.

계산 방법

1몇 번째 항을 볼지 입력합니다(G(0)부터 셉니다).
2G(n) 값을 재귀 점화식과 닫힌 식(황금비) 두 방식으로 계산해 서로 대조합니다.
3앞선 항들의 표에서 점화식이 실제로 어떻게 이어지는지 볼 수 있습니다.

자주 묻는 질문

G(0)=0으로 시작해서 G(n)=n−G(G(n−1))로 이어지는 수열입니다. 더글러스 호프스태터의 《괴델, 에셔, 바흐》에 나오는 "메타 피보나치" 수열 계열 중 하나로, G(n-1)의 결과를 다시 G의 인자로 넣는 재귀가 특징입니다.

다릅니다. Q수열(Q(n)=Q(n−Q(n−1))+Q(n−Q(n−2)))은 계산 도중 정의역을 벗어날 수 있는지가 아직 완전히 밝혀지지 않은 미해결 문제로 유명합니다. 반면 G수열은 모든 n에서 well-defined임이 증명되어 있고, 아래 닫힌 식과 정확히 일치한다는 것도 확인되어 있습니다. 이 계산기가 Q수열이 아니라 G수열을 다루는 이유입니다.

G(n) = ⌊(n+1)/φ⌋ (φ는 황금비 ≈1.618)이라는 닫힌 식이 성립합니다. 재귀로 계산한 값과 이 닫힌 식이 모든 n에서 정확히 같습니다 — 이 계산기는 두 방식을 각각 계산해 서로 대조하는 근거로 함께 보여줍니다.

G(n+1)−G(n)은 항상 0 또는 1입니다. 한 항에서 다음 항으로 갈 때 그대로 머물거나 1만큼만 늘어나며, 그 결과 계단 모양으로 완만하게 증가합니다.

아니요. 모든 계산은 브라우저 안에서만 이뤄지며 서버로 전송되지 않습니다.

알아두면 좋은 점

재귀를 메모이제이션 없이 그대로 구현하면 계산이 지수적으로 느려지므로, G(0)부터 순서대로 채워 올라가는 반복(DP) 방식으로 계산합니다.
표에 담을 항 번호에 상한을 두어 브라우저에서 바로 계산할 수 있는 범위로 제한합니다.

마지막 검증: 2026년 9월 8일 · 결과는 참고용 추정치입니다.

계산 방법

자주 묻는 질문

호프스태터 G수열이 뭔가요?

더 유명한 호프스태터 Q수열과는 다른가요?

황금비랑 무슨 관계가 있나요?

G(n)은 한 번에 얼마나 늘어나나요?

입력값이 서버로 전송되나요?

알아두면 좋은 점

함께 보면 좋은 도구