[Project Euler] 57. Square root convergents

1. 개요

    문제는 이곳에서 확인할 수 있다. $\sqrt{2}$는 다음과 같이 표현할 수 있다.

$$\sqrt{2}=1+1/(2+1/(2+1/(2+\cdots )))=1.414213\cdots$$

    4번째까지의 항을 살펴보면 다음과 같다.

    $1+1/2=3/2$

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

    $1+1/(2+1/(2+1/2))=17/12$

    $1+1/(2+1/(2+1/(2+1/2)))=41/29$

    8번째 항은 $1393/985$이며, 이때 처음으로 분자의 자리수가 분모의 자리수보다 크게 된다. 1,000번째 항 내에서 분자의 자리수가 분모의 자리수보다 큰 항의 수를 구하는 것이 문제의 목표이다.

2. 구현

    각 항에서 1을 제외하고 나열해보자.

$$\frac{1}{2},\frac{1}{2+\frac{1}{2}},\frac{1}{2+\frac{1}{2+\frac{1}{2}}},\cdots$$

    위의 식에서 다음과 같은 점화식을 유도할 수 있다.

$$a_n=\frac{1}{2+a_{n-1}}wheren\ge 2,a_1=\frac{1}{2}$$

    또한 $a$, $b$가 서로소이면 $a$, $2a+b$와 $a$, $a+b$도 서로소이다. 따라서 위의 점화식으로 유도하는 분수는 기약분수이며 약분없이 자리수를 세면 된다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

# -*- coding: utf-8 -*- # Project Euler 57   import math as m   num, denom = 1, 2 result = 0   for i in range(1000):       num, denom = denom, 2*denom + num     digit = list(map(lambda x: int(m.log10(x)), [num + denom, denom]))       if digit[0] - digit[1] > 0:         result += 1   print(result)

    답은 153이다.