Project Euler 65

2016-05-21 07:07:53

自然対数の底 e を連分数展開すると、2の倍数が登場するという性質があって、 eの100番目の連分数近似の分子の数の各桁の和を求める問題。

e-continued-fraction で n番目までの連分数表示をリストで返す。

(defun e-continued-fraction (n)
  (mapcar #'(lambda (x)
              (cond ((= x 1) 2)
                    ((= (mod x 3) 0) (* 2 (/ x 3)))
                    (t 1)))
          (loop for x from 1 to n collect x)))

(defun nth-convergent (lst)
  (if (null (cdr lst))
      (car lst)
      (+ (car lst) (/ 1 (nth-convergent (cdr lst))))))

(defun euler-065 ()
  (apply #'+
         (mapcar  #'(lambda (c)
                      (- (char-int c)
                         (char-int #\0)))
                  (coerce
                   (format nil "~a"
                           (numerator (nth-convergent (e-continued-fraction 100))))
                   'list))))

解答フォーラム眺めてると、

i took the whole (1,2,1),(1,4,1),… as ones. when coming from the down, let the result after solving n blocks is pn/qn, pn=2nqn-1+2npn-1+qn-1, qn=2nqn-1+2npn-1+2qn-1+pn-1, here q1=2(33)+1=67 and p1=2(33)+2=68

とするやり方が賢そう。

あとiterateをつかって、連分数列作ってる 解答もあった。

(defun generate-fraction (n)
  (cons
   2 (cdr
      (iter (for i from 1 to n)
            (generating k from 1)
            (with count = 1)
            (cond ((= count 2)
                   (collect (* 2 (next k)))
                   (setq count 1))
                  (t (collect 1)
                     (collect 1)
                     (incf count)))))))