NTIC Perfect Numbers

Subsection 19.4.1 A perfect definition and theorem

Definition 19.4.1.

When the ratio $\frac{\sigma(n)}{n}$ is exactly $2\text{,}$ we say $n$ is a perfect number.

This is a big definition, and it goes back at least to Euclid. Euclid defines the notion at the beginning of the number-theoretic books of the Elements, and only mentions it again over one hundred propositions later, where he proves that certain numbers are, in fact, perfect. (A careful reader will notice that the primes in question are, in fact, the Mersenne primes of Definition 12.1.6!) Such a conclusion is a fitting end, as William Dunham says in his book, Journey through Genius [C.5.5].

🔗

Theorem 19.4.2.

If $n$ is a number such that $2^n-1$ is prime, then the (even) number $2^{n-1}\left(2^n-1\right)$ is perfect.

🔗

Proof.

Euclid's proof (in the link) of this is worth looking at.

🔗

Many centuries later, Euler proved the converse; we will prove them together. (See also Chapter 1 of Dunham's Euler: The Master of Us All [C.5.6].)

🔗

Theorem 19.4.3. Characterization of Even Perfect Numbers.

If $n$ is an even number, it is perfect if and only if it is the product of a power $2^{n-1}$ and a prime of the form $2^n-1\text{.}$

🔗

Proof.

First, assume that $2^n-1$ is prime. Then the factors of $2^{n-1}\left(2^n-1\right)$ are coprime, so

\begin{equation*} \sigma\left(2^{n-1}\left(2^n-1\right)\right)=\sigma\left(2^{n-1}\right)\sigma\left(2^n-1\right)=\left(2^n-1\right)\left(2^n-1+1\right) \end{equation*}

The steps are because of multiplicativity and the formulas we had earlier (see Theorem 19.2.5) for $\sigma$ of powers of two and primes. But then

\begin{equation*} \left(2^n-1\right)\left(2^n-1+1\right)=2^n\left(2^n-1\right)=2\left[2^{n-1}\left(2^n-1\right)\right] \end{equation*}

so that the sum of divisors is exactly twice the original number.

Now for the converse, which is somewhat longer. Let us start with an even perfect number, which is perforce divisible by some power of two.

Looking ahead, call this power the $(n-1)$th power! Then our even perfect number may be written as $2^{n-1}q\text{,}$ where $q$ is the (odd) quotient.

Let's divide the rest of the proof into several pieces. First, two facts.

We know that this number is perfect, so

\begin{equation*} \sigma\left(2^{n-1}q\right)=2\cdot 2^{n-1}q=2^nq \end{equation*}
We also know how to compute $\sigma\text{,}$ so

\begin{equation*} \sigma\left(2^{n-1}q\right)=\sigma\left(2^{n-1}\right)\sigma(q)=\left(2^n-1\right)\sigma(q) \end{equation*}

We can combine these observations to see that

\begin{equation*} 2^nq=\left(2^n-1\right)\sigma(q) \end{equation*}

Note that this means $2^n-1\mid q\text{,}$ since $q$ is the only odd part of the left-hand side (implicitly using some of Theorem 6.3.2). Let's write

\begin{equation*} \left(2^n-1\right)m=q\text{.} \end{equation*}

Substituting, we have

\begin{equation*} 2^n\left(2^n-1\right)m=\left(2^n-1\right)\sigma(q)\Rightarrow 2^nm=\sigma(q) \end{equation*}

Since $m$ and $q$ both divide $q\text{,}$ by the definition of $\sigma$ we have

\begin{equation*} \sigma(q)\geq q+m=\left(2^n-1\right)m+m=2^nm \end{equation*}

Since these two divisors ($q$ and $m$) alone add up to $\sigma(q)\text{,}$ it must be true that $q$ has exactly these two divisors, so it is prime. That means $m=1\text{,}$ and $q=2^n-1\text{,}$ and so the perfect number is $2^{n-1}\left(2^n-1\right)\text{.}$ Great!

🔗

We will leave the question about whether there are odd perfect numbers to Section 19.5.

🔗

Subsection 19.4.2 Speculation and more terminology

¶

🔗

There are many things people have claimed about numbers of this type. A Hellenistic Roman in the first century in Gerasa¹Interestingly, this is the same place as one setting of the Biblical story of the demons called “Legion” who went into swine. named Nichomachus claimed that the

$n$ th perfect number had

$n$ decimal digits.

🔗

Nicomachus was more concerned with mystical claims about perfect numbers (which many repeated), but this mathematical assertion continued to be made for over a thousand years. However, knowing what we do about Mersenne primes (recall Definition 12.1.6), we see that the fifth such prime is 13, so that the next perfect number,

$\begin{equation*} \left(2^{13}-1\right)\cdot 2^{12}\text{,} \end{equation*}$

🔗

was very large and so lay mysterious for a long time. It was apparently discovered in the fifteenth century.

xxxxxxxxxx
 
(2^13-1)*2^12

🔗

Until the early modern period, such numbers were basically inaccessible.

🔗

Number theorists (often of the amateur variety, but certainly not always) have come up with all kinds of other names for various concepts related to

$\sigma(n)/n\text{.}$

🔗

Definition 19.4.4.

Recall that if $\sigma(n)=2n\text{,}$ then $n$ is perfect.

If $\sigma(n)=kn$ for some integer $k\text{,}$ then we say that $n$ is $k$ -perfect.
Or, if $\sigma(n)>2n\text{,}$ then $n$ is abundant.
If $\sigma(n)<2n\text{,}$ we say $n$ is deficient.

🔗

As it will turn out, these things are not really good characterizations of what it means to have “too many” or “too few” divisors, but in recognition of the Greeks' contributions we keep this allusive and fairly standard terminology. As examples, Exercise 19.6.7 asks for a 3-perfect number, if one exists, and Exercise 19.6.17 asks for a 4-perfect number.

🔗

Definition 19.4.5.

Here are some less well-known, but nonetheless interesting, terms.

A number is pseudoperfect if it is the sum of some of its divisors (other than itself).
A number $n$ is superabundant if the ratio $\sigma(n)/n$ for $n$ is bigger than the value of the ratio for all smaller $m\lt n\text{.}$
A number is weird if it is abundant but not pseudoperfect. (There is a famous paper of Erdős on this topic.)

🔗

There are many questions one can ask about these and other definitions; see Exercise Group 19.6.15–21 One cheeky such question is this.

🔗

Question 19.4.6.

Is a perfect number pseudoperfect?

🔗

One other interesting idea is that of amicable numbers, which are pairs

$m,n$ of numbers such that

$\sigma(n)=\sigma(m)=m+n\text{.}$ Clearly any perfect number is amicable with itself. The smallest pair of unequal amicable numbers is

$(220,284)\text{;}$ this was known to the ancient Greeks, cherished by some medieval Muslims, and apparently was not improved upon until the modern number-theoretic era.

🔗

Fermat, Descartes, and Euler all worked with this and found large examples, but it turns out that the next smallest pair was found by a sixteen-year old Italian boy in 1860!

xxxxxxxxxx
 
sigma(1184),sigma(1210),1184+1210

🔗

Apparently he came up with this by trial and error, though no one knows for sure. The internet can provide some of the most current data on these pairs.

🔗

There is a way to get as many amicable pairs as you like, discovered by Ibn Qurra and (later) Fermat (see [C.5.8, II.IV]), and finally used by Euler.

🔗

Algorithm 19.4.7. Get Amicable Numbers.

Here is one way to get amicable numbers.

Make a list of numbers of the form $p_n=3\cdot 2^n-1$ and $q_n=9\cdot 2^{2n-1}-1\text{.}$
Then check if $p_{n-1}\text{,}$ $p_n\text{,}$ and $q_n$ are all prime.
If so, then $2^np_{n-1}p_n$ and $2^nq_n$ are an amicable pair.

🔗

Proof.

Since only primes and powers of two are involved, it's easy to calculate $\sigma$ in this case, so proving it is left as an exercise (see Exercise 19.6.21).

xxxxxxxxxx
 
@interact
def _(n=[2..20]):
    pretty_print(html("We have $p_{%s}=%s$ and $p_{%s}=%s$"%(n,3*2^(n-1)-1,n,3*2^(n)-1)))
    pretty_print(html("And $q_{%s}=%s$ as well."%(n,9*2^(2*n-1)-1)))
    if is_prime(3*2^n-1) and is_prime(3*2^(n-1)-1) and is_prime(9*2^(2*n-1)-1):
        pretty_print(html("Then the pair $%s$ and $%s$ is amicable!"%(2^n*(3*2^(n-1)-1)*(3*2^(n)-1), 2^n*(9*2^(2*n-1)-1))))
    else:
        pretty_print(html("Doesn't give an amicable pair"))

🔗

Subsection 19.4.3 The abundancy index

¶

🔗

It's time to give a name to the mysterious ratio at the core of this section.

🔗

Definition 19.4.8.

The ratio $\frac{\sigma(n)}{n}$ may be called the abundancy index of $n\text{.}$

🔗

A beautiful thing is that once you name a concept, you can ask questions about it. Here's another largely open question which seems like it should be easy…

🔗

Question 19.4.9.

Rather than asking which integers can be gotten, which rational numbers can be gotten as $\frac{\sigma(n)}{n}\text{?}$

xxxxxxxxxx
 
@interact
def _(n=(20,[1..200])):
    cols = ceil(n/10)
    T = [cols*['$n$',r'$\sigma(n)/n$']]
    list = [[i,(sigma(i)/i)] for i in range(1,n+1)]
    list.extend((10-(len(list)%10))*['',''])
    for k in range(10):
        t = [item for j in range(cols) for item in list[k+10*j]]
        T.append(t)
    pretty_print(html(table(T,header_row = True, frame = True)))

🔗

There are some interesting theorems about this already known. For one thing, the abundancy index is the same thing as

$\sigma_{-1}(n)\text{.}$

🔗

Fact 19.4.10.

$\begin{equation*} \sigma_{-1}(n)=\frac{\sigma(n)}{n} \end{equation*}$

🔗

Proof.

We have that

\begin{equation*} \sigma(n)/n=\left(\sum_{d\mid n}d\right)/n \end{equation*}

Now note that for every $d\mid n\text{,}$ the quotient is also an integer divisor $d'$ of $n\text{.}$ So

\begin{equation*} \sigma(n)/n=\sum_{d\mid n}\frac{1}{d'} \end{equation*}

This is the same list as the original divisor list, so reordering gives

\begin{equation*} \sigma(n)/n=\sum_{d\mid n}\frac{1}{d}=\sigma_{-1}(n) \end{equation*}

🔗

Fact 19.4.11.

Clearly all such numbers are in the interval $\left[1,\infty\right)\text{.}$ Here are some more known facts about the abundancy index.

If $m\mid n\text{,}$ then $\sigma_{-1}(n)\geq \sigma_{-1}(m)\text{.}$
If $\sigma_{-1}(n)=\frac{a}{b}$ in lowest terms, then $b\mid n\text{.}$
If $r$ is “caught” between $\sigma(n)$ and $n$ (such that $n<r<\sigma(n)$ ) and is relatively prime to $n\text{,}$ then $r/n$ is not an abundancy index.

🔗

Proof.

We skip the proof, but proving the first two facts is left as Exercise 19.6.22.

🔗

Holdener and Stanton picturesquely call rational numbers which are not abundancies abundancy outlaws. The end of this hyper-linked paper [C.7.11] has a nice list of which numbers thus far have been found, and which have not.

Number Theory: In Context and Interactive

Section 19.4 Perfect Numbers

Subsection 19.4.1 A perfect definition and theorem

Definition 19.4.1.

Theorem 19.4.2.

Proof.

Theorem 19.4.3. Characterization of Even Perfect Numbers.

Proof.

Subsection 19.4.2 Speculation and more terminology

Definition 19.4.4.

Definition 19.4.5.

Question 19.4.6.

Algorithm 19.4.7. Get Amicable Numbers.

Proof.

Subsection 19.4.3 The abundancy index

Definition 19.4.8.

Question 19.4.9.

Fact 19.4.10.

Proof.

Fact 19.4.11.

Proof.