user3798602 user3798602 - 5 months ago 8
Java Question

Getting 63252 for Project Euler 21. Why is this incorrect?

Project Euler question:

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.

My solution in Java:

public class problem21 {

private static int answer = 0;
public static void main(String[] args){

for(int a = 1; a<10000; a++){
int b = calculateSumOfDivisorsOf(a);
if(calculateSumOfDivisorsOf(b) == a && b!=a){
//amicable numbers
//a is always amicable
answer+=a;
if(b<10000){
//b is an amicable number under 10000
answer+=b;
}
}
}
System.out.println(answer);
}
public static int calculateSumOfDivisorsOf(double num){
String divisors = "1";
int sum = 0;
for(int i = 2; i< Math.sqrt(num); i++){
if(num%i == 0){
divisors+= " " + i;
if(num/i != i){
divisors += " " + num/i;
}
}
}

double[] divisorsArr = new double[divisors.split("\\s+").length];
for(int i = 0; i< divisors.split("\\s+").length; i++)
divisorsArr[i] = Double.parseDouble(divisors.split("\\s+")[i]);

for(int i = 0; i < divisorsArr.length; i++)
sum+= divisorsArr[i];

return sum;
}


}

My(incorrect) answer:
63252

What is wrong with my code?
The correct answer is 31626

Answer

When I try to debug your code I found that you adding a,b (amicable numbers) twice. Check your code and output.

    for (int a = 1; a < 10000; a++) {
        int b = calculateSumOfDivisorsOf(a);
        if (calculateSumOfDivisorsOf(b) == a && b != a) {
            // amicable numbers
            // a is always amicable
            answer += a;
            System.out.println(a); //NOTE I AM PRINTING 'a'
            if (b < 10000) {
                // b is an amicable number under 10000
                answer += b;
                System.out.println(b); // //NOTE I AM PRINTING 'b'
            }
        }
  }

Output is:

220 
284
284
220
1184
1210
1210
1184
2620
2924
2924
2620
5020
5564
5564
5020
6232
6368
6368
6232

Now you can see that your are adding a,b twice. You didn't check whether a,b already add or not. Check below code.

List<Integer> l = new ArrayList<Integer>(); //List to add a,b
        for (int a = 1; a < 10000; a++) {
            int b = calculateSumOfDivisorsOf(a);
            if (calculateSumOfDivisorsOf(b) == a && b != a && !l.contains(a) && !l.contains(b)) { //Check whether list contain a,b
                // amicable numbers
                // a is always amicable
                answer += a;
                l.add(a); //add a to list
                if (b < 10000) {
                    // b is an amicable number under 10000
                    answer += b;
                    l.add(b); //add b to list
                }
            }
        }
        System.out.println(answer);