THE PUZZLET PAGE


How_Does_It_Work


FUNCTION:  IsAbundant().  An Abundant Number is one for which the sum of its proper divisors is greater than the number itself. The proper divisors are those integers which divide into the number, which includes 1 but excludes the number itself.

Example: 12's proper divisors are 1, 2, 3, 4, 6. These add up to 16, which is greater than 12, so 12 is Abundant.

When an integer is passed to IsAbundant(), the function checks its Abundancy. If it's Abundant, TRUE (-1) is returned, otherwise FALSE (0).

It's up to you what kind of integer you pass to the function, as long as the function declaration has already taken this data-typing into account. See the table below for the parameter limits.

Type

Exponent of 2
Value

int 230 1073741824
uint 231 2147483648
int64 261 2305843009213693952
uint64 262 4611686018427387904

Declaring the function must be done like this:

declare IsOddAbundant(a: int) (or whatever integer type you want).

Here's the code:


sub IsAbundant(a)
' If argument a is an abundant number,
' returns TRUE (-1), otherwise returns
' FALSE (0).
' By Dave Ellis.

def dvsr, flag, max, tot: int
if a < 12: 'too small
    flag = 0: 'return false
else: 'argument >= 12
    dvsr = 3: 'least divisor
    max = a/3: 'max search range
    if a % 2 = 0: 'even number
        tot = 3 + a/2: 'initialise
    else: 'odd number
 
      tot = 1: 'alternative init 
    endif
    do
        if a % dvsr = 0: 'divisor?
            tot = tot + dvsr: 'yes
        endif
        dvsr = dvsr + 1: 'get next divisor
    until dvsr > max: 'exceeded range
    if tot > a: 'sum of divs > argument
        flag = -1: 'return TRUE
    else: 'sum of divs <= argument
        flag = 0: 'return FALSE
    endif

endif
return flag

Overview:  The function opens by checking that its argument isn't less than 12, the smallest possible Abundant number.  Assuming it's 12 or greater, the appropriate values for the start of the search range are initialised in variable dvsr and the maximum point is initialised in variable max.  The values of the proper divisors will be totalised in variable tot, and this is also initialised.

The code now works through the range established above, checking each number to see if it divides exactly into argument a.  If it does, its value is totalised into tot.

At the end of the search, the value now stored in variable tot is compared with the value stored in argument a.  If it's greater, an Abundant number has been found, and TRUE (-1) is returned to the calling routine, otherwise FALSE (0).


To make it simpler to follow a detailed code description, I've numbered the lines as shown below.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

if a < 12: 'too small
    flag = 0: 'return false
else: 'argument >= 12
    dvsr = 3: 'least divisor
    max = a/3: 'max search range
    if a % 2 = 0: 'even number
        tot = 3 + a/2: 'initialise
    else: 'odd number
 
      tot = 1: 'alternative init 
    endif
    do
        if a % dvsr = 0: 'divisor?
            tot = tot + dvsr: 'yes
        endif
        dvsr = dvsr + 1: 'get next divisor
    until dvsr > max: 'exceeded range
    if tot > a: 'sum of divs > argument
        flag = -1: 'return TRUE
    else: 'sum of divs <= argument
        flag = 0: 'return FALSE
    endif

endif
return flag

Now for a line-by-line exegesis of the code.

1

if a < 12.  Variable a holds the function's argument, the value to be checked for Abundance.  The smallest Abundant number is 12, so there's no point in checking values 1 to 11.  Line 1's job is to weed them out.  So it's asking the question "Is the value stored in argument a less than 12?"

2

flag = 0.  Line 2 is only executed if the answer to the question in line 1 is "Yes," which means the function's argument is less than 12 and cannot therefore possibly be an Abundant number.  Variable flag is set to FALSE (0) so that the program will be able to quit immediately without any further checking at all. It jumps immediately to line 23 and returns the FALSE to the calling routine.

3

else.  Indicates that there is an alternative action if the answer to the question in line 1 was "No."  In fact, the rest of the code is the alternative action, and that is executed now.

4

dvsr = 3The value in variable dvsr, which holds test divisors, is initialised to 3.  It is the lowest possible value divisor for odd numbers.  It is the second lowest for even numbers, but that's taken care of in lines 6 and 7 if it's established the argument is even.  The explanation is given for them below.

5

max = a/3 The value of variable max, which holds the highest value used when testing divisors, is initialised now to a/3.  This is correct for odd numbers, but too low for even numbers (whose divisors should range up to a/3).  This is taken care of in lines 6 and 7 if it's established the argument is even.  The explanation is given for them below.

6

if a % 2 = 0 The code now goes on to decide whether argument a is even or odd, using integer arithmetic.  The % sign indicates that the code is to look only at the remainder of the operation.  So it can be paraphrased as "Is the remainder when the value stored in argument a is divided by 2 equal to zero?"  In other words, does a divide exactly by 2 without remainder?

7

tot = 3 + a/2.  Line 7 is only executed if the answer to the question in line 6 is "Yes."  This means that the value of argument a is even, and the variable tot, which holds the running total of the argument's proper divisors, is initialised to 3 + a/2.  This total comprises the following:

1
All numbers have proper divisor 1.
2
All even numbers have proper divisor 2.
a/2
All even numbers have proper divisor number/2.

Now you can see why even odd numbers can start the search range at 3 - divisors 1 and 2 have already been added to tot.  Also, it should now be clear why, even for odd numbers, the maximum search range is a/3: the divisor at a/2 has already been added to tot.

8

else.  Indicates there is an alternative action if the answer to the question in line 6 is "No," which means that the argument a is an odd number.

9

tot = 1.  And this is the alternative action described in line 8 above.  Beacuse argument a is an odd number, variable tot, which holds the totalised value of all a's proper divisors, can only be initialised to 1.  No other proper divisors can be inferred and totalised at this stage.

10

endif.  Housekeeping - closes if-endif clause opened in line 6.

11

do.  Opens the main do-until loop.  This is only a few lines long, but it's where all the important work of the function is carried out.

12

if a % dvsr = 0.  Line 12 works just like line 6.  It uses integer arithmetic to find out if the value of argument a can be divided exactly be the value currently stored in variable dvsr.  It's posing a question:  "Is the value stored in a exactly divisible by the value stored in dvsr, so that value is a proper divisor of a?"

13

tot = tot + dvsrLine 13 is only executed if the answer to the question in line 12 is "Yes," which means a proper divisor of argument a has been found.  That value is added to tot, so line 13 can be paraphrased as "add the value stored in variable tot to the value stored in variable dvsr and store their sum in variable tot, over-writing whatever was already stored in there."

14

endif.  Housekeeping - closes if-endif clause opened in line 12.
  
15

dvsr = dvsr + 1.  The code has dealt with the current value stored in variable dvsr and is now ready to work on another value.  The value stored in variable dvsr is incremented by accordingly.

16

until dvsr > maxThe program has reached the end of the do-until loop at this point.  It has to make a decision: execute it again, or move on?  The value in variable dvsr has been continually incremented; eventually, it will be greater than that stored in variable max, which, you will remember is the value set for the finish of the search.  So, line 16 says "If the value stored in variable dvsr is now greater than that stored in variable max quit the do-until loop, otherwise execute it again."

17

if tot > a.  Now the function has completed its work.  All that remains is to sort out what the answer is, put it into a suitable format, and return it to the calling routine.  Line 7 asks "Is the value stored in variable tot greater than that of argument a?"

18

flag = -1  If the answer to line 17's question is "Yes," argument a is an Abundant number, and variable flag is set accordingly to TRUE (-1).

19

elseIndicates there is an alternative action if the answer to the question in line 17 is "No," which means that the argument a is not an Abundant number.

20

flag = 0.  An Abundant number hasn't been found, so variable flag is set to FALSE (0) to record this fact.

21

endif.  Housekeeping - closes if-endif clause opened in line 17.

22

endif.  Housekeeping - closes if-endif clause opened in line 1

23

return flag.  The function has concluded.  Whatever the value stored in variable flag, whether FALSE or TRUE, it is returned to the calling routine.


MAIN MENU
HOW DOES IT WORK?

Site design/maintenance: Dave Ellis E-mail me!
Last Updated: Febuary 1st, 2010.