PERFECT NUMBERS AND PRIME NUMBERS by K2K (Peter Davy) I was interested in Graham Gallagher's piece and two programs in the No.35 8-BS magazine disk as I have written two programs called FUN WITH FACTORS and FUN WITH PRIME NUMBERS (Available on TBI-46-3). Graham's prime number generation program can be speeded up by making the following changes: Change line no.110 to M=M+2 Change line no.120 to IF M>SQR(A) THEN 160 Ideally when testing a number to see if it is a prime, we would try dividing into it just the prime numbers, i.e. 2, 3, 5, 11, 13, 17, 19, etc. Unfortunately we don't have the prime numbers available but once we have reached the divisor of 3 we can be sure that every prime number is tried by using just the odd numbers, i.e. by incrementing our divisor by 2 each time. Once our divisor has reached or exceeded the square root of the number being tested without a whole number answer being found, the number is a prime. There is no need to go any further. Think about it! Graham's original program takes 4min 40sec to generate the primes less than 1000. With the above changes the time is reduced to 28sec. Elsewhere on this disk you will find two programs PERFT2 and GPERFN3. PERFT2 This program is to test any given number to see whether it is perfect, deficient or excessive. A number is perfect if the sum of all its factors including unity but excluding the number itself is equal to the number. If a number is deficient the sum of its factors is less than the number. If a number is excessive the sum of its factors is more than the number. PERFT2 works by trying to divide the test number by 1, 2, 3, 4, 5, 6 etc. and keeping a running total of any which are found to be exact divisors. Each time an exact divisor is found, cognizance is taken of the other exact divisor being found at the same time e.g. if the test number is 2050 it will be found to be exactly divisible by 5 and the other factor found at the same time is 2050/5 = 410. This enables the process to be halted once the divisor has exceeded the square root of the test number. Line nos. 90 and 95 ensure that the "other" exact divisor is ignored if the divisor is unity (because we don't want to include the whole test number) or the test number happens to be a perfect square and the divisor is its square root. We don't want to include the square root twice. It takes my M-128 just 1min 55sec to confirm that the number 33550336 is perfect. GPERFN3 This program follows Graham's suggestion of assuming that all perfect numbers are of the form: 2 to the power(n-1) times (2 to the power n - 1) where n is a whole number and 2 to the power n - 1 is a prime. I found that things boiled down to a remarkably simple operation which produces the first seven perfect numbers in about 8sec ! This is what the program does: Start with q% and rt% each equal to 1 (line 20). Repeatedly double q% and keep a running total rt%. q% rt% 1 1 2 3 is prime. 2x3=6 is perfect 4 7 is prime. 4x7=28 is perfect 8 15 16 31 is prime. 16x31=496 is perfect 32 63 64 127 is prime. 64x127=8128 is perfect 128 255 256 511 512 1023 . . . . . . 4096 8191 is prime. 4096x8191=3355036 is perfect and so on. Each value of rt% is tested to see if it is a prime and if it is, another perfect number equal to the product of q% and rt% has been found. The next perfect number found is given by 65536x131071 and equals 8589869056. The last perfect number found is given by 262144x52487 and equals 137438691328. For these last two results the answers are too big to be given precisely by the computer's in- built facilities so I have incorporated PROCfermat to carry out the final multiplication. See magazine disk no.35 under PALINDROMIC NUMBERS for what PROCfermat does and where it came from. The first 7 perfect numbers are on the screen in about 8 seconds. The program carries on running for a total of about 3 minutes. This is until rt% reaches 999999999, the limit for the computer to hold precisely. No more perfect numbers are found up to that point. When the program stops, type PRINT q%*rt% and press RETURN. You will get the answer 5.76460752E17 which means that the next perfect number is greater than 576460752000000000 ! Thank you Graham for raising this interesting topic.