프로젝트 오일러 65

의 100번째 연분수 확장 값의 분자 자릿수를 모두 더하면?

문제 자세히 보기: [국어] [영어]

의 연분수를 꼴을 이라 했을 때, 100번째 연분수 확장 값을 계산하려면 (100번째 항)부터 값을 계산해 올라가야 한다. 문제에서 의 연분수 꼴이 로 나타낼 수 있다고 되어 있으므로 이 주어졌을 때 을 구하는 함수는 다음과 같이 만들 수 있다.

(defn- xs
  "a(n-1) a(n-2) ... a0"
  [n]
  (->> (iterate inc 1)
       (mapcat #(vector 1 (* 2 %) 1))
       (take (dec n))
       (cons 2)
       reverse))

다음과 같이 가 주어졌을 때 를 구하는 함수를 정의하면 이 함수를 xs에 f를 적용해 reduce 해 연분수 값을 구할 수 있다.

(defn- f [a b]
  (+ b (/ 1 a)))

이제 의 처음 100개 항을 구해 f를 적용해 reduce한 다음 분모를 구해 각 자릿수를 모두 더하면 문제의 답을 구할 수 있다.

(defn solve []
  (->> (xs 100)
       (reduce f)
       numerator
       digits
       (apply +)))

실행 결과는 다음과 같다.

p065=> (time (solve))
"Elapsed time: 2.597584 msecs"
2?2

참고

• 프로젝트 오일러 65 풀이 소스 코드