Perfect Number¶
Let us define the divisor function. The divisor function is the sum of all the divisors of a number to the kth power. $$ \sigma(n,k)=\sum_{p|n}p^k $$
In [ ]:
def sqrt(x):
y = 1
prev = 0
while 1 <= abs(y-prev):
prev = y
y = 1.0/2*(prev+x/prev)
while (y+1)*(y+1) < x:
y += 1
return int(y)
def divisor(x):
n = sqrt(x)
lst = []
for i in range(1, n+1):
if x % i == 0:
lst.append(i)
if i != x/i:
lst.append(int(x/i))
lst.sort()
return lst
def divisorFunction(d, k):
res = 0
for x in d:
res += x**k
return res
for i in range(1, 11):
lst = divisor(i)
df = divisorFunction(lst, 1)
print(f"{i}\t{df}\t{lst}")
1 1 [1] 2 3 [1, 2] 3 4 [1, 3] 4 7 [1, 2, 4] 5 6 [1, 5] 6 12 [1, 2, 3, 6] 7 8 [1, 7] 8 15 [1, 2, 4, 8] 9 13 [1, 3, 9] 10 18 [1, 2, 5, 10]
A perfect number is a number whose sum of its divisors excluding itself equals itself.
\begin{align} \sigma(n)-n&=n\\ \sigma(n)&=2n \end{align}
In [ ]:
def is_perfect(x):
n = sqrt(x)
sum = 0
for i in range(1, n+1):
if x % i == 0:
sum += i
if i != x/i:
sum += x/i
return 2*x == sum
for i in range(1, 30000):
lst = divisor(i)
df = divisorFunction(lst, 1)
if is_perfect(i):
print(f"{i}\t{df}\t{lst}")
6 12 [1, 2, 3, 6] 28 56 [1, 2, 4, 7, 14, 28] 496 992 [1, 2, 4, 8, 16, 31, 62, 124, 248, 496] 8128 16256 [1, 2, 4, 8, 16, 32, 64, 127, 254, 508, 1016, 2032, 4064, 8128]
Mersenne numbers are closely related to perfect numbers. An even perfect number takes a form of:
$$ 2^{p-1}*M_p $$
where $M_p$ is a Mersenne number of order $p$.
In [ ]:
import sympy
from sympy import symbols
p = symbols("p")
mersenne = 2**p-1
even_perfect_number = 2**(p-1)*mersenne
for i in range(1, 10):
n = even_perfect_number.subs([(p, i)])
flag = "*" if is_perfect(n) else " "
print(f"{flag} {i}\t{n}")
1 1 * 2 6 * 3 28 4 120 * 5 496 6 2016 * 7 8128 8 32640 9 130816