Today's number theory naive algorithm: amicable or friendly numbers
Sunday, July 13, 2008
A pair of friendly numbers--the contemporary term is amicable numbers--are numbers such that "each is equal to the sum of the other's proper divisors (divisors other than the number itself)" (I got this definition from Paul Hoffman's book about Paul Erdos,
The Man Who Loved Only Numbers, p.45).
The first pair of friendly numbers is (220, 284), with their proper divisors [1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110] for 220, and [1, 2, 4, 71, 142] for 284.
Before I go onto my naive implementation to find pairs of friendly numbers, here is an easy problem:
prove that there are an infinite number of friendly pairs.
Where does this definition of
friendliness come from? From none other than
Pythagoras. He discovered the first pair (220, 284).
According to Hoffman, it took another 22 centuries for the second smallest pair (1184, 1210) to be found, by an Italian school boy in 1866.
I find it hard to believe that it took so long to get another pair, given that the algorithm to find them is obvious:
- Let A be an integer greater than 0; get the proper divisors of A.
- Add the divisors of A, and let the sum be equal to B.
- Get the divisors of B.
- Sum the divisors of B, and let the sum be equal to C.
- Finally, if B is equal to C, then we have a friendly pair.
I have to admit that doing this by hand can become a tedious and long process, but doable with a lot of time in your hands, a pen with a lot of ink, and a few sheets of paper (don't use a calculator, it takes the fun out of it).
I haven't studied the problem to come up with a short formula to generate these pairs of numbers (I haven't tainted my mind with web searches, so the algorithm and program are 100% my creation), but computers are very good at doing trivial math, so below is a very naive program to generate such pairs.
I say it's naive, because it's just a literal implementation of the algorithm I came up with above. The running time is horrible, because I check if every number between 1 and n/2 is a proper divisor of n. This thing is set to run for ever, and it's very fast to generate the first few pairs. As the program starts checking for larger numbers, it takes longer to find the proper divisors. It's also very dumb in the sense that it doesn't know that (66992, 66928) is the same as (66928, 66992), and it wastes cycles checking for both numbers even when we know that the proper divisors will be the same.
Note that generated pairs such as (28, 28) are not errors: the number in the pair has some special
properties, which I'm not qualified today to say what they are. Obviously, these generated pairs are not considered amicable numbers, even though they are part of the output in my program--I decide to leave them, as this is the first writing of the program.
[UPDATE: the number in this pair, is actually a
perfect number. It will take this program a long time to find them.]
A few interesting tidbits from running the program:
- The first 3 divisors are the same for even numbers (well, so far--and we know that running a program for a long time is not a mathematical proof).
- When I first looked at the definition, I thought only even numbers would be friendly pairs. I was obviously wrong, when I saw the pairs (12285, 14595), (69615, 87633).
- The largest pair I have so far is (308620, 389924). The app has only been running for about tow hours or so. Your mileage may vary.
The program (
some output):
import java.util.ArrayList;
public class FriendlyNumbers {
/**
* Calculate friendly numbers.
* A pair of friendly numbers are numbers such
* that each is equal to the sum of the other's
* proper divisors (divisors * other than the number itself).
*
* Example:
*
* (220, 284)
* Divisors for 220: [1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110]
* Divisors for 284: [1, 2, 4, 71, 142]
*
*
* @param args
*/
public static void main(String[] args) {
long testNumber1 = 1;
long testNumber2 = 0;
Divisors possibleFriendly1;
Divisors possibleFriendly2;
for (;;) {
possibleFriendly1 = getDivisors(testNumber1);
testNumber2 = possibleFriendly1.getSum();
possibleFriendly2 = getDivisors(possibleFriendly1.getSum());
if (testNumber1 == possibleFriendly2.getSum()
&& testNumber2 == possibleFriendly1.getSum()) {
System.out.println("------------");
System.out.println("(" + testNumber1 + ", "
+ testNumber2 + ")");
System.out.println("Proper divisors for "
+ testNumber1 + ": "
+ possibleFriendly1.getDivisors().toString());
System.out.println("Proper divisors for "
+ testNumber2 + ": "
+ possibleFriendly2.getDivisors().toString());
System.out.println("------------");
}
testNumber1++;
}
}
private static Divisors getDivisors(long testNumber) {
long sum = 0;
long possibleDivisor = 1;
ArrayList divisors = new ArrayList();
while (possibleDivisor <= (testNumber / 2)) {
if ((testNumber % possibleDivisor) == 0) {
divisors.add(possibleDivisor);
sum += possibleDivisor;
}
possibleDivisor++;
}
return new FriendlyNumbers.Divisors(sum, divisors);
}
static class Divisors {
private long sum;
private ArrayList divisors;
public Divisors(Long sum, ArrayList divisors) {
this.sum = sum;
this.divisors = divisors;
}
public long getSum() {
return sum;
}
public void setSum(long sum) {
this.sum = sum;
}
public ArrayList getDivisors() {
return divisors;
}
public void setDivisors(ArrayList divisors) {
this.divisors = divisors;
}
}
}
Comments: