Archive for 2015年7月|Monthly archive page

projecteuler23

 正の自然数の約数の総和が、その自然数の2倍より大きい時、その数を過剰数(abundant number) と呼ぶそうです。さらに、数理解析(mathematical analysis) によると、28123より多きい数は二つの過剰数の和で表されるとか。
 そして、projecteuler問題23 は、二つの過剰数の和で表されない数の和を求める問題。
 つまり、二つの過剰数の和で表される 28123 以下の数値がわかれば答えが求まります。
 さて、まず二つの過剰数を求めます。最小の過剰数が 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)))))
(setq max-num 28124 abundants '())
(for (i 2 (- max-num 12))
  (let (lst (divisors2 i))
    (if (> (apply + (0 -1 lst)) (lst -1)) (push i abundants -1))))

 これで、計算に必要な過剰数が abundants に入ります。
 中身はこんな感じ、

> (0 10 abundants)
(12 18 20 24 30 36 40 42 48 54)
> (-10 10 abundants)
(28074 28080 28084 28086 28092 28098 28100 28104 28110 28112)
> (length abundants)
6962
> 

 つぎに、二つの過剰数の和を求めます。

(setq lst '())
(for (i 0 (-- (length abundants)))
  (if (> max-num (* 2 (abundants i)))
  (push (map (curry + (abundants i)) (i abundants)) lst -1)))
(setq two-abundants (filter (fn(x) (< x max-num)) (unique (flat lst))))

 さて、二つの過剰数の和の最大値と最小値は

> (apply max two-abundants)
28123
> (apply min two-abundants)
24
> 

 予定通りです。
 あとは、1 ~ 28123 までの数値から二つの過剰数の和を取り除いて、和を取るだけ。sequencedifference を使えば、簡単(笑)

> (apply + (difference (sequence 1 (-- max-num)) two-abundants))
4179871
> 

 これで答えが出ました。
 ちなみに、

> (sort (difference (sequence 1 (-- max-num)) two-abundants))
(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 25 26 27 28 29 31 33 
 :
 13621 13829 13879 14143 14251 14297 15371 15557 16187 17261 17891 18437 19067 20161)
> 

 ということから、20162 以上の数値が二つの過剰数の和になるようです。
 以上、如何でしょうか?

広告