Amicable and perfect numbers

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.

2 thoughts on “Amicable and perfect numbers

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s