THE PUZZLET PAGE


How_Does_It_Work


FUNCTION:  IsAchillesNr().  An Achilles number is a non-square integer whose prime factors each occur at least twice.   Here are some examples to clarify things:

NumberSquarePrime FactorsAchillesNrComments
28no2 ,2, 7noPF(7) only occurs once
36yes2, 2, 3, 3nosquare
750no2, 3, 5, 5, 5noPF(2) and PF(3) only occur once each
108no2, 2, 3, 3, 3yesnot a square and all PF's occur at least twice each

This function will process its argument and return TRUE (-1) if it's an Achilles number and FALSE (0) otherwise.

This code will only work correctly for integers. See the table below for the 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 IsAchillesNr(a: int) (or whatever integer type you want).

Here's the code:

sub IsAchillesNr(a)
' If argument a is prime, square, or  the power
' of some smaller integer, returns TRUE (-1),
' otherwise returns FALSE (0).
' By Dave Ellis.

' First, a sanity check:
if IsAPower(a) | IsASquare(a) | IsPrime(a)
    return 0
endif

' Local declarations and Initialisations:
def count, fctr, flag: int
def rmndr: int
flag = 1
fctr = 1

' Main routine of function
do
    fctr = GetNextPrime(fctr): 'get a factor
    count = 0
    do
        rmndr = a % fctr
        if rmndr = 0: 'is it a factor?
            count = count + 1
            a = a/fctr
        endif
    until (rmndr > 0) | (a = 1)
    if (a = 1): 'was it completely factored?
        select 1
            case (count > 1)
                flag = -1
            case (count = 1)
                flag = 0
        endselect
    else: 'not completely factored
        if count = 1
            flag = 0
        endif
    endif
until flag < 1
return flag
 

Let's look at the variables before we begin on the code detail.

a is the variable which has been submitted by the calling routine, that is, the argument. It's asking the question "Is a an Achilles number?" and expects one of two replies: TRUE (-1) or FALSE (0).

Variable count is used to count the number of factors which are the same as each other.  So, when dealing with 500, for example, count will reach 2 (two 2's) and 3 (three 5's).  It can of course, be less!

Variable fctr is used to store the value of prime factor to be tested with a at any particular time.

Variable flag is used to store the result of the test.  It holds value 1 when tests are not yet completed, 0 when argument a  isn't an Achilles number, and -1 when it is.

Variable rmndr is used to store the value of any remainder when the argument a is divided by the prime factor being currently investigated.

This function makes use of another of my library functions, GetNextPrime().  You must therefore include it whenever you use IsAchillesNr().  It finds the next prime greater than its argument (the variable passed to it) and returns the same to the calling routine.  If you would like a detailed description of how this function works, just click here now.

Note that the function opens with a "sanity check."  If you unintentionally pass an integer to it which is obviously not an Achilles number, this is caught immediately and, before wasting time on needless tests, FALSE (0) is passed immediately back to the calling routine.  If the argument is the power of some smaller integer, or it's a square or a prime number, it will be trapped.  The failure conditions are caught by the following lines:

if IsAPower(a) | IsASquare(a) | IsPrime(a)
    return 0
endif


Consequently, you must include these functions whenever you use IsAchillesNr().  All included functions can be examined as follows:

FunctionLink
GetNextPrime()click here
IsAPower()click here
IsASquare()click here
IsPrime()click here

There is one happy efficiency here:  GetNextPrime() calls IsPrime(), so it would need to be included anyway!

To make it simpler to follow detailed code description, I've number 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
24

' Main routine of function
do
    fctr = GetNextPrime(fctr): 'get a factor
    count = 0
    do
        rmndr = a % fctr
        if rmndr = 0: 'is it a factor?
            count = count + 1
            a = a/fctr
        endif
    until (rmndr > 0) | (a = 1)
    if (a = 1): 'was it completely factored?
        select 1
            case (count > 1)
                flag = -1
            case (count = 1)
                flag = 0
        endselect
    else: 'not completely factored
        if count = 1
            flag = 0
        endif
    endif
until flag < 1
return flag

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

1

do. Opens the main (outer) do-until loop.  It is concerned with obtaining successive prime factors to try out with the argument.

2

fctr = GetNextPrime(fctr). The code passes whatever value is stored in variable fctr to the function GetNextPrime().  The smallest prime whose value is greater than fctr will be returned and stored in fctr, over-writing whatever was already stored in there.

3

count = 0. In line 2 the code obtained a prime factor to try out with the function's argument. Since we are vitally concerned with the number of times each prime factor occurs in any given argument,  a tally must be kept.  It's stored in variable count, so this is initialised here to zero ready to begin checking.

4

do. Opens the inner, nested do-until loop.  This is concerned solely with trying out the latest prime factor with the argument: testing to see if it divides at all, and, if so, how many times.

5

rmndr = a % fctr.  Line 5 begins the process of factorisation.  It uses integer arithmetic to do so -  in this case, integer division.  The % sign causes the division of one integer by another, with any remainder being kept and the rest discarded.  So the instruction can be paraphrased as "Divide the value stored in argument a by the value stored in variable fctr and save any remainder in fctr, over-writing whatever was already stored in there."

6

if rmndr = 0. This line is asking a question: "Is the value stored in variable rmndr equal to zero?"  In the context of line 5, it could be simplified to "Is fctr a factor of argument a"

7

count = count + 1.  If the integer division in line 5 produced no remainder, the contents of variable fctr must have been a factor of argument a, so this fact needs to be recorded.  The function is particularly looking at how many times prime factors occur, and a tally is being kept in variable count.  Line 7 is only executed if the answer to the question in line 6 was "Yes," so a factor has been found.  The value in variable count is accordingly incremented by 1.

8

a = a/fctr.  Now that a factor of the argument has been found, the code sets about finding out if the same factor can be used again.  To do this, the argument is first divided by the factor.  Line 8 does that.  The instruction means "Divided the contents of argument a by what is stored in variable fctr and save the result back into variable a, over-writing what was already stored there."

9

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

10

until (rmndr > 0) | (a = 1).  The end of the inner do-until loop has been reached.  As always at this point, the program has to decide: execute the loop again, or move on?  Remember, this inner loop is concerned with trying out prime factors with the argument for divisibility.  so the decision will involve that.

If the remainder of the last factor was greater than zero, that factor obviously will not divide into the argument again.  Alternatively, the argument, which is progressively reduced in size as various factors are divided successfully into it, may have reduced as far as possible - unity. In both these cases, it's time to quit the loop, otherwise it can be executed again until one of these two conditions have been met.

So the instruction can be paraphrased as "If the value stored in variable rmnds is greater than zero, or the value stored in argument a equals one, quit the do-until loop, otherwise execute it again."

11

if (a = 1). The code has just exited the inner do-until loop, concerned with factoring the argument.  Its value will have been reduced by the divisions that involves.  Now is the time to find out if it was completely factored, evidenced by the value being reduced to one.  It's put in the form of a question: "Is the value stored in variable a equal to one?"

12

select 1.  The code has just finished its latest prime factorisation of the argument a, and needs to check that there were at least two in number if the number is to qualify as an Achilles number.

To do that it will examine the value stored in variable count.  A select-case clause is used for that.  It would have been equally possible to nest further if-endif clauses, but this method is tidier here.  The command
select 1 simply means "Select one of the following cases."

13

case (count > 1).  Line 13 caters for the case where the value stored in variable count is greater than one, which means that there were at least two of the same prior factor discovered in the last value checked.  The appropriate action follows in line 14.

14

flag = -1. The present status is that the argument has been factored down to value one (from line 11) and that the latest prime factor count is at least two.  The argument must therefore have been an Achilles number, so variable flag is set to value TRUE (-1).  This serves two purposes: firstly, it enables the code to quit the outer do-until loop and exit the function, and secondly it allows the TRUE result to be returned to the calling routine.

15

case (count = 1).  The only other possible value for count is one.  It can't be zero, or the argument would be prime (which would cause the code to terminate way back in the sanity check at the beginning of the function).  And if it's one, the argument can't have been an Achilles number, since that requires at least two of each prime factor.  The appropriate action follows on line 16.

16

flag = 0.   Since the last prime factor only occurred once, the argument cannot have been an Achilles number, so variable flag is set to FALSE (zero).  This will allow the code to exit the outer do-until loop, but will cause a FALSE result to be returned to the calling routine.

17

endselect. Housekeeping - closes the select-endselect clause opened in line 12.

18

else.  If the answer to the question in line 11 was "No" (which means that the argument wasn't completely factored), the code jumps to this line.  It indicates that a suitable alternative action is to follow in line 19.

19

if count = 1.  The code has reached this line because the argument hasn't been completely factored.  It now checks to see if the last prime factor occurred at least twice.  It does so by asking the question "Is the value stored in variable count equal to one"

20

flag = 0.  The argument wasn't completely factored, but the count for the last prime factor occurrences is only one, so this can't be an Achilles number.  Accordingly, variable flag is set to FALSE (0).  This will allow the code to exit the outer do-until loop, but will cause a FALSE result to be returned to the calling routine.

21

endif.  Housekeeping - closes the if-endif clause opened in line 19.

22

endif.  Housekeeping - closes the if-endif clause opened in line 11.

23

until flag < 1. This is the end of the outer do-until loop.  Variable flag was initialised to value 1 at the beginning of the function.  If the routine hasn't finished checking its argument, flag's value will be unchanged, and the loop must be executed again.  If the value has been changed to 0, it means the argument definitely isn't an Achilles number, and the do-until loop is exited. Likewise, if flag's value has been changed to -1, the argument definitely is an Achilles number, and the do-until loop is exited.

24

return flag.  Finally, all that remains is to pass the result of the function's checks back to the calling routine, and line 24 does just that.


MAIN MENU
HOW DOES IT WORK?

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