Problem 88 - A struggle completed in C

Problem 88 was quite the problem. I am absolutely certain that the answer I have now is not the best solution, but it is definitely a solution. This problem investigates "Product Sum numbers" - numbers that are both the sum and product of collections of numbers. I got some insight into some of the math going on by reading a paper I found online on the subject: http://www-users.mat.umk.pl/~anow/ps-dvi/si-krl-a.pdf. From what I found in that paper, I wrote up a solution in Python, which gave the correct answer...in 30 minutes. In the search for a faster solution, I realized that I was actually computing all I needed for an answer in the first minute or so of the problem and then used a lot of unnecessary computation to find the answer.

The key to making the problem tractable was to notice that though the problem asks for the minimal Product-Sum numbers for a given k (size of the set for which it is a PS number), the easier domain was to look at numbers and find for what k values they are product sum numbers. When I made this switch, I when from minutes to seconds in the speed of my code.

However, the script that I ran to initially compute the answer was written in python, for ease, but I knew I had to convert to another language eventually for the language challenge. I ended up going with C, and while C works, I ran into...a bit of an issue. In Python I was just using lists and wasn't aware of just how much memory was flying around, but when I wrote a solution in C I found out that the solution actually involves allocating many million-element arrays...so after pushing the size of my arrays and making sure to allocate and free memory well to avoid seg faults, I eventually got to a working solution, which is below. Runs in about 16 seconds in my machine. Much of that time is probably spent in malloc.

#include<stdio.h>
#include<stdlib.h>

int BOUND = 12000;

/** Gets the sums of all factoriations of n, minus the number of terms in the
 *  factorization. This is most of the k-value for which n is a Product-Sum number
 *  k-value = n - factorizationSum*/

/** Admittably not the most efficient of code...this is what I get for
 *  trying to transfer code originally written in python
 */
void getAllFactorizationSums(int n, int includeself,
        int maxlength, int* output, int* outputLength) {

    /**Don't look at exceptionally long factorizations*/
    if (maxlength == 0) {
        output[0]     = -1;
        *outputLength =  1;
        return;
    }
    int*  returnValue = (int*) malloc(sizeof(int) * 15 * BOUND);
    int  rvLength = 0;
    int f;
    for (f = 2; f*f <= n; ++f) {
        if (n % f == 0) {
            getAllFactorizationSums(n / f, 1, maxlength - 1, output, outputLength);
            int j;
            for (j = 0; j < *outputLength; ++j) {
                int fSum = output[j];
                if (fSum != -1) {
                    returnValue[rvLength++] = fSum + f - 1;
                }
            }
        }
    }
    if (includeself) {
        returnValue[rvLength++] = n - 1;
    }
    //copy back to output
    int i;
    for (i = 0; i < rvLength; ++i) {
        output[i] = returnValue[i];
    }
    *outputLength = rvLength;
    free(returnValue);
} 

int min(int x, int y) { return x < y ? x : y; }

int main(int argc, char ** argv) {
    int* productSumsForK = (int*) malloc(sizeof(int) * (BOUND + 1));
    productSumsForK[0] = 0; productSumsForK[1] = 0;
    int i;
    /**Initialize with upper bounds*/
    for (i = 2; i <= BOUND; ++i) {
        productSumsForK[i] = 2 * i;
    }
    /**Allocate lots of space...most of it actually gets used!*/
    int* factorizationSums = (int*) malloc(sizeof(int) * 15 * BOUND);
    int fsLength = 0;
    int N;
    for (N = 4; N <= 2*BOUND; ++N) {
        getAllFactorizationSums(N, 0, 15, factorizationSums, &fsLength);
        for (i = 0; i < fsLength; ++i) {
            int kIndex = N - factorizationSums[i];
            if (kIndex <= BOUND) {
                productSumsForK[kIndex] = min(productSumsForK[kIndex], N);
            }
        }
    }

    //Now, we need to convert to a set to print the answer
    char set[BOUND/4];
    for (i = 0; i < BOUND/4; ++i) { set[i] = 0; }
    for (i = 0; i <= BOUND; ++i) {
        int psNum = productSumsForK[i];
        set[psNum / 8] |= (1 << (psNum % 8));
    }
    int sum = 0;
    for (i = 0; i < 2*BOUND; ++i) {
        if ((set[i / 8] >> (i % 8)) & 1) {
            sum += i;
        }
    }
    printf("%d\n", sum);
    return 0;
}