Largest Integer not Sum of Two Abundant Numbers

From ProofWiki
Jump to navigation Jump to search

Theorem

The largest integer which is not the sum of $2$ abundant numbers is $20 \, 161$.


Proof

First we show that for $1 < k < 90$, $315 k$ is abundant.

If $k$ is divisible by $3, 5, 7$, note that:

$945, 1575, 2205$

are all abundant, and $315 k$ is a multiple of at least one of them.

Hence $315 k$ is abundant by Multiple of Abundant Number is Abundant.


If $k$ is not divisible by $3, 5, 7$:

Let $p$ be a prime such that $p \divides k$.

Then:

\(\ds \frac {\map \sigma {315 p} } {315 p}\) \(=\) \(\ds \frac 1 {315 p} \paren {1 + 3 + 3^2} \paren {1 + 5} \paren {1 + 7} \paren {1 + p}\)
\(\ds \) \(=\) \(\ds \frac {208} {105} \paren {1 + \frac 1 p}\)
\(\ds \) \(>\) \(\ds \frac {208} {105} \paren {1 + \frac 1 {90} }\) $p < 90$
\(\ds \) \(>\) \(\ds 2\)

hence $315 p$ and $315 k$ are abundant.


Since $88$ and $315$ are coprime:

$88 = 2^3 \times 11$
$315 = 3^2 \times 5 \times 7$

By Largest Number not Expressible as Sum of Multiples of Coprime Integers, all numbers greater than or equal to:

$\paren {88 - 1} \paren {315 - 1} = 27 \, 318$

can be expressed as a sum of multiples of $88$ and $315$.


Hence for $n \ge 27 \, 318 + 315 \times 2 = 27 \, 948$:

$\exists s, t \in \N: 90 > t \ge 2: n = 88 s + 315 t$

and both $88 s$ and $315 t$ are abundant for $s > 0$.


For $s = 0$, $t \ge \dfrac {27 \, 948} {315} > 2 = \paren {2 - 1} \paren {3 - 1}$.

By Largest Number not Expressible as Sum of Multiples of Coprime Integers, $t - 5$ can be expressed as a sum of multiples of $2$ and $3$.

Hence:

$\exists a, b \in \Z_{> 0}: 2 a + 3 b = t$

This gives:

$n = 630 a + 945 b$

and both $630 a$ and $945 b$ are abundant.


We still need to find representations for $20 \, 162 < n < 27 \, 948$.

We can check this via brute force.

Using Largest Number not Expressible as Sum of Multiples of Coprime Integers/Generalization, we can narrow down our search to numbers that are not divisible by small primes:


Since $\gcd \set {18, 20} = 2$, the largest multiple of $2$ not expressible as a sum of multiples of $18$ and $20$ is:

$\dfrac {18 \times 20} 2 - 18 - 20 = 142 < 20161$

Since $\gcd \set {12, 945} = 3$, the largest multiple of $3$ not expressible as a sum of multiples of $12$ and $945$ is:

$\dfrac {12 \times 945} 3 - 12 - 945 = 2823 < 20161$

Since $\gcd \set {20, 945} = 5$, the largest multiple of $5$ not expressible as a sum of multiples of $20$ and $945$ is:

$\dfrac {20 \times 945} 5 - 20 - 945 = 2815 < 20161$

Since $\gcd \set {56, 945} = 7$, the largest multiple of $7$ not expressible as a sum of multiples of $56$ and $945$ is:

$\dfrac {56 \times 945} 7 - 56 - 945 = 6559 < 20161$


All numbers involved above are abundant.

Hence we only need to consider $n$ not divisible by $2, 3, 5, 7$.


Sources