Algorithm to calculate semi perfect integers, lack of efficiency

I'm working on an algorithm to calculate weird numbers, and to do so there are several properties that needs to be calculated, one of them being, if it is NOT a semi-perfect/pseudoperfect number.

My code can surely be done a lot more effectively because semi perfect numbers have very interesting properties. The first one being, every multiple of a semiperfect number is semiperfect. So for every semi perfect number calculated, the multiple of that number can be stored so it will not have to be recalculated.

What I don't know is if there is a way to calculate if a number is NOT a semi perfect number without having to calculate if it is. It really is ineffective to calculate if a number is semi perfect, just to know if it is NOT.

Imagine infinity, which has infinite valid divisors, to prove if it is a semi perfect number would take infinite amount of calculations, but would proving the opposite also take infinite amount of calculations?

Anyways here is my code (written in Java) which will return a boolean indicating whether or not a number is semi perfect:

/**
 * 
 * @param x
 *          a number to test if it is semiperfect or not.
 * @param list
 *          this is a array of the factors of x (e.g factors of 6 are 3, 2, 1 excluding itself).
 * @return true if x is semiperfect, false otherwise.
 */
public static boolean isSemiPerfect(int x, List list) {
    if (x == 0)
        return true;
    for (int i = 0; i < list.size(); i++) {
        int temp = list.remove(i);
        if (isSemiPerfect(x - temp, list)) // using recursion
            return true;
        list.add(i, temp);
    }

    return false;
}

It seems like it is not possible to create a more effective algorithm to check if a number is NOT semi perfect, on the other hand, my current algorithm to check if a number is semi perfect or not can be improved.

I believe semi perfect numbers have some properties that would prevent the need to calculate every number, for instance. So far NO weird numb

Funny enough I was working on the same problem. My performance issue is not the Semi-Perfect part, but the check of abundancy.

You can call this (C#) function to check for a number being SemiPerfect.

static bool IsSemiPerfect(BigInteger delta, BigInteger[] d, BigInteger[] dSum, int index, BigInteger sum)
{
    if (sum == delta)
        return true;

    if (index >= d.Length || sum > delta || delta > (dSum[index] + sum))
        return false;

    for (int i = index; i < d.Length; i++)
    {
        if (IsSemiPerfect(delta, d, dSum, i + 1, sum + d[i]))
            return true;
    }

    return false;
}

The parameters are the following:

• delta: sum of the divisors - n

• d: divisors, descending sorted!

• dSum: a cached calculation of the remaining sum

BigInteger[] dSum = new BigInteger[d.Length];
for (int i = d.Length - 1; i > -1; i--)
{
    BigInteger sum = 0;
    for (int j = divsIndex - 1; j >= i; j--)
        sum += d[j];
    dSum[i] = sum;
}

• index: 0, used for recursion

• sum: 0, used for recursion

The code runs much faster compared to the other answer, because of 3 major cuts in the search tree and a slightly different approach of the problem. It is also optimised to find an answer in a progressive way.

A check of a big N = 190000006875 with 119 divisors runs well below 1 second. I didn't do real profiling but my performance bottleneck is really somewhere else. It might be NP, but very well doable this way.

It seems that posting a reply in C# code on a Java topic is a bit of bad behaviour. To make it up I'll give some slightly off-topic but cool code to find really big record breaking weird numbers in Java, using Sidney Kravitz's algorithm.

public static BigInteger getPossibleWeirdNumber(int bits)
{
    BigInteger q = BigInteger.probablePrime(bits, new Random());
    int k = q.bitLength() - 1;
    BigInteger power2k = BigInteger.valueOf(2).pow(k);
    BigInteger r = ((power2k.multiply(q)).subtract(q.add(BigInteger.ONE))).divide(q.add(BigInteger.ONE).subtract(power2k));
    if(r.compareTo(power2k) > 0)
    {
        if(r.isProbablePrime(1000000) && q.isProbablePrime(1000000)) //Some final checking on primes
        {
            BigInteger weirdNumber = (BigInteger.valueOf(2).pow(k-1)).multiply(q).multiply(r);
            return weirdNumber;
        }
    }
    return null;
}

public static BigInteger getWeirdNumber(int bits)
{
    BigInteger r = getPossibleWeirdNumber(bits);
    while(r == null)
        r = getPossibleWeirdNumber(bits);

    return r;
}

The only problem is that this algorithm does not find odd weird numbers. It's easy to see why: The \$2^{k-1}\$ always will be an even number. Multiplying with an even number always results in an even number, so Sidney Kravitz's trick will help you find large weird numbers, but no odd ones. That's why I manually started looking.

By the way, the reason I used C# is the more clean look of the code when using BigInteger. The operator overloading in .Net is lovely.

StackExchange Code Review Q#58326, answer score: 7