조화수 (Harmonic Number)

정의

조화수 (Harmonic Number) H_n 은 자연수 n 에 대해 역수의 합 Σ_{k=1}^{n} 1/k 으로 정의. 점근적으로 H_n = ln n + γ + 1/(2n) - ... (γ ≈ 0.5772, 오일러-마스케로니 상수). 정수론과 알고리즘 분석에서 O(n log n) 의 log factor 가 사실은 H_n 에서 비롯.

문제 상황과 동기

n = 10^6 일 때 Σ_{k=1}^{n} ⌊n/k⌋ 또는 약수 배수 관계의 합.

• naive (이중 루프): O(n²). n=10^5 면 10^10, 불가능.
• 조화수 통찰: n/k 의 서로 다른 값은 O(√n) 개. 구간 나누기로 O(√n) 또는 O(n log n).

핵심 통찰: ⌊n/k⌋ 는 k 가 작을 때는 자주 변하지만, k 가 클 때는 천천히 변한다. 따라서 같은 몫을 갖는 구간 을 한 번에 처리할 수 있다.

시각화

Floor Sum 블록 분할 흐름

Σ ⌊n/k⌋ 의 블록 분할 과정. 같은 몫을 갖는 구간을 한 번에 처리:

flowchart TD
    A["l = 1, sum = 0"] --> B{"l <= n?"}
    B -->|아니오| G[합계 반환]
    B -->|예| C["q = n / l  (현재 몫)"]
    C --> D["r = n / q  (같은 몫의 구간 끝)"]
    D --> E["sum += q * (r - l + 1)"]
    E --> F["l = r + 1  (다음 블록 시작)"]
    F --> B

블록 개수는 최대 2 * sqrt(n) 이므로 전체 O(sqrt(n)).

핵심 아이디어

조화수 점화

H_0 = 0
H_n = H_{n-1} + 1/n

구간 나누기 (harmonic lemma)

⌊n/k⌋ 의 값이 같은 k 의 구간 [l, r]:

r = n / (n / l)

이 구간 내에서 ⌊n/k⌋ = q 로 일정. 합을 q × (r - l + 1) 로 O(1) 에 계산.

이 기법은 각 구간을 묶어서 O(√n) 번의 연산으로 모든 ⌊n/k⌋ 의 합을 구하게 해 준다.

약수 배수 합

Σ_{i=1}^{n} d(i) = Σ_{i=1}^{n} ⌊n/i⌋ = 2 Σ_{i=1}^{√n} ⌊n/i⌋ - (⌊√n⌋)²

조화수와 O(n log n) 복잡도

n 개의 원소에 대해 i 의 배수를 모두 방문하는 패턴:

for i = 1 to n:
    for j = i, 2i, 3i, ... <= n:
        f(j)

총 방문 횟수 = n/1 + n/2 + n/3 + ... + n/n = H_n * n = O(n log n)

에라토스테네스의 체, 약수 열거, 소수 판별 등에서 이 패턴이 나타날 때마다 O(n log n).

점근 근사

H_n - ln(n) → γ 로 수렴. n 이 커질수록 근사 오차 0.

알고리즘

harmonic_sum(n):
    sum = 0
    for i = 1..n:
        sum += 1.0 / i
    return sum

harmonic_floor_sum(n):        # Σ ⌊n/i⌋
    sum = 0
    l = 1
    while l <= n:
        q = n // l
        r = n // q
        sum += q * (r - l + 1)
        l = r + 1
    return sum

구현

// H_n 계산 + harmonic floor sum O(sqrt(n))
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
​
double harmonic(int n) {
  double h = 0;
  for (int i = 1; i <= n; i++) h += 1.0 / i;
  return h;
}
​
ll floor_sum(ll n) {
  ll sum = 0;
  for (ll l = 1, r; l <= n; l = r + 1) {
      ll q = n / l;
      r = n / q;
      sum += q * (r - l + 1);
  }
  return sum;
}
​
int main() {
  int n; cin >> n;
  cout << fixed << setprecision(10);
  cout << "H_" << n << " = " << harmonic(n) << "\n";
  cout << "Sigma n/i = " << floor_sum(n) << "\n";
  return 0;
}

# H_n (float) + harmonic floor sum O(sqrt(n))
def harmonic(n):
  h = 0.0
  for i in range(1, n + 1):
      h += 1.0 / i
  return h
​
def floor_sum(n):
  s = l = 0
  while l < n:
      l += 1
      q = n // l
      r = n // q
      s += q * (r - l + 1)
      l = r
  return s
​
import sys
n = int(sys.stdin.readline())
print(f"H_{n} = {harmonic(n):.10f}")
print(f"Sigma n/i = {floor_sum(n)}")

10

H_10 = 2.9289682540
Sigma n/i = 27

1000000

H_1000000 = 14.3927267229
Sigma n/i = 13970034

복잡도

변형 / 활용

2D floor sum (확장)

2차원 버전: Σ_{i=1}^{n} Σ_{j=1}^{m} ⌊(ai+bj+c) / d⌋. 주로 격자 점 개수 계산에 등장. 복잡도 O(log max(n,m)) 의 floor_sum 라이브러리 함수 (C++17 atcoder/math.hpp) 로 처리.

약수 개수 합 O(√n) 구현 (확장)

D(n) = Σ_{i=1}^{n} d(i)  (d(i) = 약수 개수)

= 2 * Σ_{i=1}^{floor(√n)} floor(n/i) - floor(√n)^2

이 공식으로 O(√n) 에 1 부터 n 까지 모든 약수 개수 합 계산.

함정

1. 부동소수점 정밀도

H_n 은 float/double 로 n ≥ 10^7 이면 오차 누적. 큰 n 에 대해서는 log(n) + γ 근사식 사용.

2. 64-bit 오버플로우

floor_sum(n) 에서 n=10^12 면 q * (r-l+1) 이 long long 초과 가능. unsigned long long 또는 __int128 필요.

3. 구간 경계 실수

l = r + 1 에서 l 이 n+1 이면 루프 종료. r = n / (n / l) 에서 n / l == 0 이면 0으로 나누기 방지: l > n 이면 break.

4. 에라토스테네스 체와 혼동

조화수의 O(n log n) 분석을 에라토스테네스 체 O(n log log n) 과 혼동하는 경우 있음. 체는 소수에만 방문하므로 log log n. 배수 전체 방문은 H_n * n = O(n log n).

BOJ 연습 문제

참고

• 에라토스테네스의 체 (약수 관련)
• 뫼비우스 함수 (반전 공식)
• 포함 배제의 원리