-----------------------------------

netninja

Thu Oct 14, 2004 7:43 pm


Perfect number contest. (i guess)

-----------------------------------

Im trying to find newer ways to find perfect numbers more efficiently. Im currently applying my knowledge from the prime number topic from a while back. I know this is useless, but its pretty cool. SO ya, anyway. Everyone post your new and improved method of finding perfect numbers.

By the way, if someone doesnt know what a perfect number is, its a number that is the sum of its own factors excluding itself. Not the number one tho. so for eg.  6 = perfect because 1+2+3 = 6

Whoever designs the most efficient program will get some of my bits and gratitude for sharing their knowledge.

Ill start by posting my own, as soon as i write them (gtg sleep, but tommorow wont take more than and hour) I will also include the simplest one that most people come up with first.

Good night, and good luck :D


-----------------------------------

wtd

Thu Oct 14, 2004 8:40 pm



-----------------------------------

In standard C.  Finds all perfect numbers upto and including the next perfect number after the number you input.

#include 
#include 
#include 
#include 

bool is_prime(uint64_t number)
{
	for (uint64_t factor = 2; factor = 3)
		{
			uint64_t perfect_number = sum * current_power;

			if (perfect_number > high)
				break;

			printf("%lld\n", perfect_number);
		}
	}

	return 0;
}


And a translation into Ada95:

with Ada.Text_IO, Ada.Integer_Text_IO;
use Ada.Text_IO, Ada.Integer_Text_IO;
procedure Perfect_Numbers is
	function Is_Prime(Number : in Integer) return Boolean is
		Factor : Integer := 2;
	begin
		while Factor  High then
					exit;
				elsif Sum >= 3 then
					Put(Perfect_Number);
					New_Line;
				end if;
			end if;

			Power := Power + 1;
		end;
	end loop;
end Perfect_Numbers;


-----------------------------------

Brightguy

Thu Oct 14, 2004 10:52 pm


Re: Perfect number contest. (i guess)

-----------------------------------

It is worth pointing out that the above algorithm will only generate all even perfect numbers, not odd ones (if there happen to be any).

Of course since they would have to be so big, this method works perfect 8) for all reasonable inputs.


-----------------------------------

wtd

Thu Oct 14, 2004 11:37 pm



-----------------------------------

Unless I'm mistaken, all perfect numbers are even.  :)

Basically:

1 + 2 = 3 : 3 is prime : 3 * 2 = 6
1 + 2 + 4 = 7 : 7 is prime : 7 * 4 = 28
1 + 2 + 4 + 8 = 15 : 15 is not prime : no perfect number
1 + 2 + 4 + 8 + 16 = 31 : 31 is prime : 31 * 16 = 496
1 + 2 + 4 + 8 + 16 + 32 = 63 : 63 is not prime : no perfect number

The first three perfect numbers are: 6, 28, 496


-----------------------------------

Brightguy

Fri Oct 15, 2004 9:33 am


Re: Perfect number contest. (i guess)

-----------------------------------

It seems logical that all perfect numbers are even (currently all 41 known perfect numbers are even) but in fact it hasn't been proven.  It's been shown that if an odd perfect number does exist, it must be at least 300 digits long.  More info can be found [url=http://mathworld.wolfram.com/OddPerfectNumber.html]here.


-----------------------------------

netninja

Fri Oct 15, 2004 11:50 am



-----------------------------------

now i just feel stupid...

I thought i was posting in the turing section, wow, im a moron. :lol:

Anyway, my knowledge of C extends far enough to understand what you have here. So i guess its a bonus. But my original intention was for turing, one reason behind choosing the turing language is because im taking a turing class, and i intend to get a high mark (which Im already getting), taking some knowledge from this into future programs. For the most part, I chose to make this thread because i was interested in people introducing good efficiency in writing programs, and my original curiosity was aroused by the turing prime number question.

Anyways, thanks.


-----------------------------------

Brightguy

Fri Oct 15, 2004 1:01 pm


Re: Perfect number contest. (i guess)

-----------------------------------

Woah... one of my professors was mentioned in that page on odd perfect numbers. :shock: Apparently he recently proved that an odd perfect number must have 47 or more prime factors.

Anyway, thinking back to Turing now... here's the same basic solution:
function isprime (n : int) : boolean
    for a : 2 .. floor (sqrt (n))
        if n mod a = 0 then
            result false
        end if
    end for
    result true
end isprime

for p : 2 .. 16
    var mersenne : int := 2 ** p - 1

    if isprime (mersenne) then
        put mersenne * 2 ** (p - 1)
    end if
end for
That checks all mersenne numbers up to M16, after that Turing has an integer overflow.


-----------------------------------

netninja

Mon Oct 18, 2004 5:23 pm



-----------------------------------

I guess i dont have to post that anymore. Anybody have any other solutions that are more efficient? Im working on one right now, ill post it as soon as i find time. Otherwise, the simplest one will win the bit prize.