홍라이프 계산기조화수 계산기 쉽게 이해하기 — 개념과 원리
이 계산기는 조화수 Hₙ = 1 + 1/2 + 1/3 + … + 1/n을 구하며, n이 작으면 정확한 분수로 보여 줍니다. 근사식 ln n + γ + 1/(2n), Hₙ − ln n, 항들의 평균도 알려 주고, Hₙ이 목표값에 이르는 가장 작은 n을 찾습니다. 미적분의 조화급수, 알고리즘 분석, 쿠폰 수집 문제 같은 확률 퍼즐에 쓸 수 있습니다.
계산 방법
Hₙ = Σ_(k=1)^n 1/k
근사: Hₙ ≈ ln n + γ + 1/(2n) − 1/(12n²) + …, γ ≈ 0.5772156649
- n ≤ 1,000이면 항을 정확히 더하고, 그보다 크면 점근 급수를 써서 n이 10¹⁵까지 가능합니다.
- n ≤ 20이면 정확한 분수를 보여 줍니다.
원리
각 항 1/k는 폭 1, 높이 1/k인 띠의 넓이이고, 이 띠들은 곡선 y = 1/x 바로 위에 놓입니다. 1부터 n까지 그 곡선 아래 넓이가 ln n이므로, Hₙ은 ln n처럼 느리지만 끝없이 커집니다. 곧 조화급수는 발산합니다. 띠와 곡선 사이에 남는 조각들은 합쳐서 일정한 값, 오일러-마스케로니 상수 γ에 수렴하며, 그래서 Hₙ − ln n이 0.5772에 가까워집니다.
예제 풀이
기본값: n = 10, 목표 5.
- H₁₀ = 1 + 1/2 + … + 1/10 = 7381/2520 = 2.928968254입니다.
- 근사값: ln 10 + 0.5772157 + 1/20 = 2.302585 + 0.577216 + 0.05 = 2.929800758입니다.
- H₁₀ − ln 10 = 0.626383161로, γ를 향해 줄어드는 중입니다.
- 항들의 평균 = 2.928968254 ÷ 10 = 0.2928968254입니다.
- Hₙ ≥ 5가 되는 가장 작은 n = 83입니다.
결과 해석
증가가 극도로 느립니다. 5를 넘으려면 83개 항, 10을 넘으려면 약 12,367개 항이 필요합니다. 쿠폰 수집 문제에서 서로 다른 쿠폰 n종을 모두 모으는 데 평균 n·Hₙ번 뽑아야 하므로, 10종이면 약 29.3번입니다. 과자에 든 스티커 10종을 모두 모으려면 평균 30개 가까이 사야 한다는 뜻이며, 마지막 몇 종이 특히 오래 걸립니다. 같은 조화수가 정렬 알고리즘의 평균 비교 횟수 분석에도 나옵니다.
흔한 실수
- 항이 0으로 가니 조화급수가 수렴한다고 생각하는 경우
- ln n만 써서 약 0.58만큼 틀리는 경우
- Hₙ을 조화평균과 혼동하는 경우
- Hₙ이 정수일 것이라 기대하는 경우(n > 1이면 절대 정수가 아닙니다)
- 1/0처럼 0번째 항부터 더하려는 경우
자주 묻는 질문
조화급수는 수렴하나요?
아닙니다. 대략 ln n처럼 끝없이 커집니다.
H₁₀은?
7381/2520 ≈ 2.929입니다.
오일러-마스케로니 상수란?
Hₙ − ln n의 극한값으로, 약 0.5772입니다.
목표값 기능은 어디에 쓰나요?
합이 어떤 값을 넘으려면 항이 몇 개 필요한지 확인할 때 씁니다.
출처: E. W. Weisstein, "Harmonic Number", Wolfram MathWorld