[seqfan] Re: Most efficient algorithm for selecting divisors of an abundant number?
Alonso Del Arte
alonso.delarte at gmail.com
Mon Sep 5 22:44:14 CEST 2011
Yes, solutions that use "as many of the initial divisors as possible." When
I look at the divisors written out, the first solution that pops into my
head is using the larger non-trivial divisors (e.g., 15 + 10 + 5).
With the talk of NP-completeness, this suggests a computer can look at this
more efficiently than my stubborn brain.
On Sun, Sep 4, 2011 at 11:56 PM, <franktaw at netscape.net> wrote:
> I'm not sure exactly what your criteria are. Do you want a solution that
> includes as many divisors as possible? Or one that uses as many of the
> initial divisors as possible?
> In any case, for 30 your solution is optimal. To get 12 (the amount
> skipped) with divisors of 30, 15 is too big. With 10, you have to take 2, as
> in your example. With neither 15 nor 10, the only solution is 1, 5, 6
> (leaving 2, 3, 10, 15), which is clearly inferior by either criterion.
> Franklin T. Adams-Watters
> -----Original Message-----
> From: Alonso Del Arte <alonso.delarte at gmail.com>
> 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