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 までの数値から二つの過剰数の和を取り除いて、和を取るだけ。sequence と difference を使えば、簡単(笑)
> (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 以上の数値が二つの過剰数の和になるようです。
以上、如何でしょうか?