in reply to Re: Subset Sum Problem
in thread Subset Sum Problem
If the result is less than zero, the number is deficient. If greater than zero, it's abundant. If zero, it's perfect.gp ? x = 168415508261 %1 = 168415508261 ? sigma(x) - 2*x %2 = -75992596042
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.
|
|---|