Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine

Subset Sum Problem

by beretboy (Chaplain)
on Jun 14, 2003 at 00:34 UTC ( #265840=perlquestion: print w/replies, xml ) Need Help??
beretboy has asked for the wisdom of the Perl Monks concerning the following question:

This question is not perl specific, but I would like the help of the monks on it. I am dealing with a variant of a subset-sum problem, in which the set is a list of a number's proper divisors. The goal is to find wether a number is NOT semiperfect (ie. no subset of its divisors sum to it exactly.) Now a normal subset sum problem is O(2^n) complex, in which case I'm screwed because I'm dealing with numbers that have too many factors to complete the calculation in my lifetime (or the universe's for that matter.) I am trying to find (and hoping for) a shortcut based around the fact that all the numbers in the set are able to evenly divide the same number. I'm not saying this is the only shortcut, but its the one that seems likely to me. Any help would be greatly appreciated.

"Sanity is the playground of the unimaginative" -Unknown

Replies are listed 'Best First'.
Re: Subset Sum Problem
by Zaxo (Archbishop) on Jun 14, 2003 at 01:54 UTC

    Just some observations.

    • Any integer natural number may be decomposed into a product of powers of primes: $n == do { my $prod = 1; $prod *= $p[$_]**$k[$_] for 0..$#p; $prod } where @p are prime and @k are positive integers.
    • All proper divisors of $n are products of the form do { my $prod = 1; $prod *= $p[$_]**int rand($k[$_]+1) for 0..$#p; $prod } , and all such products are divisors.
    • There are therefore factorial(sum( @k)) proper divisors of $n. *
    • If $n is larger than the sum of all its divisors, no subset can sum to it either.
    • If $n is odd, an odd number of divisors will be in a sum which equals $n. If $n is even, an even number of the odd divisors will be in the sum.

    You are right that this is a hard problem. The factorization of $n alone is an age-of-the-universe problem for large $n. Math::Pari is able to factor numbers of up to 60 digits fairly quickly. It is fast for less than 50 digits.

    * Oops, that is not quite right. If an element of @k is greater than 1, there is a binomial coefficient of ways to forms a power of that prime. All those are equivalent, yielding the same factor. That makes the factorial function I leaped at significantly larger than the actual number of distinct factors. The correct number of distinct divisors of $n is do { $prod = 1; $prod *= ($_ + 1) for @k; $prod } . Thanks to OverlordQ for pointing me to the right calculation.

    After Compline,

      Math::Pari (or its command-line interface gp) also has a function sigma(x) that computes the sum of all divisors of x, including itself. So it would be easy to use it to compute whether x is abundant, deficient, or perfect:
      gp ? x = 168415508261 %1 = 168415508261 ? sigma(x) - 2*x %2 = -75992596042
      If the result is less than zero, the number is deficient. If greater than zero, it's abundant. If zero, it's perfect.

      That still doesn't find out for you if the number is weird or semiperfect, but it helps a little. Pari/gp can work with unlimited-precision numbers.

      Update: Since the abundance (sigma(x) - 2x) can be computed, one possible search you could do is for odd numbers with a low abundance. Then you only need to deal with a small subset of the divisors, those smaller than the abundance. That set might be small enough to make a solution feasible.

      For example, the abundance of 70 is 144-140=4. The only divisors that are under 4 are 1 and 2. Since there is no combination adding to 4, 70 is weird.

      Update2: Pari/gp also has operations (e.g algdep, lindep, matkerint) for LLL lattice reduction, a powerful method that can often break down knapsack problems in polynomial time. Here is a reference to a paper on using lattice reduction to solve knapsack problems (weird number testing is basically a knapsack problem): Lattice Reduction: a Toolbox for the Cryptanalyst.

      The Page used for that. A number like 1000 has prime factors 2^3 x 5^3.
      Take the factor 2 = 0 1 2 3 times = 4 choices
      Take the factor 4 = 0 1 2 3 times = 4 choices
      So all together there could be 4*4 = 16 distinct factors.
      Thanks to Zaxo for making me google for that :)
Re: Subset Sum Problem
by fglock (Vicar) on Jun 14, 2003 at 00:49 UTC

    There is some analysis of this problem in this page: - see "Problem 2"

    The interesting part is: "You only need to go to sqrt(x). If you find a d such that x%d == 0, then you know that d and x/d are both divisors. You do have to make a quick check to make sure that d and x/d are not equal before summing both".

Re: Subset Sum Problem
by OverlordQ (Hermit) on Jun 14, 2003 at 04:37 UTC
    Dunno if this will help or not but:

    Every multiple of a semiperfect number is semiperfect, as are all numbers:
    (2^m)p for m >= 1 and p, a prime between 2^m and 2^(m+1). (Guy 1994, p. 47).

    Biblio: Guy, R. K. "Almost Perfect, Quasi-Perfect, Pseudoperfect, Harmonic, Weird, Multiperfect and Hyperperfect Numbers." žB2 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 45-53, 1994.
      And for the heck of it if you need test cases, here's the first few odd Semiperfect/Pseudoperfect numbers:

      6, 12, 18, 20, 24, 28, 30, 36, 40, 42, 48, 54, 56, 60, 66, 72, 78, 80, 84, 88, 90, 96, 100, 102, 104, 108, 112, 114, 120, 126, 132, 138, 140, 144, 150, 156, 160, 162, 168, 174, 176, 180, 186, 192, 196, 198, 200, 204, 208, 210, 216, 220, 222, 224, 228, 234, 240, 246, 252, 258, 260, 264
Re: Subset Sum Problem
by beretboy (Chaplain) on Jun 14, 2003 at 03:08 UTC
    fglock: Thanks for the link! I'm going to contact Mr.Beech, looks like he was in a similar situation.

    Zaxo: Good points, but I'd like to point out a couple of things I did not mention earlier. The greater purpose here is to find "weird numbers", which are abundant and NOT semiperfect. No odd weird number is known, yet no proof of their non-existence has been formulated, so your last point is interesting.

    Everyone: I am not so concerned about the factoring, much more so about testing for the lack of semi-perfection.

    "Sanity is the playground of the unimaginative" -Unknown

      Ah! I wasn't sure how sophisticated you were or how much so you wanted to get. Now, I see you know what you want.

      Since you don't care what $n is, you may be able to select a set of factors to obtain particular properties. I think that you will have better success going at the problem from an algebraic point of view than searching numerically. These kinds of problems have usually been mined out for many digits.

      After Compline,

      I think you meant to say "no odd wierd number is known." The reference Weird Number lists several even ones.

      This reference to Semiperfect Numbers says that every multiple of a semiperfect number is semiperfect, which makes me think some form of sieving process would eliminate many cases quickly.

      Update: I found a paper using google: Sums of Divisors and Egyptian Fractions which has some interesting results on weird numbers. Two things it mentioned are that a computer search proved there are no odd wierds below 2^32, and that all abundant numbers of the form 3^a * 5^b * 7^c are semiperfect (where a, b, c > 0).

Re: Subset Sum Problem
by TomDLux (Vicar) on Jun 14, 2003 at 04:35 UTC

    CS people are notoriously mediocre mathemeticians. Why don't you find a math list to ask math questions


      On the other hand, sometimes mathematicians are mediocre programmers. Look at this "solution" to the subset sum problem: Subset Sum. He says to multiply out N binomials and collect the terms, which is O(2^N). Mathematically it's correct; computationally it's not feasible.

      (I know that the subset sum problem is NP-complete, it's just the author of the article presents this as a solution without mentioning the issue at all.)

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://265840]
Approved by Zaxo
Front-paged by educated_foo
Eily sets the confetti thrower
[Discipulus]: Eily adjust the shot: i'll be at seaside when it will happen
[Eily]: oh, I'll have to find something else then, don't want to litter the sea. Fireworks maybe?

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (10)
As of 2017-07-27 10:10 GMT
Find Nodes?
    Voting Booth?
    I came, I saw, I ...

    Results (409 votes). Check out past polls.