# Existence of Arbitrarily Long Aliquot Sequences

## Theorem

It is possible to construct an aliquot sequence of arbitrary length which is monotonically increasing.

## Proof

Let $p_i$ be the $i$th prime.

Construct the sequence $\sequence {t_i}_{t \mathop = 1}^\infty$ of natural numbers $t_i$ recursively as follows:

$t_1 = 2$
$t_{i + 1} = \map \phi {p_i^{t_i + 1} } - 1 = p_i^{t_i} \paren {p_i - 1} - 1$ for $i \ge 1$

We claim that this sequence has the property:

$(1): \quad p_i^{t_i + 1} \divides \map {\sigma_1} {p_{i + 1}^{t_{i + 1} } }$ for $i \ge 1$

For $i = 1$, $p_1 = 2$ and $t_1 = 2$.

$t_2 = 2^2 \paren {2 - 1} - 1 = 3$
$\map {\sigma_1} {p_2^{t_2} } = \map {\sigma_1} {3^3} = 40$

which is a multiple of $2^3 = 8$.

For $i > 1$:

 $\ds \paren {p_{i + 1} - 1} \map {\sigma_1} {p_{i + 1}^{t_{i + 1} } }$ $=$ $\ds p_{i + 1}^{t_{i + 1} + 1} - 1$ Divisor Sum of Power of Prime $\ds$ $=$ $\ds p_{i + 1}^{\map \phi {p_i^{t_i + 1} } } - 1$ $\ds$ $=$ $\ds 0$ $\ds \pmod {p_i^{t_i + 1} }$ Euler's Theorem

For $i > 1$, $p_{i + 1} - 1 > 2$.

Hence $p_{i + 1} - 1$ is even and composite.

Since $p_i$ is odd and $p_i > \dfrac {p_{i + 1} - 1} 2$ by Bertrand-Chebyshev Theorem:

$p_{i + 1} - 1$ and $p_i^{t_i + 1}$ are coprime.

By Euclid's Lemma, $p_i^{t_i + 1} \divides \map {\sigma_1} {p_{i + 1}^{t_{i + 1} } }$.

We define for $l \ge 1$: $A_l = \set {m \in \N: p_i^{t_i} \divides m, p_i^{t_i + 1} \nmid m, \forall i: 1 \le i \le l}$.

Denote $\map s n$ the aliquot sum of $n$.

Then for $m \in A_l$ where $l \ge 2$, we claim:

 $\text {(2)}: \quad$ $\ds \map s m$ $>$ $\ds m$ $\text {(3)}: \quad$ $\ds \map s m$ $\in$ $\ds A_{l - 1}$

Let $m \in A_l$ where $l \ge 2$.

From definition we have:

 $\ds p_1^{t_1}$ $=$ $\ds 4 \divides m$ $\ds p_2^{t_2}$ $=$ $\ds 27 \divides m$

Hence $m$ is a multiple of $27 \times 4 = 108$.

Since $108$ is abundant, $m$ is also abundant by Multiple of Abundant Number is Abundant.

$\map s m > m$ follows from definition of abundant numbers.

Write $m = p_1^{t_1} \cdots p_l^{t_l} k$, where $k$ is not divisible by $p_1, \dots, p_l$.

Then:

 $\ds \map s m$ $=$ $\ds \map {\sigma_1} m - m$ $\ds$ $=$ $\ds \map {\sigma_1} {p_1^{t_1} } \map {\sigma_1} {p_2^{t_2} } \cdots \map {\sigma_1} {p_l^{t_l} } \map {\sigma_1} k - m$ Divisor Sum Function is Multiplicative $\ds$ $=$ $\ds K p_1^{t_1 + 1} \cdots p_{l - 1}^{t_{l - 1} + 1} - p_1^{t_1} \cdots p_l^{t_l} k$ for some $K \in \N$, by $(1)$ $\ds$ $=$ $\ds p_1^{t_1} \cdots p_{l - 1}^{t_{l - 1} } \paren {K p_1 \cdots p_{l - 1} - p_l^{t_l} k}$

Since $K p_1 \cdots p_{l - 1}$ is divisible by $p_1, \dots, p_{l - 1}$ while $p_l^{t_l} k$ isn't:

$p_1, \dots, p_{l - 1} \nmid \paren {K p_1 \cdots p_{l - 1} - p_l^{t_l} k}$

Hence for each $i$ where $1 \le i \le l - 1$:

$p_i^{t_i} \divides \map s m, p_i^{t_i + 1} \nmid \map s m$

This shows that $\map s m \in A_{l - 1}$.

Hence to create an aliquot sequence of length $l$, one picks an element $m$ from $A_l$.

Applying $(2)$ and $(3)$ repeatedly, we see that:

$m, \map s m, \map s {\map s m}, \dots, \map {s^l} m$

$\blacksquare$