Project Euler Problem 26

問題26: 1000未満のdにおいて 1/d を小数にした時、循環部の長さがもっとも長くなる d を求めよ。[=>問題文]

問題26の解答

　気がつけば do ばっかり使ってる自分がいる。

;; Emacs Lisp
(defun problem026 (limit)
  (let ((recurring-length  ; 1/d の循環部の長さを求める関数
         (lambda (d)
           (do ((table (make-hash-table))
                (r 1) (count 0 (1+ count))
                (result))
               ((not (null result)) result)
             (cond ((zerop r)
                    (setq result 0))
                   ((gethash r table)
                    (setq result (- count (gethash r table))))
                   (t (puthash r count table)
                      (setq r (mod (* r 10) d))))))))
    ;; メインループ
    (do ((max-length 0)
         (result)
         (i (1- limit) (1- i)))
        ((<= i max-length) result)
      (let ((len (funcall recurring-length i)))
        (when (> len max-length)
          (setq max-length len)
          (setq result i))))))

(problem026 1000)

　考え方のベースは割り算の筆算です。ここで重要なのは「商」として並ぶ数字列ではなく「余り」の部分。無限小数になるということはいつまでも割り切れない･･･つまり「余り」が０にならないことが条件になります。
　筆算をしていった時、以前に出現した「余り」が再び現れると、それ以降は以前と同じ計算が繰り返されることになり、結果として循環した小数になります。同じ「余り」が出現するまでのループ回数を数えれば、それが循環部の長さになります。
　recurring-length では、hash table に、「キー:余り、値:ループカウンタ」を保存してゆき、計算した「余り」がすでに登録されていた場合、保存されているカウンタ値と、現在のカウンタ値の差をとることで、求める循環部の長を得ています。
　割り算の「余り」はその性質上「割る数」より小さい値にしかなりえません。したがって循環するための「余り」のバリエーションは「割る数」以上にはならないため、循環小数の循環部も「割る数」より長くはなりません。だから 1/d の d は大きい方からチェックを行い、既に計算済みの中での最大長(max-length)より d が小さくなったらそれ以下の d は調べる必要がありません。