music
OSdata.com: programming text book 

OSdata.com

amicable numbers

summary

    This subchapter looks at amicable numbers.

free computer programming text book project

table of contents
If you like the idea of this project,
then please donate some money.
more information on donating

Google

amicable numbers

    Amicable numbers are a pair of numbers such that each number is the sum of the divisors of the other number.

    The most famous pair of amicable numbers, discovered in antiquity, are 220 and 284. Neo-Platonic philosopher Iamblichus of Chalcis attributed the discovery of this pair to Pythagoras, although they were discovered much earlier. The Arab scholar Ibn Khaldun (1332-1406) reported on this pair in his work Historical Prolegomenon.

    Amicable numbers played an important role in mysticism and numerology.

    The Arab mathematician Abu-I-Hasan Thabit ben Korrah came up with a formula for discovering additional (but not all) amicable numbers in the ninth century. This method was independently discovered by Fermat.

    Consider the sequence of numbers created by the formula:

pn = 3 · 2n - 1

    This formula produces the following sequence of numbers:

n 1 2 3 4 5 6 7
pn 5 11 23 47 95 191 383

    If for some n you find that two successive terms pn-1 and pn are both prime numbers, test the number:

qn = 9 · 22n-1 -1

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

M = 2npn-1pn      N = 2nqn

    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

    /* limit already set before this loop fragment */
    for (n=1;n=limit;++n)
    {
        p = 3 * 2**n - 1;
        /* print p for human evaluation */
        /* or store p in an array for computer */
        /* or store p for a comparison with previous p */
    }

    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 pn happens to be double the previous pn-1 plus one.

pn = 2(pn-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:

    /* limit already set before this loop fragment */
    /* we prepare the first number in the sequence outside the loop */
        previous = 3 * 2**n - 1;
    for (n=2;n=limit;++n)
    {
        p = previous *2 +1;
        /* print p for human evaluation */
        /* or store p in an array for computer */
        /* or store p for a comparison with previous p */
        previous = p;
        /* update previous */
    }

    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.


free music player coding example

    Coding example: I am making heavily documented and explained open source code for a method to play music for free — almost any song, no subscription fees, no download costs, no advertisements, all completely legal. This is done by building a front-end to YouTube (which checks the copyright permissions for you).

    View music player in action: www.musicinpublic.com/.

    Create your own copy from the original source code/ (presented for learning programming).


return to table of contents
free downloadable college text book

view text book
HTML file

Because I no longer have the computer and software to make PDFs, the book is available as an HTML file, which you can convert into a PDF.

previous page next page
previous page next page

free computer programming text book project

Building a free downloadable text book on computer programming for university, college, community college, and high school classes in computer programming.

If you like the idea of this project,
then please donate some money.

send donations to:
Milo
PO Box 1361
Tustin, California 92781

Supporting the entire project:

    If you have a business or organization that can support the entire cost of this project, please contact Pr Ntr Kmt (my church)

more information on donating

Some or all of the material on this web page appears in the
free downloadable college text book on computer programming.


Google


Made with Macintosh

    This web site handcrafted on Macintosh computers using Tom Bender’s Tex-Edit Plus and served using FreeBSD .

Viewable With Any Browser


    †UNIX used as a generic term unless specifically used as a trademark (such as in the phrase “UNIX certified”). UNIX is a registered trademark in the United States and other countries, licensed exclusively through X/Open Company Ltd.

    Names and logos of various OSs are trademarks of their respective owners.

    Copyright © 2010 Milo

    Created: November 25, 2010

    Last Updated: November 25, 2010


return to table of contents
free downloadable college text book

previous page next page
previous page next page