Zumkeller numbers | Rosetta Code | #22

By -
URL to the problem page: http://rosettacode.org/wiki/Zumkeller_numbers


Zumkeller numbers are the set of numbers whose divisors can be partitioned into two disjoint sets that sum to the same value. Each sum must contain divisor values that are not in the other sum, and all of the divisors must be in one or the other. There are no restrictions on how the divisors are partitioned, only that the two partition sums are equal.

E.G. 

  • 6 is a Zumkeller number; The divisors {1 2 3 6} can be partitioned into two groups {1 2 3} and {6} that both sum to 6.
  • 10 is not a Zumkeller number; The divisors {1 2 5 10} can not be partitioned into two groups in any way that will both sum to the same value.
  • 12 is a Zumkeller number; The divisors {1 2 3 4 6 12} can be partitioned into two groups {1 3 4 6} and {2 12} that both sum to 14.


Even Zumkeller numbers are common; odd Zumkeller numbers are much less so. For values below 10^6, there is at least one Zumkeller number in every 12 consecutive integers, and the vast majority of them are even.


Find and display here, on this page, the first 220 Zumkeller numbers.
Find and display here, on this page, the first 40 odd Zumkeller numbers.



#include <iostream>
using namespace std;

long long int power(int a, int b) {
    long long int result = 1;
    for (int i = 0; i < b; i++) {
        result *= a;
    }
    return result;
}

int main() {
    long long int cnt = 0, oddcnt = 0, cnt2, a, b, tmp, num1, num2, odds[40];

    cout << "First 220 Zumkeller numbers are:" << endl;
    for (int i = 2; oddcnt < 40; i++) {
        if (cnt >= 220 && i % 2 == 0) {
            continue;
        }
        cnt2 = 2;
        for (int j = 2; j <= sqrt(i); j++) {
            if (i % j == 0) {
                if (j != (i / j)) {
                    cnt2 += 2;
                }
                else {
                    cnt2++;
                }
            }
        }
        a = 1;
        b = cnt2 - 2;
        int* divisors = new int[cnt2];
        divisors[0] = 1;
        divisors[cnt2 - 1] = i;
        for (int j = 2; j <= sqrt(i); j++) {
            if (i % j == 0) {
                if (j != (i / j)) {
                    divisors[a] = j;
                    divisors[b] = (i / j);
                    a++;
                    b--;
                }
                else {
                    divisors[a] = j;
                    a++;
                }
            }
        }
        int* binary = new int[cnt2];
        for (long long int j = 1; j < power(2, cnt2); j++) {
            tmp = j;
            num1 = 0;
            num2 = 0;
            for (int k = (cnt2 - 1); k >= 0; k--) {
                binary[k] = tmp % 2;
                tmp /= 2;
                if (binary[k] == 1) {
                    num1 += divisors[k];
                }
                else {
                    num2 += divisors[k];
                }
            }
            if (num1 == num2) {
                if (cnt < 220) {
                    cnt++;
                    cout << i << ", ";
                    if (cnt % 20 == 0) {
                        cout << endl;
                    }
                }
                if (i % 2 == 1) {
                    odds[oddcnt] = i;
                    oddcnt++;
                }
                break;
            }
        }
    }
    cout << endl << endl << "First 40 odd Zumkeller numbers are:" << endl;
    for (int i = 0; i < 40; i++) {
        cout << odds[i] << ", ";
    }
    cout << endl;
    return 0;
}



Comments

Post a Comment

My photo
Ercan Tomac
instagram.com/ercantomac