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

p21.py

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

#!/usr/bin/python

# -*- coding: utf-8 -*-

defsum_proper_factors(n):

(result, sqrt) = (1, n ** 0.5)

(start, step) = n % 2 == 1and (3, 2) or (2, 1)

for i in range(start, int(sqrt) + 1, step):

if n % i == 0:

result += i + n / i

if sqrt == int(sqrt):

result -= sqrt

return result

defmain():

result = 0

for i in range(1, 10000):

sum1 = sum_proper_factors(i)

if sum1 > i:

if i == sum_proper_factors(sum1):

result += i + sum1

print result

if __name__ == '__main__':

import time

startTime = time.time()

main()

print time.time() - startTime

p21.go

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

package main

import (

"fmt"

"math"

"time"

)

funcsum_proper_factors(n int)int {

sum, sqrt := 1, math.Sqrt(float64(n))

start, step := 2, 1

if n%2 == 1 {

start, step = 3, 2

}

for i := start; i <= int(sqrt); i += step {

if n%i == 0 {

sum += i + n/i

}

}

if sqrt == float64(int(sqrt)) {

sum -= int(sqrt)

}

return sum

}

funcmain() {

result, startTime := 0, time.Now()

for i := 1; i < 10000; i++ {

iSum := sum_proper_factors(i)

if iSum > i {

if i == sum_proper_factors(iSum) {

result += i + iSum

}

}

}

fmt.Println(result, time.Now().Sub(startTime))

}

I’m the 70186th person to have solved this problem.