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 * 1019, 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.
Algorithm to calculate semi perfect integers, lack of efficiency
java;optimization;algorithm;recursion;mathematics
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 writepublic 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.