If this number is also a prime, then you can produce a pair of amicable numbers by the formulas:

M = 2ⁿp_n-1p_n      N = 2ⁿq_n

    Fermat used this sequence in 1636 to generate the pair of amicable numbers (17,296 and 18,416). Descartes used this sequence in 1638 to find the pair (9,363,584 and 9,437,056). Euler created additional methods and published a list of 30 new amicable number pairs in 1747, and later expanded his discoveries to more than 60 pairs.

    At the moment we wont get into how to write a prorgam to determine if a number is prime and only assume that we are generating the sequence of numbers. If we immediately jumped into coding, we might write:

C

    Because anything that is repeated inside a loop (especially an innermost loop) is going to take a lot of computer time (especially when the loop is repeated a large number of times), it is very valuable to discover patterns that reduce the amount of work the computer performs inside a loop.

    If we look a little closer at the pattern in the table of the first seven results (above), we will notice that there is an additional pattern.

    Each p_n happens to be double the previous p_n-1 plus one.

p_n = 2(p_n-1)+1

    This is a pattern that an optimizing compiler is extremely unlikely to notice, but a pattern that a human being can think of and use.

    Our revised program would now be:

    We have changed the inner loop from one multiplication, one exponentiation, and one subtraction to one multiplciation and one addition. Further, exponentiation is very expensive in computer processing time, especially as the exponent increases (unless the exponentiation is doen by hardware). Also, the multiplication is a doubling and binary dooubling can be performed via a simple shift operation on an integer (until the numbers become large enough to require floating point arithmetic.