본문바로가기
[오일러 프로젝트] 꼬리에 꼬리를 무는 수 이야기: 무리수 √2 그리고 연분수
수학동아 2021.09.24 14:05 조회 152

 

코.알.못 홍 기자의 코딩 도전기

코딩(프로그래밍)의 ‘코’자도 모르는 코.알.못. 홍 기자가 수학 문제를 코딩으로 푸는 오일러 프로젝트 문제를 하나하나 해결해 나갑니다. 오일러 프로젝트는 수학과 코딩 실력을 모두 키울 수 있도록 2001년에 만든 수학 문제 웹사이트입니다. 홍 기자와 함께한다면 수학과 코딩 언어의 하나인 파이썬 모두 정복할 수 있지 않을까요?

 

 

1.414213562…. 계산기에 2를 넣고 제곱근(√)표시를 누르면,

√2의 값이 꼬리에 꼬리를 무는 수로 나타납니다. 이 숫자에는 규칙도, 끝도 없죠.

하지만 ‘이것’을 사용하면 값을 단 한 줄의 규칙으로 나타낼 수 있습니다.

그 정체는 바로 연. 분. 수. 입니다. (두둥)

 

 

<오일러 프로젝트 57번>

1+1/2부터 시작해 1/2의 분모에 1/2을 계속해 더해가면 √2의 값에 점점 가까워집니다.

 

1+1/2 = 3/2 = 1.5

1+1/(2+1/2) = 7/5 = 1.4

1+1/[2+1/(2+1/2)] = 17/12 = 1.41666...

 

단계를 반복할 때마다 만들어지는 분수를 보면, 3/2부터 시작해 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985로 이어집니다. 이 중 8번째 분수인 1393/985은 처음으로 분자의 자릿수가 분모의 자릿수를 넘어섭니다. 그렇다면 1천 번째 단계까지 연분수를 만들어갈 때, 분자의 자릿수가 분모보다 많아지는 경우는 몇 번일까요?

 

 

연분수는 말 그대로 '연속적인 분수'를 의미합니다. 오일러 프로젝트 57번 문제에서 √2에 가까워지는 연분수들의 형태를 정리하면 k+1번째 나올 연분수는 k번째 단계의 연분수를 이용해 아래의 식으로 나타낼 수 있고, 이를 √2에 가까워지는 연분수 사이의 관계를 나타낸 '점화식'이라고 합니다.

 

 

이처럼 √2를 소수로 나타내면 1.414213562...로 이어져 소수점 아래 자릿수에는 규칙이 없지만, 연분수로 나타내면 위의 점화식 형태의 규칙을 발견할 수 있습니다. 이를 이용해 연분수의 규칙을 코드로 나타내고 57번 문제를 해결해보겠습니다.

 

 

파이썬 완전정복! ‘무한하지만 규칙적인 연분수 만들기’

57번 문제를 해결하는 데 필요한 파이썬 명령어입니다.

꿀팁 중의 꿀팁, 밑줄 쫙! 핵심만 소개하니 꼭 익혀두세요!

 

1. 연분수 사이의 관계 나타내는 점화식 정리하기

앞서 찾은 점화식을 이용해 문제를 푸는 코드를 만들기 전에, 먼저 점화식을 정리해야 합니다. k번째 단계의 연분수에서 분자는 pk, 분모는 qk라고 하면, 연분수 ak는 pk/qk로 나타낼 수 있습니다. 그럼 k+1번째 단계의 연분수 ak+1은 점화식을 따라 1+1/(1+ak)이므로, 1+1/(1+pk/qk)입니다. 이 분수의 분모를 정리하면 아래와 같습니다.

 

 

ak+1은 위의 설명처럼 pk+1/qk+1로 나타낼 수 있으므로 이를 이용하면 다음의 등식이 성립합니다.

 

 

2. 분자와 분모의 자릿수 구하기

57번 문제에서는 2를 나타내기 위한 연속된 단계의 연분수 중에서 분자의 자릿수가 분모의 자릿수보다 큰 경우의 수를 찾아야 합니다. 따라서 위의 점화식으로 구한 분자와 분모의 자릿수를 알아내야 하죠. 이때 크게 두 가지 방법을 사용할 수 있는데, 첫 번째는 로그함수를 사용하는 방법입니다. 로그함수(log10)는 어떤 수를 10의 거듭제곱 꼴로 나타내 그 지수를 구하는 함수입니다. 예를 들어 10은 101로 표현되며, 지수는 1입니다. 100은 102로 표현되므로 지수는 2이죠. 이때 자릿수는 지수 값의 자연수 부분에 1을 더한 것과 같습니다. 이를 이용한 자릿수를 구하는 코드는 아래와 같습니다.

 

 

위의 방법 외에 분자, 분모의 숫자를 문자열로 바꾼 뒤 문자열의 길이를 구하는 방법도 있습니다. 숫자를 문자열로 바꾸는 명령어 str()와 문자열의 문자 개수, 즉 문자열의 길이를 구하는 명령어 len()을 사용해 코드로 나타냅니다.

 

 

 

도전! 오일러 프로젝트 57번 문제 뽀개기

* 코딩 언어는 Python으로 두고 실행하세요!

 

 

#1 분자와 분모의 자릿수를 셀 때 사용할 로그함수가 담겨있는 math 모듈을 불러옵니다.

#2, 3 로그함수 또는 문자열 변환을 이용해 분자와 분모의 자릿수를 세는 함수를 정의합니다.

#4 첫 번째부터 1천 번째 단계의 연분수를 구해 57번 문제의 답을 구할 함수를 정의합니다.

#5 √2를 나타내기 위한 첫 번째 단계의 연분수인 1+1/2 = 3/2의 분자, 분모 값을 p, q의 초깃값으로 둡니다.

#6 분자의 길이가 분모의 길이보다 긴 분수의 개수를 변수 cnt로 두고, 초깃값을 0으로 둡니다.

#7, 8, 9, 10 분자(p)와 분모(q)의 자릿수를 비교해 분자가 더 긴 경우, cnt에 1을 더합니다. 그리고 앞서 구한 점화식을 이용해 다음에 나오는 분자, 분모를 구한 뒤 자릿수를 계속 비교합니다. 여기서 ➐의 for문에 변수 _를 사용한 이유는 이미 반복할 횟수가 정해져 있고, 몇 번째 시행인지 변수 i로 나타내더라도, 아래의 코드에서 사용되지 않기 때문입니다. 반복 작업이 끝나면 cnt를 반환합니다.

#11 e057() 함수를 실행해 57번 문제의 답을 구합니다.

 

 

BONUS 오일러 퀴즈

오일러 프로젝트 57번 문제를 풀어보고, 다음 예제 문제에도 도전해보세요!

 

① 그렇다면 √2를 나타내기 위한 첫 번째 단계부터 2천 번째 단계까지의 연분수 중에서 분자가 분모의 자릿수보다 긴 경우는 몇 번일까요?

 

② √7 역시 연분수의 꼴로 나타낼 수 있고, 분모를 이루는 정수 부분이 1, 1, 1, 4로 반복됩니다. 이를 이용해 분자와 분모의 자릿수를 비교하는 코드를 만들어보세요.

 

 

증명, 계산 없이 영감으로만 무리수들을 연분수로 나타냈던 라마누잔은 지금도 ‘천재적인 인도의 마술사’라고 불립니다. 그리고 이스라엘공과대학교 연구팀이 개발해 그의 이름을 붙인 ‘라마누잔 머신’이 라마누잔이 죽은 뒤에도 작업을 계속하고 있죠. 최근에는 π(원주율), e(자연 상수), 카탈랑 수 등 수학적, 과학적으로 의미 있는 무리수를 연분수로 나타내는데 성공하기도 했답니다.

 

첫 댓글의 주인공이 되어 보세요!
  • 폴리매스 문제는 과학기술진흥기금 및 복권기금의 재원으로 운영되고, 과학기술정보통신부와 한국과학창의재단의 지원을 받아 수행된 성과물로 우리나라의 과학기술 발전과 사회적 가치 증진에 기여하고 있습니다.

  • ☎문의 02-6749-3911