Perfect Number AlgorithmDate: 10/24/2001 at 00:34:29 From: Cristopher Wick Subject: An algorithm for testing a number to see if it is perfect. I'm having a smidge of trouble creating an algorithm to test whether or not a number is a Perfect Number. I'm trying to find one that would be easily translatable into C++ code. Do you have an algorithim that might help? Date: 10/24/2001 at 12:06:08 From: Doctor Paul Subject: Re: An algorithm for testing a number to see if it is perfect. There are really two approaches you can take here. The first is easy, but it is probably not what your teacher had in mind if this is for a class assignment. There are only 38 perfect numbers known. Program them into an array and then input the number to be checked. Just run a for loop from 1 to the length of the array that checks each entry in the array against the number to be checked. The computer should take about 2 seconds to decide whether or not your number is perfect. :-) If you want to do it this way, you should be asking, "What are the known perfect numbers?" First a digression: A Mersenne prime is a number of the form 2^p - 1 that is prime. For example, 2^3 - 1 = 7. So 7 is a Mersenne prime. 2^p - 1 will never be prime if p is not prime. So you only need to check prime exponents. But not all prime exponents produce Mersenne primes. For example, 2^11 - 1 = 2047 = 23 * 89. Mersenne primes and perfect numbers are intimitely related: If k = 2^p - 1 is a Mersenne prime, then: k * 2^(p-1) is perfect. So the search for perfect numbers has been relegated to the search for Mersenne primes. Thus far, 38 Mersenne primes have been found. The Great Internet Mersenne Prime Search (GIMPS) Project is ongoing: http://mersenne.org/ . GIMPS has found the last 4 Mersenne Primes. You can get a list of them here: http://www.utm.edu/research/primes/mersenne.shtml The current world record prime is the 38th Mersenne prime: 2^6972593 - 1 has 2,098,960 digits. The perfect number will be even larger. So maybe your array won't be able to hold such a large number. This is probably the case. But the other method (described below) requires you to factor this large number. Your routine probably won't be able to do that either! The other method would be as follows: Write an algorithm that produces the factors of the integer to be tested and then add them up and compare to the integer to be tested. For example: To verify that 28 is perfect, your program woudld produce the factors of 28: [1,2,4,7,14,28], and then sum all except the last one to obtain 28, which proves that 28 is perfect. Factoring algorithms are hard to come by and our inability to factor large integers has led to much of the security of Internet transactions (see RSA Security, http://rsasecurity.com/ ). If you use Netscape, type "about:" in the address window (where you normally type http://www... ) and you'll see that RSA Security provides encryption mechanisms used in Netscape. The RSA encryption algorithm would not be secure if we could quickly factor large integers. But for "small" numbers, you should be able to write a primitive factoring algorithm as follows: First notice that the factors of a number come in pairs; for example: the factors of 48 are: [1,2,3,4,6,8,12,16,24,48] But we can view them this way: [ {1,48}, {2,24}, {3,16}, {4,12}, {6,8} ] So if I know that 6 is a factor, I can find out that 8 goes with it by dividing 6 into 48. The smaller factor in each pair of factors must occur before floor(sqrt(48)) So run a for loop for i from 2 to floor(sqrt(n)) and check to see if each i divides n evenly. You can use the mod operator (% I think) to test divisibility. For example: 3 divides 48 so 48 % 3 will give 0. Whenever n % i is zero, you have found a factor. Once you have found a factor, place it in an array. Then right next to it, place its pair - n/i So if you did this for n = 48, your array would be: [1,48,2,24,3,16,4,12,6,8] Now sort this array in increasing order to obtain: [1,2,3,4,6,8,12,16,24,48] Call this array A. and now add all but the last entry: for p from 1 to length(A)-1 value = value + A[p] When done, if value = n then n is perfect. This algorithm works well for relatively small numbers. Notice that to find all of the factors of 1,000,000 (and hence test whether or not 1,000,000 is perfect) it only has to test up to floor(sqrt(1,000,000)) = 1000. I wrote a similar routine for my TI-86 Graphing Calculator. It can tell me the sum of the factors of 100,000, not counting 100,000 of course, in less than 20 seconds (the answer is 146,078). Certainly a c++ routine should be able to do it almost instantaneously. Feel free to write back if you'd like to talk about this some more or if you have questions about what I've written above. - Doctor Paul, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/