problem 33 - mtsuyuguの日記

49/98 は 1/2 ですが、49/98 の 9 を消しても 4/8 = 1/2 になるという面白い性質を持っています。

問題 33 は二桁の分母分子からなる 1 未満の分数で先の例のような分数をすべてかけたときの分母の値はいくつか？というものです。 30/40 の 0 を消して 3/4 のような trivial なものは除外します。

gauche は正数の除算を既約分数の形で表してくれるため、約分の処理を書かなくて済みました。

(use srfi-1)
(use util.combinations)

(define (pseudo-cancel n d) ; (12 23) -> (/ 1 3)
  (define (num->digits n) ; 12 -> (1 2)
    (map (cut <> n 10) (list quotient modulo)))
  (define (same-digits? n1 n2) ; (same-digits? 12 23) -> 2
    (let* ((d1 (num->digits n1))
           (d2 (num->digits n2)))
      (any (lambda (x) (if (apply = x) (car x) #f))
           (cartesian-product (list d1 d2)))))
  (define (del-digits n d) ; (del-digits 23 2) -> 3
    (let ((q (quotient n 10))
          (m (modulo n 10)))
      (cond ((= q d) m)
            ((= m d) q)
            (else 0))))
  (let ((found (same-digits? n d)))
        (if found
          (/ (del-digits n found) (del-digits d found))
          0)))


(define (p33)
  (define (gen-rational)
    (fold (lambda (d p)
            (append p (map (lambda (n) (list n d))
                           (iota (- d 9) 10))))
          '() (iota 90 10)))
  (denominator
    (apply *
           (filter-map (lambda (num)
                         (let* ((n (car num))
                                (d (cadr num))
                                (p (pseudo-cancel n d)))
                           (cond ((= n d) #f) ; trivial (ex. 12/12 = 1)
                                 ((every (lambda (x) (= 0 (modulo x 10))) num) #f) ; trivial (ex. 10/20 = 1/2)
                                 ((= p (apply / num)) p)
                                 (else #f))))
                (gen-rational)))))