How to check for perfect numbers?

2,407

Solution 1

Let $\mathbb{P}$ the set of all prime numbers.

It can be shown that if $2^p-1\in\mathbb{P}$ (which implies that $p\in\mathbb{P}$), then $2^{p-1}(2^p-1)$ is perfect. This was proved by Euclid (and those numbers are sometime called Euclid's numbers).

Conversely, any even perfect number is an Euclid's number : this was proved about 20 centuries later by Euler.

Until today, no odd perfect number is known ...

So detecting even perfect numbers is closely related to the question of detecting Mersenne primes (that is : primes of the form $2^p-1$).

A fast algorithm exists for this : it's called the Luca's test (see here)

It should also be worth looking at this site

Solution 2

Computing the factor sum $\sigma_1(N)$ is quickly done from the prime decomposition of $N$.

Suppose $N$ has a number of prime factors $p_1^{a_1}p_2^{a_2}\ldots$. For the purpose of illustration take $a_1=3$. Then for any divisor $d$ of $N$ that is coprime to $p_1$, $N$ is also divisible by $p_1d$, $p_1^2d$, and $p_1^3d$. Also we know that $d$ must divide $N/p_1^3$. So here the factor sum of $N$ can be decomposed as $\sigma_1(N) = \sigma_1(N/p_1^3)(1+p_1+p_1^2+p_1^3)$ and since $(1+p_1+p_1^2+p_1^3) = \sigma_1(p_1^3)$ we can write this as $\sigma_1(N) = \sigma_1(N/p_1^3)\sigma_1(p_1^3)$.

So we can decompose $N$ into primes and for each prime power use the sum of powers formula. See how that works for $N=72=2^33^2$; we should find that $\sigma_1(N) = \sigma_1(2^3)\sigma_1(3^2) = (1+2+4+8)(1+3+9) = 15\cdot 13 = 195$. Laying out a table of factors of $72$ we can see this multiplication effect at work:

\begin{array}{c} 1 & 2 & 4 & 8 \\ 3 & 6 & 12 & 24 \\ 9 & 18 & 36 & 72 \\ \end{array}

Now when we're looking for perfect numbers, we're looking for the case when $\frac{\sigma_1(N)}{N}=2$, so it makes sense to consider this ratio. This can also obviously be decomposed into distinct prime components $\frac{\sigma_1(p_i^{a_i})}{p_i^{a_i}}$, which gives many of the results concerning perfect numbers, since the size of this value is tightly constrained between $\frac{p_i+1}{p_i}$ and $\frac{p_i}{p_i-1}$.

Share:
2,407

Related videos on Youtube

Admin
Author by

Admin

Updated on February 16, 2020

Comments

  • Admin
    Admin over 3 years

    To quote Wikipedia :

    In number theory, a perfect number is a positive integer that is equal to the sum of its proper positive divisors, that is, the sum of its positive divisors excluding the number itself (also known as its aliquot sum). Equivalently, a perfect number is a number that is half the sum of all of its positive divisors (including itself) i.e. $\sigma_1(n) = 2n$.

    So one can easily define an algorithm to check for perfect numbers :

    Let the number be $N$. We take an iteration from $i=1$ to $i=(N-1)$. If any particular $i $ satisfies $N \, mod\,\, i=0$ , then it is added to some variable say $S$, which is $0$ to begin with. At last, if $S = N$ , then $N$ is a perfect number.

    This process is very lengthy and sometimes tedious.

    Is there any faster way to check if a number is perfect? Is there any result in Number Theory related to checking Perfect Numbers? Is there any "general formula" / "closed form" for perfect numbers ?

    Thanks in advance ! :-)