ホーム - Project Euler

Problem 21¶

Amicable Numbers¶

Let $d(n)$ be defined as the sum of proper divisors of $n$ (numbers less than $n$ which divide evenly into $n$).
If $d(a) = b$ and $d(b) = a$, where $a \ne b$, then $a$ and $b$ are an amicable pair and each of $a$ and $b$ are called amicable numbers.
For example, the proper divisors of $220$ are $1, 2, 4, 5, 10, 11, 20, 22, 44, 55$ and $110$; therefore $d(220) = 284$. The proper divisors of $284$ are $1, 2, 4, 71$ and $142$; so $d(284) = 220$.
Evaluate the sum of all the amicable numbers under $10000$.

友愛数¶

d(n) を n の真の約数の和と定義する. (真の約数とは n 以外の約数のことである. )
もし, d(a) = b かつ d(b) = a (a ≠ b のとき) を満たすとき, a と b は友愛数(親和数)であるという.

例えば, 220 の約数は 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 なので d(220) = 284 である.
また, 284 の約数は 1, 2, 4, 71, 142 なので d(284) = 220 である.

それでは10000未満の友愛数の和を求めよ.

(import (scheme base)
        (gauche base)
        (math prime)
        (scheme list)
        (scheme vector))

(define (non-primes num)
  (let ([primes-num (take-while (^n (<= n num)) (primes))]
        [iota-4-num (iota (+ num 1 -4) 4)])
    (lset-difference = iota-4-num primes-num)))

(define (proper-divisors num)
  (let loop ([n 2] [result '()])
    (cond
      [(< num (* n n)) (delete-duplicates (cons 1 result))]
      [(zero? (mod num n))
       (loop (+ n 1) (cons* n (div num n) result))]
      [else (loop (+ n 1) result)])))

(define (sum-divisors lis)
  (map
    (^n (cons n
              (apply + (proper-divisors n))))
    lis))

(define (amicable-numbers num)
  (let ([divisors-list (sum-divisors (non-primes num))]
        [table (make-vector (+ num 1) #f)])
    (for-each
      (^[cell]
        (let ([a (car cell)]
              [b (cdr cell)])
          (when (and (not (= a b)) (<= b num))
            (set! (vector-ref table a) b))))
      divisors-list)
    (vector-fold
      (^[lis index num-or-f]
        (cond
          [(not num-or-f) lis]
          [(not (vector-ref table num-or-f)) lis]
          [(= index (vector-ref table num-or-f))
           (set! (vector-ref table index) #f)
           (set! (vector-ref table num-or-f) #f)
           (cons* index num-or-f lis)]
          [else lis]))
      '()
      (list->vector (iota (+ num 1)))
      table)))

(define answer-21
  (apply + (amicable-numbers 9999)))

(format #t "21: ~d~%" answer-21)