21.Amicable numbers

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.

Pythagoras when asked, “What is a friend”, replied that a friend is one “who is the other I” such as 220 and 284.  The numbers 220 and 284 form the smallest pair of amicable numbers (also known as friendly numbers) known to Pythagoras.

http://www.shyamsundergupta.com/amicable.htm

One simple rule given by Arab Thabit ibn Korrah in 9th century is given below:  Take any power of 2, such as 2n where n>1 and form the numbers   h = 3.2^n –1,    t = 3.2^n-1 –1,     s = 9.2^2n-1 –1

If h, t and s are all primes then 2^n ht and 2^n s are amicable.

For example when n=2, we get h=11, t=5 and s=71, which are all primes hence 2n h t = 220 and 2n s = 284 are amicable numbers.
Similarly when n = 4, we get the amicable pair (17296, 18416).

There is a possible ambiguity here: should both members of a pair be below 10000 or does the condition also include pairs (a,b) for which a<10000, but b not. If you displayed all pairs you found, you will have noticed that there is no such pair, so we will not bother.

import java.util.Calendar;
public class Problem21 {
    public void amicablePE() {
        double sum = 0;
        for (int i=2;i<99999;i=i+1){
            int b = SumOfProperDivisors(i);
            if (b>i){
                if (SumOfProperDivisors(b)==i){
                    sum+=i+b;
                    System.out.println(i + " - " + b + " - " +sum);
                }
            }
        }
        System.out.println(sum);
    }
    
    public int SumOfProperDivisors(int n){
        int sum=1;
        for(int f=2;f<=n-1;f++) {
            if (n%f==0) sum+=f;
        }
        return sum;
    }
    
    public void amicablePE1() {
        double sum = 0;
        for (int i=2;i<99999;i=i+1){
            int b = SumOfProperDivisors1(i);
            if (b>i){
                if (SumOfProperDivisors1(b)==i){
                    sum+=i+b;
                    System.out.println(i + " - " + b + " - " +sum);
                }
            }
        }
        System.out.println(sum);
    }
    
    public int SumOfProperDivisors1(int n){
        int r= 1, sum =1, f=0, step=0;
        if(n==1)
            return 0;
        else
            r=(int)Math.floor(Math.sqrt(n));
        
        //first take into account the case that n is a perfect square.
        if (r*r==n) { 
            sum=1+r;
            r=r-1; 
        } else {
            sum=1;
        }
        if (n%2==1) {
            f=3; 
            step=2;
        } else {
            f=2;
            step=1;
        }
        while (f<=r) {
            if (n%f==0)
                sum=(sum+f+n/f);
                f=f+step;
        }
        return sum;
    }
   
/* In fact this can be even improved on using the prime factorisation of n.     If we know the prime factorisation if n it is easy to calculate the sum of the divisors of n from  that.  The sum of the proper divisors of n is then the sum of the divisors of n minus n itself.  More on this can be found on the companion website to Project Euler:  http://mathschallenge.net/index.php?section=faq&ref=number/sum_of_divisors*/
    
    public void amicablePE2() {
        double sum = 0;
        for (int i=2;i<99999;i=i+1){
            int b = SumOfProperDivisors3(i);
            if (b>i){
                if (SumOfProperDivisors3(b)==i){
                    sum+=i+b;
                    System.out.println(i + " - " + b + " - " +sum);
                }
            }
        }
        System.out.println(sum);
    }
    public int SumOfProperDivisors3(int n) {
        return SumOfDivisors(n)-n;
    }
/*  The line:   while p*p<=n and n>1  prevents us from checking prime factors greater then n . Note that as more and more primefactors get divided out, n gets smaller and smaller and the upperlimit for p decreases accordingly!
The line:  if n>1 then sum=sum*(n+1)  covers the case that one prime factor greater than n remains.  */    
    public int SumOfDivisors(int n) {
        int sum=1, p=2,j=0;
        while(p*p<=n && n>1) {
            if (n%p==0) {
                j=p*p;
                n=n/p;
                while(n%p==0){
                    j=j*p;
                    n=n/p;
                }
                sum=sum*(j-1);
                sum=sum/(p-1);
            }
            if (p==2) p=3; else p=p+2;
        }
        if (n>1) sum=sum*(n+1);
        return sum;
    }
        
    public static void main(String[] args) {
        long start = 0, end=0;
        Problem21 p = new Problem21();
        start =(Calendar.getInstance()).getTimeInMillis();
        p.amicablePE();
        end =(Calendar.getInstance()).getTimeInMillis();
        System.out.println(start + " - " + end  + " - " +(end-start) + " Time");
        
        start =(Calendar.getInstance()).getTimeInMillis();
        p.amicablePE1();
        end =(Calendar.getInstance()).getTimeInMillis();
        System.out.println(start + " - " + end  + " - " +(end-start) + " Time");
        
        start =(Calendar.getInstance()).getTimeInMillis();
        p.amicablePE2();
        end =(Calendar.getInstance()).getTimeInMillis();
        System.out.println(start + " - " + end  + " - " +(end-start) + " Time");
    }
}

Advertisement

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 )

Connecting to %s

%d bloggers like this: