Threaded Mode | Linear Mode

***l3g1sl4tor*** · 03-31-2010, 04:26 AM

Greetings guys... Today I will talk with you about perfect numbers, one of, for me, the most interested appear in math.

Code:

number n>1 E R is perfect if sum of all it's positive divisors (includin 1 and n) equal 2n. Find all perfect numbers n for case n-1 and n+1 mod 2 <> 0

Competitors of math with little experience wouldnt be hard to solve a task using well known fact, every prime number bigger then 3 we can write down as 6k-1 or 6k+1 for some natural number k. However, there is an other solution. It requires some higher knowing of theory of numbers, but it is interesting, because it shows connection between this task and some famous unsolved problems of theory of numbers.

A little of history. Perfect numbers are very old in math. It were developed by the ancient greeks, and they were very easy counted few first represents of it... 6, 28, 496, 8128.... Some logical questions are :

Code:

) Is there some basic formula for calculating all perfect numbers?

) Is there uncountable amount of that numbers?

) First few perfect numbers are even... Are they all even?

Particular answer on the first question was found in the ancient time. Euklid formed next theorem : If p and 2^p - 1 are prime numbers, then Sp = 2^p-1((2^p)-1).

Proof of this theorem isnt so hard... It is enough to notice that all positive divisors of number Sp : 1,2,2^2, ... , 2^p-1,

1((2^p)-1), 2((2^p)-1), (2^2)((2^p)-1), ... , (2^p-1)((2^p)-1).

sum of divisors from the first line we can easy count as

1+2+2^2+...+2^p-1=(2^p)-1

sum of divisors in the second line is equal
((2^p-1)-1)(1+2+2^2+ ... + 2^p-1) = (2^p - 1)(2^p - 1)

So whole sum of all divisors is
(2^p - 1) + (2^p -1)(2^p -1) = (2^p - 1)(1 + 2^p -1) = 2x2^p(2^p - 1) = 2Sp

Conclusion : Number Sp is a perfect number!

Code:

Is with given formula found all of even perfect numbers?

Old Greeks believed that is correct, but they did not succeed do proove it. That speculation is, however, correct, and first prove of that gathered Swis scientist Oyler in the 18th century.

Theoreme 2 :

Every even perfect number can be writed in shape :
Sp = (2^p-1)((2^p - 1))
where p and (2^p) - 1 are prime.

Code:

Table of first 4 perfect numbers :

p  | 2^p - 1 | Sp |

2  |      3     |  6  |

3  |      7     | 28 |

5  |     31    |496|

7  |    127   |8128|

Next prime number (11) is not giving perfect number cos 2^11 - 1 = 2047 = 23x89... Sp = 2096128. So, for some prime numbers p number Sp is perfect, and for some it is not. Further tries indicates that for big prime numbers p perfect numbers are less. Until today it is found only 44 perfect numbers! The bigest of them is explored in spetember 2006 and have over 19 million digits!

Code:

and what is with eventual odd perfect numbers?

Here we have big lack of information. Til now on several different ways are checked all odd numbers with less then 300 digits , and all of them which have at least 1 prime divisor with less then 20 digits.They didn't found not one perfect number?! O.o Again, most of scientists that this number isnt exist (answer on upper question is negative) but without of proves... It is one more very old and open math problem...

================================================

If you have free time, and want to be a famous world scientist, try touse upper algorithm and make a program for discovering more perfect numbers! Tongue

Hope Iand my story wasn't to borring for you, and I also hope you have read it til end! Smile

***drdebcol*** · (This post was last modified: 03-31-2010 05:24 PM by drdebcol.)

I am impressed with your post. I knew about this numbers !
They are almost important as prime numbers.
This formula is great :
[Image: 49694_formulaperfectnumbers.jpg]

[Image: 49694_formulaperfectnumbers.jpg]

And it is known that you can generate perfect numbers using this formula and this sequence of primes :

Code:

2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917

Euclid is one of the best mathematicians ever !
You said that the biggest perfect number is explored in 2006 and have over 19 million digits, and for primes it is around 10^6 digits.
I wanted to solve this problem in programming easily.
So i made this in Pascal and C !
In Pascal i used longint and it can easily generate 4 first perfect numbers :
6,28,496,8128.
I used the theory that all perfect numbers are even and i implemented that to make it faster.
Here is the code :

Code:

program perfect_numbers;

uses wincrt;

var

i,n:longint;

function is_perfect(a:longint):boolean;

var

  i,s:longint;

begin

  s:=0;

  for i:=1 to a do

    if a mod i = 0 then

      s:=s+i;

  if s div 2 = a then

    is_perfect:=true

  else

    is_perfect:=false;

end;

begin

readln(n);

  for i:=2 to n do

    if not odd(i) then

      if is_perfect(i) then

        writeln(i);

end.

And in C i used "unsigned long long", the biggest integer built in data type in C or C++ programming language.
You can see it's size here :

Code:

0 . . 18 446 744 073 709 551 615

And here is the solution :

Code:

# include <stdio.h>

short is_perfect(unsigned long long a)

{

  unsigned long long i,s;

  s=0;

  for (i=1;i<=a;i++)

    if (a % i == 0) 

      s+=i;

  if (s == a*2) 

    return 1;

  else

    return 0;

}

int main()

{

   unsigned long long i,n;

   printf("Enter to which num you want perfect numbers : \n");

   scanf("%d",&n);

   for (i=2;i<=n;i++)

     if (i % 2 == 0 && is_perfect(i)==1)

         printf("%d\n",i); 

   scanf("%d");    

   return 0; 

}

I used only <stdio.h> so in the end i didn't use system("pause"), because you need to have <iostream> included, but i wanted pure C.
There could be some optimizations in both programs. Some operations can be skipped, but i think that both are fast enough to generate first 4 perfect numbers.
Overall l3g1sl4tor great job !

Alphablend · 03-31-2010, 08:49 AM

The story wasnt boring. The post is great. Smile

@ DrDebcol
nice code.

***l3g1sl4tor*** · 03-31-2010, 08:39 PM

Thx guys

In the near future i will try to introduce you with few more interesting math things Smile

@drdebcol : smooth solution in pascal, good job, pure math Smile