Archive for 2015年4月|Monthly archive page

projecteuler21

 projecteuler問題21 は、10000 未満の友愛数の和を求める問題。
 この問題を解いていると聞いたこともない種類の数の名前が出てきます。友愛数もその一つ。
 友愛数は親和数とも呼ばれ、約数から自身を除いた和が相手の数値になり、その相手の数値の約数の和が自分と同じになる組だそうです。
 つまり、突き詰めれば全ての約数を求める問題。約数を求めるのは 問題12でやっているので、コード自体は、

(define-macro (memoize mem-func func) 
  (set (sym mem-func mem-func) 
    (letex (f func  c mem-func) 
      (lambda () 
        (or (context c (string (args))) 
            (context c (string (args)) (apply f (args))))))))
(define (make-sublist lst)
  (clean nil? (map (fn(x) (if x $idx)) lst))
)
(memoize combination2 (lambda (n)
  (if (= n 0) '()
    (let (res (combination2 (-- n)))
      (push (list n) res -1)
      (dolist (x res (= (x 0) n))
         (push (append x (list n)) res -1))
      res))))
(define (divisors2 num , (res '(1)))
  (let (numbers (factor num))
    (if (= num 1) 1
        numbers
      (let (sublist (combination2 (length numbers)))
        (dolist (x sublist)
          (push (apply * (select numbers x)) res -1))
        (unique res)))))
(let (res)
  (for (a 2 9999)
    (let (b (apply + (chop (divisors2 a))))
      (if (and (> b 1) (!= a b) (= a (apply + (chop (divisors2 b)))))
        (push a res -1))))
  (println res)
  (apply + res))

 こんな感じ。これを実行すれば、

(220 284 1184 1210 2620 2924 5020 5564 6232 6368)
31626

 10000 未満の友愛数とその和 31626 が出てきます。

 以上、如何でしょうか?

広告