Project Euler - Problem 23

問題

• 原文

  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))