Project Euler

[ホーム](https://redmine.noppi.jp) - [[Wiki|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未満の友愛数の和を求めよ.

```scheme

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

```