[seqfan] Re: Most efficient algorithm for selecting divisors of an abundant number?

[israel at math.ubc.ca]

Given a set S of positive integers and a positive integer N, the problem of 
selecting a subset whose sum is N is the "subset sum problem". This is 
NP-complete, but there is, for example, a pseudo-polynomial-time dynamic 
programming algorithm which works quite well if N is not too big. See e.g. 
<http://en.wikipedia.org/wiki/Subset_sum_problem>

Robert Israel                                israel at math.ubc.ca
Department of Mathematics        http://www.math.ubc.ca/~israel 
University of British Columbia            Vancouver, BC, Canada

On Sep 4 2011, Alonso Del Arte wrote:

>What would be the most efficient algorithm for selecting divisors of an
>abundant number that add up to that number such that the smallest divisors
>are used and the fewest divisors are skipped over for larger divisors?
>
>In the case of the Erdős-Nicolas numbers (A194472) the answer is easy: just
>select the first k divisors.
>
>In the case of the weird numbers (A006037) the answer is just as easy: no
>selection is possible.
>
>But with other abundant numbers, how do you decide which divisors to skip
>over, other than trying each possible selection and weighing it against the
>goals?
>
>For example, with 30, I'm not convinced 1 + 3 + 5 + 6 + 15 (skipping over 2
>and 10) is the best selection.
>
>Al
>
>_______________________________________________
>
>Seqfan Mailing list - http://list.seqfan.eu/
>