problem 26 - mtsuyuguの日記

循環小数 1/d (1<d<1000) の循環部の桁数がいちばん多い d を求める問題。

(use srfi-1)

; 循環小数を求める
(define (find-repeating num)
  (let loop ((n 1)
             (result '()))
    (let* ((m (modulo n num))
           (q (quotient n num))
           (found (assq m result)))
      (cond ((= m 0) '())
            (found (set-cdr! (cdr found) (+ (cddr found) 1))
                   (reverse (acons m (cons q 1) result)))
            (else (loop (* m 10) (acons m (cons q 1) result)))))))

; 循環の個数を調べる
(define (count-repeating l)
  (let loop ((l l))
    (cond ((null? l) 0)
          ((= (cddr (car l)) 2) (length (cdr l)))
          (else (loop (cdr l))))))

(define (p26)
  (caar (sort (map (lambda (x) (cons x (count (find-repeating x))))
                   (iota 999 1))
              (lambda (x y)
                (> (cdr x) (cdr y))))))

(print (p26))