Project Euler, problem 21

[alfin informatics]

I'm trying to solve problem 21 from Project Euler site, I think that I don't have any mistakes, but I get wrong result, can anyone find mistake that occurs. I get 18320, but correct answer is 31626.

    #include <iostream>

    using namespace std;

    unsigned long sumOfDivisors(unsigned int a){
        unsigned long sum = 0;
        for(unsigned int i=1; i<=a/2; i++)
            if(a%i==0)
                sum+=i;

        return sum;
    }

    int main()
    {
        unsigned int n = 10000;
        unsigned long long sum = 0;

        for(unsigned int i=1; i<n; i++)
            if(sumOfDivisors(i)==sumOfDivisors(sumOfDivisors(i)))
                sum+=(sumOfDivisors(i)+sumOfDivisors(sumOfDivisors(i)));

        cout << sum << endl;

        return 0;
    }

[Naughty Albatross]

Hi,
Can you please give some little details about the algorithm you are trying to write?

[alfin informatics]

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.

[Naughty Albatross]

unsigned long sumOfDivisors(unsigned int a)
{
        unsigned long sum = 0;
        for(unsigned int i=1; i<=a; i++)
            if(a%i==0)
                sum+=i;
        return sum;
    }

You simply forgot that a number can also be divisible by itself. For example : 8 can be divided by 8, accordingly.

[alfin informatics]

But in task text, 220 don't have 220 as divisor. So, I suppose that we don't need to include number as divisor.
And I have tried that, but I get result 2.

[Naughty Albatross]

> But in task text, 220 don't have 220 as divisor
Then just use your old function.

unsigned int n = 10000;
        unsigned long long sum = 0;
        for(unsigned int i=1; i<n; i++)
            if(sumOfDivisors(i)==sumOfDivisors(sumOfDivisors(i)))
                sum +=(sumOfDivisors(i)+sumOfDivisors(sumOfDivisors(i)));
        cout << sum << endl;

Your program is actually doing too much. According to your algorithm, only a single function call is more than enough to fix the problem.

unsigned int n = 10000;
        unsigned long long sum = sumOfDivisors(n);
        cout << sum << endl;

[Naughty Albatross]

Does that help you? :)

[alfin informatics]

Again I get wrong result->14211

[alfin informatics]

Here is how they solve this task in C:

#include <stdio.h>
#include <stdlib.h>
 
unsigned int sum_divisors(unsigned int n) {
    unsigned int s = 0, i = 1;
    while(i < n) {
        if(n % i == 0) s = s + i;
        i++;
    }
    return s;
}
 
unsigned int sum_amicable_pairs(unsigned int low, unsigned int high) {
    unsigned int a = low, b, sum = 0;
    while(a <= high) {
        b = sum_divisors(a);
        if(b > a && sum_divisors(b) == a) sum = sum + a + b;
        a++;
    }
    return sum;
}
 
int main(int argc, char **argv) {
    unsigned int ans = sum_amicable_pairs(1,10000);
    printf("result: %d\n",ans);
    return 0;
}

[Naughty Albatross]

So you already have a solution? O.o

Anyway, here is my solution :

unsigned int k;
for(unsigned int i=1; i<=n; i++)
{
    k = sumOfDivisors(i);
if(sumOfDivisors(k) == i && i != k)
      sum += (i + k);
}
cout << "Sum : " << sum << endl; 

[alfin informatics]

Yes, I have that solution, but I want to know why my solution don't work, I don't want to just copy-paste solution from internet
And also, I have tried your solution, but it don't work too.

[Naughty Albatross]

I edited my solution.
Let me know your program output.

[alfin informatics]

Nope-63252 :) And answer is 31626

[Naughty Albatross]

That's strange. This :

unsigned int sum = 0; 
unsigned int k;
for(unsigned int i=1; i<=n; i++)
{
    k = sumOfDivisors(i);
if(sumOfDivisors(k) == i && i != k)
{
      cout << "Amicable found (";
      cout << k << " - " << i << ")" << endl;
      sum += (i + k);
}
}
cout << endl << "Sum : " << sum << endl;

Just copy all the program output and show it to us.

[alfin informatics]

Here is the screenshot: http://imgur.com/tUGcJor I think that we only need to divide result by 2, and than we get correct answer.

[Naughty Albatross]

> Here is the screenshot: http://imgur.com /tUGcJor
Sorry, I can't see :)
Why don't you just post raw text here? It is so much easier to spot :)

> I think that we only need to divide result by 2, and then we get correct answer.
Is that so? How brilliant of you!!

[Naughty Albatross]

Woah, I noticed this :

Amicable found (284 - 220)
Amicable found (220 - 284)

A pair of amicable numbers are encountered at least two times. That fully explains that why the result is double though :)