Amicable numbers

2014-09-15

Problem 021: Amicable numbers

Description:

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.

Solution:

v
# ... #
. . . .
.  .  .
. . . .
# ... #
                                 >v       >#        v#   <
>"d"4*:10p55**00p00g>1-::20p0\2/:|>:20g\%#^_:30p+30g>1-:#^_$v
                    |:                     p+1/g01g02%g01g02<
v$$             p100<            >1                         ^
>00g1-20p090p>20g10g%20g10g/1+g40p40g10g%40g10g/1+g50p 20g50g-#v_20g40g`!#v_20g." - ",,,40g.55+,v
             |p02-1:g02                                        <          <       p09++g04g02g09<
        @.g09<

Download

This program is too big to display/execute here, click [download] to get the full program.

Explanation:

Most of the time is here spent in the NumberOfDivisors function. So we first cache every possible result of this function (from 0 to 10000). The rest is simple searching for numbers where a == D(D(a)) and a != D(a).

Interpreter steps:	601 124 986
Execution time (BefunExec):	1min 42s (5.87 MHz)
Program size:	400 x 33
Solution:	31626
Solved at:	2014-09-15