[seqfan] Re: Most efficient algorithm for selecting divisors of an abundant number?
jfb at brennen.net
Mon Sep 5 06:01:18 CEST 2011
Isn't this basically a sequence of knapsack problems?
In other words, can we find some subset of the first k divisors which add up to N?
If not, can we find some subset of the first k+1 divisors which add up to N?
If not, can we find some subset of the first k+2 divisors which add up to N?
Etc., etc., etc.
If it is, the knapsack problem (specifically the subset sum problem) is known to
be NP-complete, so that gives you some idea of what type of "most efficient"
algorithm you'd be looking for.
For the case you gave, of 30, note that the divisors are 1,2,3,5,6,10,15.
If you take the first six divisors and sum them, you only get to 27, so that's
impossible. And if you take all seven divisors, you need to skip at least two
of them, and in fact there is only one way to do it which skips two, which is
the solution that you gave.
On 9/4/2011 8:48 PM, 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
> For example, with 30, I'm not convinced 1 + 3 + 5 + 6 + 15 (skipping over 2
> and 10) is the best selection.
> Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan