music 
OSdata.com 
amicable numbers
summary
This subchapter looks at amicable numbers.
free computer programming text book projecttable of contents

music 
OSdata.com 
This subchapter looks at amicable numbers.
free computer programming text book projecttable of contents

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. NeoPlatonic philosopher Iamblichus of Chalcis attributed the discovery of this pair to Pythagoras, although they were discovered much earlier. The Arab scholar Ibn Khaldun (13321406) reported on this pair in his work Historical Prolegomenon.
Amicable numbers played an important role in mysticism and numerology.
The Arab mathematician AbuIHasan 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:
p_{n} = 3 · 2^{n}  1
This formula produces the following sequence of numbers:
n  1  2  3  4  5  6  7 
p_{n}  5  11  23  47  95  191  383 
If for some n you find that two successive terms p_{n1} and p_{n} are both prime numbers, test the number:
q_{n = 9 · 22n1 1}
If this number is also a prime, then you can produce a pair of amicable numbers by the formulas:
M = 2^{n}p_{n1}p_{n} N = 2^{n}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:
/* 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 p_{n} happens to be double the previous p_{n1} plus one.
p_{n} = 2(p_{n1})+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.
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 frontend 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
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 
Tweets by @osdata 
free computer programming text book projectBuilding 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, 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) free downloadable college text book on computer programming. 
This web site handcrafted on Macintosh computers using Tom Bender’s TexEdit Plus and served using FreeBSD .
†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 