Project Euler 64

2016-05-21 07:07:29

ひさしぶりに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))))