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

Question

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

Not sure if it is an issue here, but why introduce floating point numbers and strings to store integers? — Thilo, Jun 24 '16 at 00:48
Does the numeric relationship between your answer and the correct one suggest anything to you? It does to me. — CPerkins, Jun 24 '16 at 01:20
@CPerkins yes I know it is half of the answer I have, but I don't really see anything wrong with my code — dhruvm, Jun 24 '16 at 01:21
What could cause a sum of a list of numbers to be double what it should be? — CPerkins, Jun 24 '16 at 03:07

score 1 · Accepted Answer · answered Jun 24 '16 at 04:32

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:

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);

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

1 Answers1