Weird numbers | Rosetta Code | #25

URL to the problem page: http://rosettacode.org/wiki/Weird_numbers


In number theory, a weird number is a natural number that is abundant but not semiperfect (and therefore not perfect either).

In other words, the sum of the proper divisors of the number (divisors including 1 but not itself) is greater than the number itself (the number is abundant), but no subset of those divisors sums to the number itself (the number is not semiperfect).

For example:

• 12 is not a weird number.

•     It is abundant; its proper divisors 1, 2, 3, 4, 6 sum to 16 (which is > 12),
•     but it is semiperfect, eg 6 + 4 + 2 == 12.

• 70 is a weird number.

•     It is abundant; its proper divisors 1, 2, 5, 7, 10, 14, 35 sum to 74 (which is > 70),
•     and there is no subset of proper divisors that sum to 70.

Find and display, here on this page, the first 25 weird numbers.

#include <iostream>

using namespace std;

unsigned long long int power(int a, int b) {

    unsigned long long int result = 1;

    for (int i = 0; i < b; i++) {

        result *= a;

    }

    return result;

}

int main()

{

    int cnt, cnt2 = 0, a, sum, divisors[1024] = { 0 };

    unsigned long long int tmp;

    cout << "First 25 weird numbers are:" << endl;

    for (int i = 10; cnt2 < 25; i += 2) {

        if (i % 3 != 0 && i % 4 != 0 && i % 5 != 0) {

            continue;

        }

        a = 2;

        sum = (i / 2) + 3;

        for (int j = 3; j <= (i / 3); j++) {

            if (i % j == 0) {

                divisors[a] = j;

                a++;

                sum += j;

            }

        }

        if (sum == i || sum < i) {

            continue;

        }

        divisors[0] = 1;

        divisors[1] = 2;

        divisors[a] = i / 2;

        a++;

        int* binary = new int[a - 2];

        cnt = 0;

        for (unsigned long long int j = (power(2, (a - 2)) - 1); j > 0; j--) {

            sum = divisors[a - 1] + divisors[a - 2];

            tmp = j;

            for (int k = 0; k < (a - 2); k++) {

                binary[k] = tmp % 2;

                tmp /= 2;

                if (binary[k] == 1) {

                    sum += divisors[k];

                    if (sum > i || sum == i) {

                        break;

                    }

                }

            }

            if (sum == i) {

                cnt++;

                break;

            }

        }

        if (cnt == 0) {

            cout << i << " (" << a << " divisors.)" << endl;

            cnt2++;

        }

    }

    return 0;

}

CLICK TO SEE THE OUTPUT.