Algorithm to calculate semi perfect integers, lack of efficiency

Question

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<Integer> 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 number has been discovered which is a odd number.

So unless the number in question (x) is above 1.8 * 10¹⁹, every odd number doesn't have to be checked if it is semi perfect or not, because every weird number below that is even.

Taking a look at this, a list of properties can be found, which can reduce the amount of numbers that needs to be checked.

I've realized that it will be hard to eliminate the calculation aspect completely, but can be reduced a lot. So I would like to have help with my algorithm to improve it, and perhaps implement a few of these properties to reduce the need to check every single number.

Answer 1

As @vnp stated, there is no known efficient (i.e. polynomial-time) solution to the subset sum problem. That said, your code can be made to run faster, but first I want to address a few points.

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.

Suppose I said that I had a fast way to determine if a number is not semi-perfect; faster than the best possible way to determine if a number is semi-perfect. How would you know I was wrong? Without even looking at my code?

Imagine that such a method isNotSemiPerfect existed. Well then you could write

public static boolean isSemiPerfect(int n) {
  if (isNotSemiPerfect(n)) {
    return false;
  }
  return true;
}

So you see the problems are just as hard as each other.

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?

Semi-perfection (is that a word?) is defined only for positive integers; infinity is not an integer.

Now as for the code. Deleting from and inserting into a List is terribly inefficient. What we want is a way to enumerate the \$2^k\$ different sums of the proper divisors, where \$k\$ is the number of proper divisors.

Here's a way to do it that uses BigInteger as a counter. We let the counter range over \$[0, 2^k)\$, and at each step add the \$j\$th divisor to the sum if the \$j\$th bit of the counter is set.

public static boolean isSemiPerfect(int n, List<Integer> divisors) {
  BigInteger combinations = BigInteger.valueOf(2).pow(divisors.size());
  for (BigInteger i = BigInteger.ZERO; i.compareTo(combinations) < 0; i = i.add(BigInteger.ONE)) {
    int sum = 0;
    for (int j = 0; j < i.bitLength(); j++) {
      sum += i.testBit(j) ? divisors.get(j) : 0;
    }

    if (sum == n) {
      return true;
    }
  }

  return false;
}

I ran a test of printing the semi-perfect numbers under 500. On my machine, this method takes the run-time down from ~25s to ~0.9s.

In practice, you can use an int instead of a BigInteger for your counter, since if a number has more than 32 proper divisors, you will be waiting a long, long time.

Answer 2

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.

Answer 3

I have bad news. From the link you posted,

Identifying pseudoperfect numbers is therefore equivalent to solving the subset sum problem.

and a subset sum article states that

The given sum problem is NP-complete.

So I would not expect a really efficient solution.