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.