11SSTEIN%GALLUA.BITNET@wiscvm.wisc.EDU (10/07/87)
I am working on a perfect number program and I have faced some problems.
Notice: A perfect number is a number that has its divisors add up to itself.
I.E. 6 = 1 + 2 + 3 = 6
28 = 1 + 2 + 4 + 7 + 14 = 28
All that... you have an idea on a good program?
I tried mine and it takes TOO long. I used this program:
FOR I=2 TO 10000 DO
FOR K=2 TO I DO
IF I/K = TRUNC (I/K) THEN W=W+(I/K)
IF W=I THEN PRINT W "IS A PERFECT NUMBER"
Forgot to add between 1st and 2nd line:
W=0
Any ideas?crobbins@Cs.Ucl.AC.UK (Colin J Robbins) (10/07/87)
For a start you could remove 2 of the divides in the inner loop like thus:
FOR I=2 TO 10000 DO
BEGIN
W = 0;
D = I/K;
FOR K=2 TO I DO
IF D = TRUNC (D) THEN W=W+(D)
IF W=I THEN PRINT W "IS A PERFECT NUMBER"
END
This should have approximately a 3 fold increse in speed.
Secondly, you could write a more inteligent routin altogether that
take account of the factors tried before, for example, if 2 was not
a factor then it is pointless trying 4,6,8 etc to see if the are
factors.
The routine for this - left as an exercise for the reader !!!
Colin Robbins
University College, London
England.silva@tcgould.TN.CORNELL.EDU (Victor M. Silva) (10/07/87)
You can reduce your processing time in half by just having your inner
loop (FOR K=2 TO I...) only go to I/2 since anything larger cannot be
a divisor (ie. 2*(I+1) > I ).
-VMS-jkr@pyr.gatech.EDU (J. Kenneth Riviere (JoKeR)) (10/07/87)
In article <9652@brl-adm.ARPA> 11SSTEIN%GALLUA.BITNET@wiscvm.wisc.EDU writes: > I am working on a perfect number program and I have faced some problems. > I tried mine and it takes TOO long. I used this program: > > FOR I=2 TO 10000 DO > W=0 > FOR K=2 TO I DO > IF I/K = TRUNC (I/K) THEN W=W+(I/K) > IF W=I THEN PRINT W "IS A PERFECT NUMBER" > First of all, when you discover a divisor of I you have also discovered another divisor of I (when you find that 2 is a divisor of 28 it is clear that 28/2 means that 14 is also a divisor of 28). Thus you should be able to increment W by both K and I/K when your test is true. Furthermore, since you are checking both K and I/K it is not necessary for your inner loop to progress past the square root of I since you will only rediscover the same divisors from the other side (you would eventually find 14 again, but with my approach you shouldn't need to loop past 5 to find divisors for 28). Hope this helps. J. Kenneth Riviere (JoKeR) ISA, Georgia Tech, Atlanta, GA 30332 Internet: jkr@pyr.gatech.edu Bitnet: iadt1kr@gitvm1 uucp: ...!{decvax,linus,rutgers,ihnp4,hplabs,seismo}!gatech!gitpyr!jkr
victor@cs.vu.nl (L. Victor Allis) (10/07/87)
In article <9652@brl-adm.ARPA> 11SSTEIN%GALLUA.BITNET@wiscvm.wisc.EDU writes: > > > I am working on a perfect number program and I have faced some problems. > > Notice: A perfect number is a number that has its divisors add up to itself. > I.E. 6 = 1 + 2 + 3 = 6 > 28 = 1 + 2 + 4 + 7 + 14 = 28 > > All that... you have an idea on a good program? > > Any ideas? It is well known that every even perfect number must be of the form 2^(p-1) * (2^p - 1), where 2^p -1 is prime. Since there are only a little over 30 known primes of the form 2^p - 1, there are only 30 known perfect numbers. There are no odd perfect numbers found so far, neither is proven that none exist. This gives the following suggestions: 1) Find a recent article on Mersenne primes (2^p -1), and make a list of the perfect numbers these primes produce. This gives a very fast program. 2) Start looking for odd perfect numbers. This probably will not produce any perfect numbers, but could make you famous if you find one. 3) If you just want search for perfect numbers between, say, 1 and 100000, for fun, you could try something like the following: -------------- program Perfect(input, output); const Max = 100000; var Numbers : array[1..Max] of integer; i, j : integer; begin for i := 2 to Max do Numbers[i] := 1; for i := 2 to Max do for j := 2 to Max div i do Numbers[i*j] := Numbers[i*j] + i; for i := 1 to Max do if Numbers[i] = i then writeln(i:1, ' is a perfect number.') end. -------------- This program produced all perfect numbers between 1 and 100000 in 64 sec. on our VAX-11/70 Its complexity is O(n*logn). I hope this helped. Victor Allis. Free University of Amsterdam. The Netherlands.
jws@hpcllf.HP.COM (John Stafford x75743) (10/07/87)
Well it is bound to be slow; perfect numbers are rather scarce.
The first four are 6, 28, 496, and 8128.
It has been a while since I played with them, but I seem to recall
(although I may well be wrong) that:
1. That they have a tendency, for a while, to end alternately with
the digits 6 and 28, but not forever.
2. There is a formula involving two raised to prime powers that will
generate them for a while, but not forever. I discovered this
formula myself only to later discover I was several hundred years
too late. For a clue, look at the binary representation of the
first four perfect numbers (110, 11100, 111110000, 1111111000000).
3. You might look into Marsienne (spelling?) primes. I believe that
each one of them has a related perfect number that is relatively
easy to compute (assuming you have an easy way to compute the
primes :-{)}).
4. The greeks decided that some numbers are perfect. Numbers whose
prime factors add to less than themselves are 'insufficient' and
those whose add to more than themselves are 'oversufficient', only
a relative few are 'perfect' (or something to that effect).
John Stafford -- Hewlett Packard Computer Language Lab
{allegra,decvax,ihnp4,ucbvax}!hplabs!hpclla!jws
{fortune,sun,thirdi,ucbvax} !hpda !hpclla!jwsgrimlok@hubcap.UUCP (Mike Percy) (10/08/87)
in article <9662@brl-adm.ARPA>, silva@tcgould.TN.CORNELL.EDU (Victor M. Silva) says: > > You can reduce your processing time in half by just having your inner > loop (FOR K=2 TO I...) only go to I/2 since anything larger cannot be > a divisor (ie. 2*(I+1) > I ). > Actually, you only have to go to sqrt(i), since anything above sqrt(i) will have already been discovered as "the other factor" in a factor pair. I seem to remember doing this a while back...where did I put that cocktail napkin...
kishore2@watdcsu.UUCP (10/08/87)
In article <9662@brl-adm.ARPA> silva@tcgould.TN.CORNELL.EDU (Victor M. Silva) writes: >You can reduce your processing time in half by just having your inner >loop (FOR K=2 TO I...) only go to I/2 since anything larger cannot be >a divisor (ie. 2*(I+1) > I ). > -VMS- And you can reduce it further by going to trunc(sqrt(i)) instead. The other thing to do is to keep track of factors and to go backwards in your testing of k. -- ============================================================================= | Sherman Lang, Systems Design Engineering, University of Waterloo. | | "A screaming comes across the sky..." | =============================================================================
brianc@cognos.uucp (Brian Campbell) (10/13/87)
In article <9652@brl-adm.ARPA> 11SSTEIN%GALLUA.BITNET@wiscvm.wisc.EDU writes:
!
! I am working on a perfect number program and I have faced some problems.
!
! Notice: A perfect number is a number that has its divisors add up to itself.
! I.E. 6 = 1 + 2 + 3 = 6
! 28 = 1 + 2 + 4 + 7 + 14 = 28
!
! All that... you have an idea on a good program?
I'm not sure whether your program is supposed to generate ALL perfect
numbers or not. Nor am I sure the following produces all of the perfect
numbers. Anyway, I remember some math text that listed the theory (?) that
if:
(2 ^ n) - 1 is prime, then
[(2 ^ n) - 1] * (2 ^ [n - 1]) is perfect
Hope this helps...
--
Brian Campbell uucp: decvax!utzoo!dciem!nrcaer!cognos!brianc
Cognos Incorporated mail: POB 9707, 3755 Riverside Drive, Ottawa, K1G 3Z4
(613) 738-1440 fido: sysop@163/8