自然対数の底 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)))))))