Project Euler 21: Amicable Numbers
Peter Prevos |
439 words | 3 minutes
Share this content
Project Euler 21 takes us to the realm of amicable numbers. Sequence A259180 in the OEIS lists all amicable, or friendly numbers. These are the most romantic numbers in all of maths. Amicable numbers
Recreational mathematicians love to find numbers with special properties. Other such special numbers are 'perfect numbers', which equal the sum of its proper divisors. Mathematicians have also defined sociable numbers and betrothed numbers, which are similar to amicable numbers. But perhaps these are for another Euler problem. Euler Problem 23 is about finding abundant numbers, which are numbers for which the sum of its proper divisors is higher than the number itself.
Amicable numbers were known to the Pythagoreans, who credited them with many mystical properties. Before we had access to computers, finding amicable numbers was a task that required a lot of patience. No algorithm can systematically generate all amicable numbers, and until 1946 only 390 pairs were known. Medieval Muslim mathematicians developed several formulas to create amicable numbers, but the only way to be complete is by using brute force.
Project Euler 21 Definition
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 \neq 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.
Proposed Solution
The first part of the code provides for a function to list all proper divisors for a given integer x.
The loop determines the divisors for numbers 220 to 10,000, calculates their sum and then checks if these numbers are amicable.
## Project Euler 21: Amicable Numbers
divisors <- function(x) {
divisors <- vector()
d <- 1
for (i in 1:floor(sqrt(x))) {
if (x %% i == 0) {
divisors[d] <- i
if (i != x/i) {
d <- d + 1
divisors[d] <- x / i
}
d <- d + 1
}
}
return(divisors)
}
answer <- 0
n <- 220
while (n <= 10000) {
div.sum <- sum(divisors(n)) - n
if (n == sum(divisors(div.sum)) - div.sum & n != div.sum) {
answer <- answer + n
print(paste0("(", n, ", ", div.sum, ")"))
}
n <- n + 1
}
print(answer)Share this content
