Re: Subset Sum Problem

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,
Zaxo

Comment on Re: Subset Sum Problem Select or Download Code

Replies are listed 'Best First'.
Re: Re: Subset Sum Problem by tall_man (Parson) on Jun 14, 2003 at 22:04 UTC
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) - 2x %2 = -75992596042` [download] 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.	[reply] [d/l]
Re: Re: Subset Sum Problem by OverlordQ (Hermit) on Jun 15, 2003 at 01:53 UTC
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 :)	[reply]