[seqfan] Re: Most efficient algorithm for selecting divisors of an abundant number?
israel at math.ubc.ca
israel at math.ubc.ca
Mon Sep 5 06:11:31 CEST 2011
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/
>
More information about the SeqFan
mailing list