ひさしぶりにProject Eulerを解いてみた。 連分数を計算させる問題。ポイントは再帰的に計算すること。
例で、整数部分 + 小数部分と分けている部分を見比べて、 ローカル関数fnを作った。
関数squarepは平方数かどうか確かめる述語。 関数continued-fractionは、平方数以外の自然数だけ。 また、この関数は、連分数部分ではない、整数部分がリストの最後にあるため、 解答を求めるときに、oddp ではなく、evenp を使う必要があった。
(defun continued-fraction (p)
(unless (> p 0)
(error "p must be positive"))
(when (squarep p)
(error "p must be non-square integer"))
(flet ((fn (a b c)
(declare (ignore b))
(let*
((newa (/ (- p (* c c)) a))
(newb (floor (- (sqrt p) c) newa))
(newc (+ (* newa newb) c)))
(list newa newb (- newc)))))
(mapcar #'second
(let ((k (floor (sqrt p))))
(do ((param (list 1 k (- k)) (apply #'fn param))
(res nil (cons param res)))
((some (lambda (x) (equal x param)) res) res))))))
(defun squarep (x)
(let ((n (floor (sqrt x))))
(= x (* n n))))
(defun euler-064 ()
(count-if #'evenp
(mapcar #'(lambda (x) (length (continued-fraction x)))
(loop for x from 2 upto 10000 unless (squarep x) collect x))))