Abundant Numbers I

Last Sunday, I was browsing Project Euler where I found an interesting line in the statement of Problem 23:

“…it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers.”

An abundant number is a positive integer n such that the sum of the proper divisors of n is greater than n. Equivalently, the sum of the divisors of n is greater than 2n.

Problem 23 isn’t about the above stated result, but that is what interested me. So, I want to spend the next two or three posts proving this result and then, if we feel like it, providing a solution to problem 23. In this first post, I want to give an exposition of Douglass E. Iannucci’s 2005 article On the Smallest Abundant Number Not Divisible by the First k PrimesWe don’t need the full strength of the algorithm to find said abundant number, but it will be useful for finding odd abundant numbers.

Let \sigma:\mathbb{N}\rightarrow\mathbb{N} denote the arithmetic function

\displaystyle\sigma(n):=\sum_{d\mid n}d,\indent\forall n\in\mathbb{N}

where d ranges over the divisors of n. We define the index of a positive integer n by

\displaystyle\sigma_{-1}(n):=\dfrac{\sigma(n)}{n}=\prod_{j=1}^{k}\left(1+\dfrac{1}{p_{j}}+\cdots+\dfrac{1}{p_{j}^{e_{j}}}\right),

where n=p_{1}^{e_{1}}\cdots p_{k}^{e_{k}} is the prime factorization of n. The right-most expression shows that \sigma_{-1} is a multiplicative function.

Suppose p and q are primes with p<q. Then

\displaystyle\dfrac{q}{q-1}=1+\dfrac{1}{q-1}\leq1+\dfrac{1}{p}=\dfrac{p+1}{p},

where the inequality is strict if q>3. For integers e,f\geq 1, we obtain the inequality

\displaystyle\sigma_{-1}(q^{f})<\dfrac{q}{q-1}\leq\frac{p+1}{p}\leq\sigma_{-1}(p^{e})

Consider the product

\displaystyle V_{t}(k)=\prod_{j=k+1}^{t}\dfrac{p_{j}+1}{p_{j}}=\sigma_{-1}(p_{k+1}\cdots p_{t}),\indent\forall k\geq 1

where t>k. Since the infinite series \sum\frac{1}{p} diverges, where p ranges through all the primes, we see that V_{t}(k) increases without bound as t\rightarrow\infty. For k\geq 1, define the quantity v(k) by

\displaystyle v(k):=\min\left\{t:V_{t}(k)>2\right\}

Let A(k) denote the minimal abundant number not divisible by the first k primes. Tautologically,

\displaystyle A(k)\leq p_{k+1}\cdots p_{v(k)}

For k\geq 1 and t\geq 2, define the quantity U(k) by

\displaystyle U_{t}(k)=\prod_{j=k+1}^{t}\dfrac{p_{j}}{p_{j}-1}

and u(k) by

\displaystyle u(k):=\min\left\{t:U_{t}(k)>2\right\}

Since \frac{p_{j}}{p_{j}-1}>\frac{p_{j}+1}{p_{j}}, we see that U_{t}(k)>V_{t}(k) and therefore u(k)\leq v(k).

Lemma 1. A(k) is divisible by p_{k+1},\ldots,p_{u(k)}.

Proof. Suppose that p_{1}\cdots p_{u(k)}\nmid A(k). A(k) has the unique prime factorization

\displaystyle A(k)=q_{1}^{e_{1}}\cdots q_{t}^{e_{t}}\text{ where }q_{1}<\cdots<q_{t}\text{ and }e_{i}\geq1

By definition of A(k), we have that p_{k}<q_{1}. Since \left\{p_{i}\right\}_{i=1}^{\infty} is an enumeration of the primes in ascending order, we see that q_{i}\geq p_{k+i} for all i=1,\ldots,t.

I claim that t\geq u(k)-k. Indeed, otherwise

\begin{array}{lcl}\displaystyle\sigma_{-1}(A(k))=\sigma_{-1}(q_{1}^{e_{1}})\cdots\sigma_{-1}(q_{t}^{e_{t}})&<&\sigma_{-1}(p_{k+1}^{e_{1}})\cdots\sigma_{-1}(p_{k+t}^{e_{t}})\\[2 em]&\leq&\displaystyle\dfrac{p_{k+1}}{p_{k+1}-1}\cdots\dfrac{p_{k+t}}{p_{k+t}-1}\\[2 em]&\leq&\displaystyle\dfrac{p_{k+1}}{p_{k+1}-1}\cdots\dfrac{p_{u(k)-1}}{p_{u(k)-1}-1}\\[2 em]&\leq&\displaystyle2\end{array}

But this is a contradiction, as A(k) is by definition an abundant number and therefore \sigma_{-1}(A(k))>2

By hypothesis, there exists an index 1\leq j\leq k such that p_{j}\nmid A(k). Since t\geq u(k)-k, q_{1}<\cdots<q_{t}, and q_{i}\geq p_{k+i}, we see that there is at least one index i such that q_{i}>p_{u(k)}. Relabeling if we necessary, we may assume without loss of generality that i=1. Our work above shows that

\displaystyle\sigma_{-1}\left(p_{j}q_{2}^{e_{2}}\cdots q_{t}^{e_{t}}\right)>\sigma_{-1}\left(q_{1}^{e_{1}}q_{2}^{e_{2}}\cdots q_{t}^{e_{t}}\right)=\sigma_{-1}\left(A(k)\right)>2

Since \sigma_{-1} is multiplicative, we conclude that

\displaystyle p_{j}q_{2}^{e_{2}}\cdots q_{t}^{e_{t}}<q_{1}^{e_{1}}q_{2}^{e_{2}}\cdots q_{t}^{e_{t}}=A(k),

which contradicts the minimality of A(k) \Box.

We now describe an algorithm for finding the smallest abundant number not divisible by the first k primes (e.g. A(k)). First, compute u(k). Set P_{k}:=p_{1}\cdots p_{k}. As argued above, the divergence of the infinite series \sum_{p}\frac{1}{p}, where p ranges over all primes, implies that the product mP_{k}\rightarrow\infty, as m\rightarrow\infty. This is still true if we require that m be coprime to p. Hence, there exists a unique minimal integer M(k) such that

\displaystyle M(k)=\min_{(m,P_{k})=1}\left\{m:\sigma_{-1}(mp_{k+1}\cdots p_{u(k)})>2\right\}

I claim that A(k)=M(k)p_{k+1}\cdots p_{u(k)}. Indeed, by the division algorithm and Lemma 1, we can write A(k)=mp_{k+1}\cdots p_{u(k)}, where m is a positive integer. Since p_{1},\ldots,p_{k}\nmid A(k), we must have that (m,P_{k})=1. Since A(k) is by definition the minimal abundant number not divisible by P_{k}, we conclude that m=M(k)

Advertisements
This entry was posted in math.NT, Problem Solving, Python and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s