Project Euler 2: 짝수 피보나치 수만 골라 더하기
피보나치 수열에서 짝수 항이 세 칸마다 나온다는 사실을 증명하고, 짝수 항끼리의 점화식 E(k) = 4E(k−1) + E(k−2)를 유도해 사백만 이하의 짝수 항만 더합니다. C++17과 Python 3 구현, 정확성 증명, 정수 범위까지 다룹니다.
스포일러 주의 · 이 글에는 풀이 과정과 정답이 그대로 나옵니다. 직접 먼저 풀어 보고 싶다면 Project Euler 2번 문제부터 보세요.
Project Euler 시리즈의 두 번째 문제입니다. 피보나치 수열을 차례로 만들면서 짝수만 더해도 풀리지만, 짝수 항이 어디에 나오는지를 먼저 따져 보면 짝수 항만 곧바로 이어 만드는 점화식을 얻을 수 있습니다. 홀짝(2로 나눈 나머지)을 따라가는 방법과 점화식을 변형하는 방법은 뒤의 문제에서도 자주 쓰입니다.
스포일러 주의: 이 글에는 풀이 전체와 정답이 들어 있습니다. 직접 먼저 풀어 보고 싶다면 원래 문제부터 보세요. 이 시리즈의 글에는 광고를 싣지 않습니다. 문제 본문의 라이선스(CC BY-NC-SA 4.0)가 비영리 조건을 두기 때문입니다.
문제
1과 2로 시작하고, 그다음 항부터는 바로 앞의 두 항을 더해 만드는 피보나치 수열을 생각합니다. 처음 몇 항은 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …입니다. 이 가운데 값이 사백만(4,000,000)을 넘지 않는 항만 보고, 그중 짝수인 항을 모두 더한 값을 구합니다.
경계는 “넘지 않는다”, 즉 4,000,000 이하입니다. 4,000,000 자체는 피보나치 수가 아니어서 이 문제에서는 “미만”으로 읽어도 답이 같지만, 함수로 일반화할 때는 이하로 정확히 구현해 둡니다.
필요한 배경 지식
피보나치 수열과 번호 붙이기. 이 글에서는 문제의 시작값을 그대로 따라 F₁ = 1, F₂ = 2로 두고, n ≥ 3이면 Fₙ = Fₙ₋₁ + Fₙ₋₂로 정의합니다. 그러면 F₃ = 3, F₄ = 5, F₅ = 8, F₆ = 13, F₇ = 21, F₈ = 34입니다. 흔히 보는 1, 1, 2, 3, …과는 번호가 하나씩 어긋나므로, 다른 자료의 공식을 가져올 때는 번호를 맞춰야 합니다.
수열은 순증가합니다. F₂ > F₁이고, n ≥ 3이면 Fₙ = Fₙ₋₁ + Fₙ₋₂ > Fₙ₋₁입니다(모든 항이 양수이므로). 그래서 같은 값이 두 번 나오지 않고, 어떤 항이 상한을 넘으면 그 뒤의 항도 모두 넘습니다. “상한을 넘으면 멈춘다”는 반복이 옳은 근거가 이것입니다.
홀짝의 덧셈. 짝수 + 짝수 = 짝수, 짝수 + 홀수 = 홀수, 홀수 + 홀수 = 짝수입니다. 2로 나눈 나머지끼리 더한 뒤 다시 2로 나눈 나머지를 보면 되기 때문입니다(0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 2 → 0). 피보나치 수열의 각 항은 앞의 두 항의 합이므로, 앞의 두 항의 홀짝만 알면 다음 항의 홀짝이 정해집니다.
지수적 증가. 항이 지수적으로 커지면 상한 N 아래의 항 수는 N이 아니라 log N에 비례합니다. 아래 “복잡도”에서 짝수 항에 대해 구체적인 부등식으로 보입니다.
가장 단순한 방법
가장 먼저 떠오르는 방법은 두 가지입니다.
- 1부터 4,000,000까지 모든 정수를 보면서 피보나치 수인지, 짝수인지 확인합니다. 정수를 하나씩 보므로 상한 N에 대해 O(N)번 이상의 확인이 필요하고, 피보나치 수인지 판정하는 비용도 따로 듭니다.
- 피보나치 수열을 직접 만들면서, 상한 이하인 항 중 짝수인 것만 더합니다.
a, b = 1, 2
total = 0
while a <= 4000000:
if a % 2 == 0:
total += a
a, b = b, a + b두 번째 방법은 이미 충분히 빠릅니다. 피보나치 수가 지수적으로 커지므로 4,000,000 이하의 항은 32개뿐이고, 반복도 32번이면 끝납니다. 시간 복잡도는 O(log N), 공간은 O(1)입니다. 그런데 이 32개 중 실제로 더하는 짝수 항은 11개이고, 나머지 21번은 홀짝을 확인하고 버리는 데 씁니다. 아래에서는 짝수 항이 정확히 어디에 나오는지 증명하고, 짝수 항만 곧바로 만드는 점화식을 유도합니다. 점근적인 복잡도는 같지만 반복 횟수가 약 3분의 1로 줄고 홀짝 검사가 사라지며, 무엇보다 “왜 그런지”를 식으로 설명할 수 있습니다.
풀이 유도
1단계: 작은 예로 패턴을 봅니다. 처음 열 항과 홀짝을 나란히 적어 봅니다.
n : 1 2 3 4 5 6 7 8 9 10
Fₙ : 1 2 3 5 8 13 21 34 55 89
홀짝: 홀 짝 홀 홀 짝 홀 홀 짝 홀 홀짝수 항은 F₂ = 2, F₅ = 8, F₈ = 34로, 번호가 2, 5, 8처럼 세 칸마다 나옵니다. 89 이하의 짝수 항의 합은 2 + 8 + 34 = 44입니다. 이 값은 뒤에서 코드의 작은 예 검사에 씁니다.
2단계: 짝수 항이 정확히 세 칸마다 나온다는 것을 증명합니다. 연속한 두 항의 홀짝 쌍 (Fₙ, Fₙ₊₁)을 봅니다. 다음 쌍은 (Fₙ₊₁, Fₙ + Fₙ₊₁)이므로 지금 쌍만으로 정해집니다.
(홀, 짝) → (짝, 홀 + 짝 = 홀) → (홀, 짝 + 홀 = 홀) → (홀, 홀 + 홀 = 짝) → (홀, 짝) → …첫 쌍 (F₁, F₂) = (1, 2)가 (홀, 짝)이고, 세 번 넘어가면 다시 (홀, 짝)으로 돌아옵니다. 다음 쌍이 지금 쌍에 의해서만 정해지므로 이 주기 3의 순환은 끝없이 반복됩니다. 따라서 Fₙ이 짝수인 것은 n을 3으로 나눈 나머지가 2일 때, 즉 n = 3k − 1 (k = 1, 2, 3, …)일 때뿐입니다. 이제 짝수 항을 Eₖ = F₃ₖ₋₁로 부르겠습니다. E₁ = F₂ = 2, E₂ = F₅ = 8, E₃ = F₈ = 34입니다.
3단계: 세 칸 떨어진 항 사이의 관계를 만듭니다. n ≥ 7이면 정의 Fₘ = Fₘ₋₁ + Fₘ₋₂를 m = n, n − 1, n − 2, n − 4에 쓸 수 있습니다(모두 3 이상). 한 단계씩 풀어 씁니다.
Fₙ = Fₙ₋₁ + Fₙ₋₂
= (Fₙ₋₂ + Fₙ₋₃) + Fₙ₋₂ ← Fₙ₋₁을 풀어 씀
= 2Fₙ₋₂ + Fₙ₋₃
= 2(Fₙ₋₃ + Fₙ₋₄) + Fₙ₋₃ ← Fₙ₋₂를 풀어 씀
= 3Fₙ₋₃ + 2Fₙ₋₄
= 3Fₙ₋₃ + Fₙ₋₄ + (Fₙ₋₅ + Fₙ₋₆) ← Fₙ₋₄ 하나를 풀어 씀
= 3Fₙ₋₃ + (Fₙ₋₄ + Fₙ₋₅) + Fₙ₋₆
= 3Fₙ₋₃ + Fₙ₋₃ + Fₙ₋₆ ← Fₙ₋₄ + Fₙ₋₅ = Fₙ₋₃
= 4Fₙ₋₃ + Fₙ₋₆마지막 줄의 Fₙ₋₄ + Fₙ₋₅ = Fₙ₋₃도 정의를 m = n − 3에 쓴 것이고, n ≥ 7이면 n − 3 ≥ 4라서 쓸 수 있습니다.
4단계: 짝수 항끼리의 점화식으로 바꿉니다. n = 3k − 1을 넣으면 n − 3 = 3(k − 1) − 1, n − 6 = 3(k − 2) − 1이므로
Eₖ = 4Eₖ₋₁ + Eₖ₋₂ (k ≥ 3, 이때 n = 3k − 1 ≥ 8 ≥ 7)입니다. 손으로 검산하면 E₃ = 4 · 8 + 2 = 34, E₄ = 4 · 34 + 8 = 144이고, 실제로 F₁₁ = 144입니다(F₉ = 55, F₁₀ = 89, F₁₁ = 144).
5단계: 시작값을 정리합니다. 점화식은 k ≥ 3부터 증명했으므로 E₁ = 2, E₂ = 8을 시작값으로 두면 됩니다. 코드에서는 편의상 E₀ = 0을 하나 더 둡니다. 4 · E₁ + E₀ = 4 · 2 + 0 = 8 = E₂이므로, (E₀, E₁) = (0, 2)에서 출발해도 같은 식으로 E₂부터 올바르게 이어집니다. E₀은 더하지 않는 보조값일 뿐입니다.
최종 알고리즘
상한을 limit이라고 하면:
previous = 0(E₀),current = 2(E₁),sum = 0으로 시작합니다.current ≤ limit인 동안sum에current를 더하고,(previous, current)를(current, 4 · current + previous)로 바꿉니다.current > limit이 되면sum을 돌려줍니다.- 정답을 출력하기 전에 작은 상한에서 결과를 확인합니다. 1 → 0(짝수 항 없음), 2 → 2, 8 → 2 + 8 = 10(경계 값을 포함하는지 확인), 89 → 44(1단계의 예). 하나라도 다르면 0이 아닌 종료 코드로 끝냅니다.
C++ 구현에는 아주 큰 상한에서 다음 항을 계산하다 넘치지 않도록 하는 검사가 하나 더 있습니다. 아래 “정수 범위”에서 설명합니다.
정확성 증명
반복문이 j번째 검사(j = 1, 2, …)를 할 때 다음이 성립합니다(불변식).
previous = Eⱼ₋₁,current = Eⱼsum = E₁ + E₂ + … + Eⱼ₋₁
처음(j = 1)에는 previous = 0 = E₀, current = 2 = E₁, sum = 0(빈 합)이므로 성립합니다. current ≤ limit이면 sum에 Eⱼ를 더해 E₁ + … + Eⱼ가 되고, 새 current는 4Eⱼ + Eⱼ₋₁ = Eⱼ₊₁(j = 1이면 5단계, j ≥ 2이면 4단계의 점화식), 새 previous는 Eⱼ이므로 j + 1에서도 성립합니다.
E는 피보나치 수열의 일부이므로 순증가하고, 언젠가 반드시 limit을 넘습니다. 처음으로 Eⱼ > limit이 되는 순간 반복이 끝나고, 이때 sum = E₁ + … + Eⱼ₋₁입니다. 순증가이므로 E₁, …, Eⱼ₋₁은 모두 limit 이하이고 Eⱼ 이후는 모두 limit을 넘습니다. 2단계에서 짝수인 피보나치 항은 정확히 E₁, E₂, …임을 보였고, 수열이 순증가하므로 각 값은 한 번씩만 나옵니다. 따라서 sum은 limit 이하인 짝수 피보나치 항의 합과 정확히 같습니다.
복잡도
반복 횟수. k ≥ 3이면 Eₖ = 4Eₖ₋₁ + Eₖ₋₂ > 4Eₖ₋₁이고, E₂ = 8 = 4E₁이므로 k ≥ 2에서 Eₖ ≥ 4Eₖ₋₁입니다. 따라서 Eₖ ≥ 2 · 4^(k−1)이고, limit 이하인 짝수 항의 개수 K는 2 · 4^(K−1) ≤ limit에서 K ≤ 1 + log₄(limit / 2)입니다. limit = 4,000,000이면 log₄(2,000,000) ≈ 10.47이라 K ≤ 11이고, 실제로 11개입니다. 반복 횟수가 O(log limit)이고 한 번의 반복은 고정 폭 정수에서 상수 시간이므로 시간 복잡도는 O(log limit), 저장하는 값이 세 개뿐이므로 공간 복잡도는 O(1)입니다.
정수 범위. 이 문제의 값은 모두 작습니다. 더하는 마지막 짝수 항이 사백만 이하이고, 반복을 끝낼 때 만드는 다음 짝수 항도 1,500만 정도라 32비트 정수에도 들어갑니다. 그래도 함수를 다른 상한에 다시 쓸 수 있도록 범위를 따져 둡니다.
- 합의 크기: 위의
Eⱼ₋₁ ≤ Eⱼ / 4를 거듭 쓰면, 마지막으로 더한 항을 E_K라 할 때 합은E_K (1 + 1/4 + 1/16 + …) < (4/3) E_K ≤ (4/3) limit입니다. 그래서 합은 언제나 상한의 4/3배보다 작습니다. - C++는
unsigned long long을 씁니다. C++ 표준은 이 타입이 최소 64비트임을 보장하고(C 표준의ULLONG_MAX최솟값을 따름), 부호 없는 정수의 연산은 2^N을 법으로 정의되어 있어 정의되지 않은 동작이 생기지 않습니다. 다만 넘치면 조용히 틀린 값이 되므로 넘치지 않게 해야 합니다. - 다음 항
4 · current + previous는 상한이 2^64 가까이면 넘칠 수 있습니다. 넘쳐서 작은 값으로 돌아가면 반복이 끝나지 않거나 틀린 합을 더하게 됩니다. 그래서 C++ 구현은 다음 항을 계산하기 전에current > (limit − previous) / 4인지 봅니다. 정수에서4 · current > limit − previous는current > ⌊(limit − previous) / 4⌋와 같으므로, 이 조건이 참이면 다음 항이 limit을 넘는다는 뜻이고 반복은 어차피 끝납니다. 계산하지 않고 멈춰도 결과는 같습니다. 반복 안에서는 previous ≤ current ≤ limit이라limit − previous도 0 아래로 돌아가지 않습니다. - 이 검사 덕분에 다음 항은 limit 이하일 때만 계산되어 넘치지 않고, 합은 (4/3) limit보다 작으므로 limit ≤ 2^63이면 2^64보다 작습니다. 즉 C++ 함수는 limit ≤ 2^63에서 정확합니다.
- Python의
int는 정밀도에 제한이 없어 넘칠 일이 없으므로 이 검사를 두지 않았습니다. 알고리즘은 같습니다.
경계 사례
- limit < 2: 가장 작은 짝수 항 2보다 작으므로 짝수 항이 없고 결과는 0입니다. 반복 조건이 처음부터 거짓이라 따로 처리할 필요가 없습니다. Python에서는 0이나 음수를 넣어도 0이 됩니다. C++는 부호 없는 타입이라 음수를 받지 않습니다.
- limit이 짝수 항과 같을 때: “넘지 않는다”는 이하이므로 그 항도 더해야 합니다. limit = 2이면 2, limit = 8이면 10이어야 하고, 코드의 작은 예 검사에 이 두 경우가 들어 있습니다.
- 시작값이 1, 1일 때: 1, 1, 2, 3, …으로 시작하는 다른 정의에서는 1이 두 번 나오지만, 1은 홀수라 짝수 항의 합에는 영향이 없습니다. 이 문제에서 1과 2로 시작한다는 조건은 짝수 항의 합만 놓고 보면 결과를 바꾸지 않습니다.
- 아주 큰 limit (C++): 위의 정수 범위대로 limit ≤ 2^63에서 정확합니다. 그보다 크면 합이 넘칠 수 있습니다.
C++17 구현
#include <iostream>
// Sum of the even Fibonacci terms (1, 2, 3, 5, 8, ...) that do not exceed limit.
// The even terms are 2, 8, 34, ..., and each one is 4 * previous + the one before.
unsigned long long sum_even_fibonacci_up_to(unsigned long long limit) {
unsigned long long previous = 0;
unsigned long long current = 2;
unsigned long long sum = 0;
while (current <= limit) {
sum += current;
// previous <= current <= limit, so limit - previous does not wrap.
// If 4 * current + previous would exceed limit, stop before computing it.
if (current > (limit - previous) / 4) {
break;
}
const unsigned long long next = 4 * current + previous;
previous = current;
current = next;
}
return sum;
}
int main() {
if (sum_even_fibonacci_up_to(1) != 0 || sum_even_fibonacci_up_to(2) != 2 ||
sum_even_fibonacci_up_to(8) != 10 || sum_even_fibonacci_up_to(89) != 44) {
return 1;
}
std::cout << sum_even_fibonacci_up_to(4000000) << '\n';
return 0;
}작은 예의 확인은 assert가 아니라 if로 했습니다. assert는 NDEBUG가 정의된 빌드에서 사라지기 때문입니다. 확인이 하나라도 틀리면 return 1로 0이 아닌 종료 코드를 냅니다.
Python 3 구현
def sum_even_fibonacci_up_to(limit: int) -> int:
"""Sum of the even Fibonacci terms (1, 2, 3, 5, 8, ...) that do not exceed limit.
The even terms are 2, 8, 34, ..., and each one is 4 * previous + the one before.
"""
previous, current = 0, 2
total = 0
while current <= limit:
total += current
previous, current = current, 4 * current + previous
return total
def main() -> None:
if (
sum_even_fibonacci_up_to(1) != 0
or sum_even_fibonacci_up_to(2) != 2
or sum_even_fibonacci_up_to(8) != 10
or sum_even_fibonacci_up_to(89) != 44
):
raise SystemExit(1)
print(sum_even_fibonacci_up_to(4000000))
if __name__ == "__main__":
main()C++와 같은 알고리즘, 같은 작은 예입니다. previous, current = current, 4 * current + previous는 오른쪽을 모두 계산한 뒤 한꺼번에 대입하므로 임시 변수가 필요 없습니다. 작은 예가 틀리면 raise SystemExit(1)로 종료 코드 1을 냅니다. assert는 python -O로 실행하면 제거되므로 쓰지 않았습니다.
정답과 검증
점화식으로 사백만 이하의 짝수 항을 차례로 만들면 다음과 같습니다(괄호 안은 그때까지의 합).
E₁ = 2 (2)
E₂ = 8 (10)
E₃ = 4 · 8 + 2 = 34 (44)
E₄ = 4 · 34 + 8 = 144 (188)
E₅ = 4 · 144 + 34 = 610 (798)
E₆ = 4 · 610 + 144 = 2584 (3382)
E₇ = 4 · 2584 + 610 = 10946 (14328)
E₈ = 4 · 10946 + 2584 = 46368 (60696)
E₉ = 4 · 46368 + 10946 = 196418 (257114)
E₁₀ = 4 · 196418 + 46368 = 832040 (1089154)
E₁₁ = 4 · 832040 + 196418 = 3524578
E₁₂ = 4 · 3524578 + 832040 = 14930352 > 4,000,000 → 멈춤따라서 답은 1089154 + 3524578 = 4613732입니다.
검증은 세 겹으로 합니다.
- 작은 예. 두 프로그램 모두 답을 출력하기 전에 상한 1, 2, 8, 89의 결과가 0, 2, 10, 44인지 확인하고, 다르면 0이 아닌 종료 코드로 끝납니다. 89 이하의 값 44는 “풀이 유도” 1단계에서 처음 열 항으로 손으로도 확인했습니다.
- 두 구현의 일치. 이 시리즈의 저장소에서는 검사 스크립트가 C++ 코드를
g++ -std=c++17 -O2 -Wall -Wextra -Werror로 컴파일해 실행하고(경고도 실패로 처리), Python 코드를python3 -I -B로 실행합니다. 두 출력이 저장해 둔answer.txt와 바이트 단위로 같아야 하고, 0이 아닌 종료 코드나 시간 초과(C++ 1초, Python 10초)는 실패입니다. 시리즈 규칙상 이 검사를 통과한 코드만 글에 싣습니다. - 손 계산과 다른 방법. 위 표에서 각 항이 실제 피보나치 수인지(예: 610 = F₁₄, 2584 = F₁₇) 두 항씩 더해 가며 맞춰 볼 수 있습니다. “가장 단순한 방법”의 반복문으로 32개 항을 모두 만들고 짝수만 더해 같은 값이 나오는지 비교해 보는 것도 좋은 연습입니다.
더 생각해 볼 것
- 홀수 항의 합. 같은 상한 아래에서 홀수 항의 합은 어떻게 구할까요? 전체 항의 합에서 짝수 항의 합을 빼면 됩니다. 전체 합에는 F₁ + F₂ + … + Fₙ을 Fₙ₊₂로 나타내는 닫힌 식이 있으니, 이 글의 번호 붙이기(F₁ = 1, F₂ = 2)에 맞춰 직접 유도해 보세요.
- 다른 나머지. 3의 배수인 피보나치 항은 몇 칸마다 나올까요? 2단계처럼 (Fₙ mod 3, Fₙ₊₁ mod 3) 쌍을 따라가면 주기를 찾을 수 있습니다. 그 항들 사이에도 3단계와 같은 방식으로 점화식을 만들 수 있는지 따져 보세요.
- 세 칸 대신 m칸. 3단계의 전개를 일반화하면 Fₙ을 Fₙ₋ₘ과 Fₙ₋₂ₘ으로 나타낼 수 있습니다. m = 2일 때의 계수는 무엇이고, m = 3일 때 4가 나오는 이유는 무엇인지 확인해 보세요.
- 오버플로 실험. C++ 코드에서 넘침 검사를 빼고 limit에
ULLONG_MAX에 가까운 값을 넣으면 어떤 일이 생기는지, 또 limit이 2^63보다 클 때 합이 실제로 넘치는지 Python의 결과와 비교해 보세요. - 이 시리즈의 다음 문제들. 피보나치 수와 점화식은 1–100번 안의 다른 문제에서도 다시 나옵니다. 그때는 항이 고정 폭 정수에 들어가지 않을 만큼 커지기도 하므로, 이번의 정수 범위 분석을 기억해 두면 도움이 됩니다.
출처와 라이선스
- Project Euler, Problem 2 — 원래 문제. 이 글의 “문제” 절은 그 내용을 직접 요약한 것이고, 원문과 같은 CC BY-NC-SA 4.0으로 공유합니다. 문제의 저작자 표시는 Project Euler입니다.
- Project Euler, Copyright — 문제 본문의 라이선스와 링크 방식. 비영리 조건에 따라 이 글에는 광고를 싣지 않습니다.
- 풀이, 증명, 코드는 직접 쓴 것입니다. Project Euler의 해설(overview), 포럼, 회원 전용 자료나 다른 풀이 사이트는 참고하지 않았습니다. Motitory는 Project Euler와 제휴나 후원 관계가 없고, Project Euler가 이 글을 검토하지도 않았습니다.
- C++17 최종 작업 초안 N4659 — §6.9.1 기본 타입(부호 없는 정수의 2^N 법 연산), §21.3.6
<climits>(C 표준의 범위를 따름), §22.3assert(NDEBUG) - Python 표준 라이브러리: Numeric Types —
int의 무제한 정밀도 - Python 레퍼런스: The assert statement — 최적화 모드에서
assert가 제거됨