I’m reading Simon Singh’s wonderful book: Fermat’s Last Theorem. In it he writes about perfect numbers and amicable numbers. Perfect numbers have the property that the integer divisors sum to the number. An example is the number 6. The divisors are 1, 2 and 3. The sum of the divisors is 6.

Amicable numbers occur in pairs where the sum of the divisors of one number equals a second number and the sum of the divisors of that number equals the first number. An example pair is 220 and 284. The factors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, and 110, which sum to 284. The factors of 284 are 1, 2, 4, 71 and 142 which sum to 220. Singh suggests that the pair (220 – 284) is symbolic of friendship. There is a nice discussion in Wikipedia and mathworld.

Up until 1636 only 1 pair of amicable numbers was known (220 – 284), then Fermat discovered (17,296 – 18,416). Leonard Euler (~1747) listed 62 amicable pairs and now over 1 billion have been found. The full list is here.

Writing a program to efficiently factor large numbers is tricky (see the discussion here) but we can tackle smallish numbers with a few lines of R code.

Function to calculate all factors (source):

MyFactors <- function(x) { x <- as.integer(x) div <- seq_len(abs(x / 2)) div[x %% div == 0L] }

Let’s try it

MyFactors(220) #[1] 1 2 4 5 10 11 20 22 44 55 110 sum(MyFactors(220)) #[1] 284 sum(MyFactors(284)) #[1] 220

Here is my rather clunky algorithm to find perfect and amicable numbers between 1 and 10,000.

x1 <- sapply(1:10000, MyFactors) # factors of numbers up to 10000 x2 <- sapply(x1, sum) # sum of factors x2[1] <- 1 # 1 isn't handled appropriately so we need to fix it x3 <- x2[x2[x2] == 1:length(x2)] # find perfect and amicable numbers x3 <- x3[!is.na(x3)] # remove missing x4 <- data.frame(number = x3, FactorSum = sapply(x3, function(x) sum(MyFactors(x)))) # store in a data frame x4 <- x4[order(x4$number), ] # sort x4 <- x4[-1, ] # remove the mishandled first row x4$type <- ifelse(x4$number == x4$FactorSum, 'Perfect', 'Amicable') # label x4 # print

And the answer is:

Number | Sum of factors | Type |
---|---|---|

6 | 6 | Perfect |

28 | 28 | Perfect |

220 | 284 | Amicable |

284 | 220 | Amicable |

496 | 496 | Perfect |

1184 | 1210 | Amicable |

1210 | 1184 | Amicable |

2620 | 2924 | Amicable |

2924 | 2620 | Amicable |

5020 | 5564 | Amicable |

5564 | 5020 | Amicable |

6232 | 6368 | Amicable |

6368 | 6232 | Amicable |

8128 | 8128 | Perfect |

Simon Singh’s ‘The Code Book’ is also a great read.

Carl PomeranceCongratulations on the discovery of so many amicable pairs. To what level are you certain you have found all of them?

tonyladsonPost authorGood question! From my reading, the pair 1184-1201 was missed by a lot of very smart people and only found in 1860. It’s much easier now others have done the hard work e.g. Amicable numbers https://oeis.org/A063990 and perfect numbers https://oeis.org/A000396