11
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ "It really is ineffective to calculate if a number is semi perfect, just to know if it is NOT." Determining if a number is not semi-perfect is just as hard as determining if it is semi-perfect. "Imagine a number with infinite valid divisors..." Any number has finitely many proper divisors. \$\endgroup\$ – mjolka Jul 29 '14 at 1:27
  • \$\begingroup\$ "unless the number in question (x) is above 1.8 * 10^19…" - x is an int and so has a maximum value of ~2e9. If you want larger values, use BigInteger. \$\endgroup\$ – mjolka Jul 31 '14 at 7:44
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thank you, I mentioned some false statements without even thinking what it meant. But from previous experiences, I find BigInteger and BigDecimal much slower than a int and double? Would I benefit from using BigInteger? \$\endgroup\$ – Linus Aug 1 '14 at 10:36
  • \$\begingroup\$ @Linus int will be faster but I think the code will be trickier to get right. It will make a fun exercise though :) thanks for posting a good question. \$\endgroup\$ – mjolka Aug 1 '14 at 10:44
  • \$\begingroup\$ I did manage to get it working by using the Integer.bitCount method and as a replacement for the testBit method, I used (i & (1L << j)) != 0, it worked out very well. And to resolve the issue where the amount of combinations would be greater than the maximum value of a integer, I made a check and if so, I called the method which involves BitInteger :) \$\endgroup\$ – Linus Aug 1 '14 at 10:51
  • \$\begingroup\$ @Linus nice work! I'm sure if you post that code for review, someone more proficient in Java than I am will have a look at it. \$\endgroup\$ – mjolka Aug 1 '14 at 10:54
  • \$\begingroup\$ I think I'll be satisfied with this code thanks, although, I wanted to see if a specific number is semiperfect (2850960) which unfortunately gives 6.044629098073146 × 10^23 unique combinations. And if a computer (with today's processor) would manage around 10^9 operations per second, it would at most take approximently 191.5 years to calculate if 2850960 is semi perfect, unless a combination which adds up to 2850960 is found much earlier. \$\endgroup\$ – Linus Aug 1 '14 at 11:05
7
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ C# code for an Java question is really weird. Are you reviewing Op algorithm or just sharing your approach ? \$\endgroup\$ – Marc-Andre Aug 6 '14 at 13:19
  • \$\begingroup\$ OP had a problem with the performance of his algorithm. Mine fixes that. Yes it is C#, but well readable for someone programming Java. Is this really weird? Then this might be my only contribution to this forum. \$\endgroup\$ – Nipokkio Aug 6 '14 at 13:31
  • \$\begingroup\$ I'd add a reference to java.math.BigInteger and it's functions, as well as explaining how to port this function to Java. That would help the OP and everyone else coming here later. \$\endgroup\$ – Pimgd Aug 6 '14 at 13:49
  • 5
    \$\begingroup\$ @Nipokkio don't let this incident be the reason why you only contributes once. We do try to answer in the same language or keep us to the improved algorithm itself without the code. You'll notice it when you hang around in the chat we are all friendly people. \$\endgroup\$ – chillworld Aug 6 '14 at 13:59
  • 2
    \$\begingroup\$ It's been shown that you don't have to be an absolute expert in a language to give a good review. Nipokkio reviewed the code and showed how he would do it in a language he is comfortable in. I see no issues with this. The code in this answer is nearly agnostic. \$\endgroup\$ – RubberDuck Aug 6 '14 at 14:40
5
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.