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

franktaw at netscape.net franktaw at netscape.net
Mon Sep 5 05:56:26 CEST 2011

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 

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 
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: 
select the first k divisors.

In the case of the weird numbers (A006037) the answer is just as easy: 
selection is possible.

But with other abundant numbers, how do you decide which divisors to 
over, other than trying each possible selection and weighing it against 

For example, with 30, I'm not convinced 1 + 3 + 5 + 6 + 15 (skipping 
over 2
and 10) is the best selection.


More information about the SeqFan mailing list