問題
-
Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.
-
2つの過剰数の和で書き表せない正の整数の総和を求めよ.
解答
Problem 21を解くときに使ったdivisors
を流用してブルートフォース。small-sigma
は約数関数です。
(use srfi-1)
(define (divisors n)
(define (divisor? m) (zero? (reremainder n m)))
(let loop ((i 1) (early '()) (later '()))
(if (> (* i i) n) (append-reverse early later)
(cond
((= (* i i) n) (loop (+ i 1) (cons i early) later))
((divisor? i) (loop (+ i 1) (cons i early) (cons (/ n i) later)))
(else (loop (+ i 1) early later))))))
;;; divisor function
(define (small-sigma x n) (apply + (map (cut expt <> x) (divisors n))))
(define small-sigma1 (cut small-sigma 1 <>))
(define (abundant-number? n) (< (* 2 n) (small-sigma1 n)))
(define (get-sieve upper-limit)
(define lookup-table (make-vector (+ upper-limit 1) #f))
(define (sum-of-abundants? n) (ref lookup-table n))
(define abundant-numbers (filter abundant-number? (iota upper-limit 1)))
(unless (null? abundant-numbers)
(let init-lookup-table ((i (car abundant-numbers))
(rest (cdr abundant-numbers)))
(let inner-loop ((j i) (rest-of-rest rest))
(define sum (+ i j))
(if (> sum upper-limit)
(unless (null? rest)
(init-lookup-table (car rest) (cdr rest)))
(begin
(set! (ref lookup-table sum) #t)
(unless (null? rest-of-rest)
(inner-loop (car rest-of-rest)
(cdr rest-of-rest))))))))
sum-of-abundants?)
(define (solve)
(apply + (remove (get-sieve 28123) (iota 28123 1))))
(define (main argv)
(display (solve))
(newline))
コメント
コメントを投稿