Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Perfect number contest. (i guess)
Index -> Contests
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
netninja




PostPosted: Thu Oct 14, 2004 7:43 pm   Post subject: 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 Very Happy
Sponsor
Sponsor
Sponsor
sponsor
wtd




PostPosted: Thu Oct 14, 2004 8:40 pm   Post subject: (No subject)

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

code:
#include <stdio.h>
#include <math.h>
#include <stdbool.h>
#include <stdint.h>

bool is_prime(uint64_t number)
{
        for (uint64_t factor = 2; factor <= number / factor; ++factor)
                if (number % factor == 0)
                        return false;

        return true;
}

int main()
{
        uint64_t sum = 0;
        uint64_t high = 0;

        printf("How high should I go? ");
        scanf("%lld", &high);

        for (uint64_t n = 0; ; ++n)
        {
                uint64_t current_power = (uint64_t)pow(2, n);

                sum += current_power;

                if (is_prime(sum) && sum >= 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:

code:
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 <= Number / Factor
                loop
                        if Number mod Factor = 0 then
                                return False;
                        end if;
                       
                        Factor := Factor + 1;
                end loop;
               
                return True;
        end Is_Prime;
       
        Sum, Power, High : Integer := 0;
begin
        Put("How high would you like to go? ");
        Get(High);
       
        loop
                declare
                        Current_Power, Perfect_Number : Integer := 0;
                begin
                        Current_Power := 2 ** Power;
                        Sum := Sum + Current_Power;

                        if Is_Prime(Sum) then
                                Perfect_Number := Sum * Current_Power;

                                if Perfect_Number > 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




PostPosted: Thu Oct 14, 2004 10:52 pm   Post subject: 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




PostPosted: Thu Oct 14, 2004 11:37 pm   Post subject: (No subject)

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

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




PostPosted: Fri Oct 15, 2004 9:33 am   Post subject: 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 here.
netninja




PostPosted: Fri Oct 15, 2004 11:50 am   Post subject: (No subject)

now i just feel stupid...

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

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




PostPosted: Fri Oct 15, 2004 1:01 pm   Post subject: Re: Perfect number contest. (i guess)

Woah... one of my professors was mentioned in that page on odd perfect numbers. Shocked 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:
code:
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




PostPosted: Mon Oct 18, 2004 5:23 pm   Post subject: (No subject)

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.
Sponsor
Sponsor
Sponsor
sponsor
Display posts from previous:   
   Index -> Contests
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 8 Posts ]
Jump to:   


Style:  
Search: