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 |
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.R | Title | User | Personal Name | Date | Lines |
---|---|---|---|---|---|
221.1 | METOO::TOOLSHED | Tue Feb 12 1985 16:23 | 5 | ||
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.2 | TURTLE::GILBERT | Fri Feb 15 1985 22:24 | 7 | ||
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.3 | TURTLE::GILBERT | Sun Feb 17 1985 07:35 | 18 | ||
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.4 | HARE::GILBERT | Wed Feb 20 1985 00:25 | 1 | ||
The program now runs in under 4 CPU minutes. | |||||
221.5 | CLT::GILBERT | Juggler of Noterdom | Fri Jun 27 1986 05:20 | 44 |