## 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. 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

By definition of $A(k)$, we have that $p_{k}. 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, 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}},

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)$