Project Euler Problem 21

Problem 21

05 July 2002

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

Answer: 31626

 

 

C#

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace Euler {
    class Program {
        static void Main(string[] args) {
            Func<int, int> dsum = (n => Enumerable.Range(1, n / 2).Where(x => n % x == 0).Sum());
            Func<int, bool> amicable = (n => {
                int d = dsum(n);
                return d != n && dsum(d) == n;
            });

            Console.WriteLine(Enumerable.Range(1,9999).Where(amicable).Sum());
            Console.ReadKey();
        }
    }
}

Racket

; slow
(define (dsum n)
  (sequence-fold + 0 (sequence-filter (lambda (x) (= 0 (modulo n x)))(in-range 1 (+ 1 (/ n 2))))))
(define (amicable n) 
  (let ([d (dsum n)])
    (and (not (= d n))
         (= (dsum d) n))))
(time (displayln (sequence-fold + 0 (sequence-filter amicable (in-range 1 10000)))))

; fast
(define (dsum n)
  (for/sum ([x (in-range 1 (+ 1 (quotient n 2)))]
            #:when (= 0 (modulo n x)))
    x))

(define (amicable n)
  (let ([d (dsum n)])
    (and (not (= d n))
         (= (dsum d) n))))
(time 
 (begin
   (displayln
    (for/sum ([x (in-range 1 10000)]
              #:when (amicable x))
      x))))
(time (displayln (sequence-fold + 0 (sequence-filter amicable (in-range 1 10000)))))

Javascript

function dsum(n) {
  var sum=0; for(var x=n/2;x>=1;x--) if(n%x==0) sum+=x;
  return sum;
}

function amicable(n) {
  var d = dsum(n);
  return d != n && dsum(d) == n;
}

var sum=0; for(var x=1;x<=9999;x++) if(amicable(x)) sum+=x;
alert(sum);