파이썬으로 피보나치 수열에서 숫자의 n번째 배수 위치 찾기

이 글에서는 다음 문제에 대한 해결 방법을 살펴봅니다.

문제 정의

숫자 k와 정수 n이 주어졌을 때, 피보나치 수열에서 k의 n번째 배수가 등장하는 위치(항 번호)를 구하는 것이 목표입니다.
예를 들어 k=4, n=5라면, 피보나치 수열에서 4의 배수에 해당하는 항들 가운데 다섯 번째 값이 몇 번째 항에 위치하는지 찾아야 합니다.

접근 방법

피보나치 수열의 중요한 성질 중 하나는 "F_m이 F_n을 나누려면 m이 n의 약수여야 한다"는 점입니다. 이 성질을 활용하면 문제를 다음과 같이 단순화할 수 있습니다.

먼저 반복문으로 피보나치 수를 하나씩 생성하면서 처음으로 k로 나누어떨어지는 항의 위치 i를 찾습니다. 그다음, 위 성질에 따라 k의 배수는 정확히 i의 배수 위치마다 등장하므로, n번째 배수의 위치는 n × i가 됩니다.

구현 코드

# k의 n번째 배수 위치를 찾는 함수
def find(k, n):
    f1 = 0
    f2 = 1
    i = 2
    # 피보나치 수열을 생성하며 조건 검사
    while True:
        f3 = f1 + f2
        f1 = f2
        f2 = f3
        if f2 % k == 0:
            return n * i
        i += 1

# 찾고자 하는 배수의 순번
n = 5
# 기준이 되는 숫자
k = 4

print("피보나치 수열에서 k의 n번째 배수의 위치:", find(k, n))

실행 결과

피보나치 수열에서 k의 n번째 배수의 위치: 30

코드 설명

함수 find()와 변수 n, k는 모두 전역 범위(global scope)에서 선언되어 사용됩니다. 함수 내부에서는 f1, f2 두 변수로 피보나치 수열을 순차적으로 생성하며, 각 항이 k로 나누어떨어지는지 검사합니다. k=4일 때 처음으로 4의 배수가 되는 항은 여섯 번째 항(F₆=8)이고, 따라서 다섯 번째 배수의 위치는 5 × 6 = 30이 됩니다.

결론

이 글에서는 피보나치 수열의 배수 관련 성질을 활용하여, 숫자 k의 n번째 배수가 수열에서 등장하는 위치를 효율적으로 구하는 파이썬 프로그램을 살펴보았습니다.