[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

221.0. "abundant sums" by HARE::STAN () Sun Feb 10 1985 17:55

Richard V. Andree asks, in the Problems and Puzzles column of Abacus:

Find the maximum number of ways in which an integer < 10^6 can
be expressed as the sum of two abundant numbers.

This is problem 12 in a series and the first solution including
a working computer program will win a book prize.

Reference:

Richard V. Andree. Problems and Puzzles. Abacus. 2(1985 no. 2)63.
T.RTitleUserPersonal
Name
DateLines
221.1METOO::TOOLSHEDTue Feb 12 1985 16:235
An 'abundant' number is one the sum of whose divisors is greater than itself,
in case you didn't already know that...
An example is 24, whose divisors are 1,2,3,4,6,8,12, which sum to 36.
(To be precise, I guess you have to specify aliquot divisors, which excludes 
the number itself as a divisor.) - Lynn
221.2TURTLE::GILBERTFri Feb 15 1985 22:247
I have such a working program -- the problem is that it'll be a few months
before it completes.  Determining which numbers are abundant is easy; the
hard part is determining the number of ways a number < 10^6 can be expressed
as the sum of two of them.  The straight-forward approach is "order N squared",
where N about 10^12.

Any suggestions for fast algorithms ot do this?  Thanks.
221.3TURTLE::GILBERTSun Feb 17 1985 07:3518
Although it doesn't matter, I've assumed that X+Y and Y+X are two different
ways of expressing the sum.

The number 997920 can be expressed as the sum of two abundant numbers
in 234159 different ways.  This is the maximum over all integers < 10^6.
This is a little surprising, as there are only 247543 abundant numbers < 10^6
(and only 247023 abundant numbers < 997920).

Determining that 997920 yields the maximum of 234159 required checking 999999
through 937884 (there are only 234158 abundant numbers less than 937884).

This was a good way to burn 21 hours of CPU time.

One trick (to make the program run faster) involved recognizing the scarcity
of odd abundant numbers (only about 2000 out of the 247543).  I'll add a
longer note later.

					- Gilbert
221.4HARE::GILBERTWed Feb 20 1985 00:251
The program now runs in under 4 CPU minutes.
221.5CLT::GILBERTJuggler of NoterdomFri Jun 27 1986 05:2044