This is a nearly-elementary introduction to the theory and analysis of aliquot sequences, assuming only a very
little bit of basic number theory, and using that to motivate and delve into the various defintions such as
**guides**, **class**, **twos count**, and others as related by Clifford Stern, though I
hope this is somewhat more pedagogically oriented. The reason I'm writing this is because the knowledge built
herein was only acquired by myself after a couple of years of slowly digesting Mr. Stern's material with
almost no comprehension, slowly working my way through it step by elementary step. This will also serve
as a good reference.

This guide starts from the basics: all that's assumed is a basic understanding of primality, unique factorizations, divisors (including such things as gcd), an understanding of why 6 is a perfect number, and some low level college mathematics notation. We'll develop the rest as we need it.

6 is a **perfect number** because the sum of its divisors, 1, 2, and 3, is 1 + 2 + 3 = 6. Except that this is a slight
misunderstanding, because if 1 divides 6, then we must also say 6 divides 6 (consistent with the number
theoretic definition of divisibility), and so the "actual" sum of divisors
of 6 is 1+2+3+6=12. Lets formalize this. We define the **sum of divisors function** as follows:
$$\sigma(n) = \sum_{d \mid n}{d}$$
To allow 6 as a perfect number, we define the **aliquot function**, the sum of
**proper divisors**, as
$$a(n) = \sigma(n) - n$$
(that is, all the divisors except the number itself,) and say that a perfect number is a number $n$ such that
$a(n) = n$, or equivalently, $\sigma(n) = 2n$. But how many numbers are perfect in this sense? It is conjectured
to be infinite, but as it turns out, there are very few known. It is relatively easy to prove (first done by
Euclid) that if $2^p - 1$ is a prime number
(a Mersenne prime), then $$n = 2^{p-1}(2^p - 1)$$ is a perfect number. To see this, first list the powers of 2
that divide $n$: $1$, $2$, $2^2$, $2^3$, ..., $2^{p-1}$. Next, $(2^p - 1)$ is clearly a divisor, but finally we
also have to include $2 \cdot (2^p - 1)$, $2^2 \cdot (2^p - 1)$, $2^3 \cdot (2^p - 1)$, ..., $2^{p-1} \cdot (2^p - 1)$.
(If $2^p - 1$ were not prime, there would be other divisors besides $2^p - 1$ to worry about.) In order to add
up all these divisors, we use the formula for the sum of a geometric series:
$$ 1 + r + r^2 + r^3 + ... + r^k = \sum_{i=0}^{k}{r^k} = \frac{r^{k+1} - 1}{r - 1}$$
In this case, we have $r = 2$ and $k = p - 1$, so that the powers of 2 from $1$ to $2^{p-1}$ sum to $S = \frac{2^{p-1 + 1}-1}{2-1}
= 2^p - 1$; meanwhile we note that the divisors
containing $2^p - 1$ correspond to the same series multipled by $2^p - 1$, so that the sum of all the divisors is equal to
$$\sigma(n) = S + (2^p - 1)S = S + S^2 = S (1+S)$$
But by the definition of $S = 2^p - 1$, we thus also know that $n = 2^{p-1} \cdot (2^p - 1) = \frac{S+1}{2} S$, and so
$$\sigma(n) = S(1+S) = 2n$$
thus $n$ is indeed a perfect number.
Proving the converse is slightly more involved, but it will be done in short order. Note that these perfect
numbers are even; it is still an open mathematical problem of some interest whether or not there are any odd
perfect numbers (most mathematicians believe not).

Now we've got a handle on numbers where $a(n) = n$, but what about other numbers? Well, lets try a
prime number. Let $p$ be any prime number; then its only divisors (by definition) are $1$ and $p$, so
$\sigma(p) = p + 1$, and consequently $a(p) = \sigma(p) - p = 1$. (What's $a(1)$? Only $1$ divides $1$, so
$a(1) = 1 - 1 = 0$. Meanwhile, $a(0)$ is not defined because it makes no sense to talk about the divisors of 0.)
Well, that's interesting. Is it possible for $a(n)$ to be prime? Yes, for example, $a(4) = 1 + 2 + 4 - 4 = 3$.
So we see
that $a(a(4))$ = 1. Does this work for other numbers? Sure. Let's try 12: $a(12) = 1 + 2 + 3 + 4 + 6 = 16$ (note
that in this case $a(n) \gt n$). Next, $a(16) = 1 + 2 + 4 + 8 = 15$, and $a(15) = 1 + 3 + 5 = 9$, and $a(9) = 1
+ 3 = 4$, and as we discussed, $a(4)$ is prime and thus $a(a(4)) = a(a(a(a(a(a(12)))))) = 1$. This iterated
aliquot function application is called an **aliquot sequence**, and they are the main objects of interest on
this page.

And so we've seen that the aliquot sequence starting at $12$ **terminates** with the prime number $3$, and in turn $1$. Are there other
ways an aliquot sequence can terminate? As it turns out, yes: consider $n = 220$. In order to calculate
$a(220)$, we must first factor 220. This is fairly straight forward: $220 = 22 \cdot 10 =
2 \cdot 11 \cdot 2 \cdot 5 = 2^2 \cdot 5 \cdot 11$. So its divisors include 1, 2, 4, 5, 11, 10, 20, 22, 44, 55,
110, and 220; these (save for 220 itself) sum to 284. And so we continue: what is $a(284)$? Well there is a
surprise in store here, for in fact $284 = 2^2 \cdot 71$, and $1 + 2 + 4 + 71 + 142$ is actually *220* once
again! So $a(220) = 284$, and simultaneously $a(284) = 220$. These are called **amicable numbers**, and they
demonstrate that it's possible for aliquot sequences to "terminate" without "reaching" a prime (and thus 1).
Amicable numbers are an example of **aliquot cycles** of order 2; higher order cylces exist, whose members are
called **sociable numbers**. Examples include the
cycle starting with $n=12496$: $a(12496) = 14288$, $a(14288) = 15472$, $a(15472) = 14536$, $a(14536) = 14264$,
and finally $a(14264) = 12496$, for a cycle of order 5. There are several million amicable pairs known, 225
cycles of order 4 known, the sole cycle above known of order 5, five cycles of order 6, three cycles of order 8,
one cycle of order 9, one curious cycle of order 28, and perhaps strangely, no cycles whatsoever of order 3.
We could arguably classify perfect numbers as aliquot cycles of order 1 -- there are
48
49 known Mersenne primes, and thus 49 known cycles
of order 1.

And now, the big question. Are there numbers which commence an aliquot sequence that never terminates? That is, is there an aliquot sequence which never has a prime term and which never reaches a repeating cycle (of order 1, 2, or otherwise)? Such a sequence would, by necessisity, grow without bound. This question is known as Catalan's aliquot sequence conjecture, and it remains open to this day. (Catalan specifically conjectured that all aliquot sequences terminate, which is to say, are bounded in size.) The smallest number whose aliquot sequence is as yet not known in its entirety is 276; as of writing, it has 2044 terms, with the last terms having more than 200 digits. (As a small fun fact milestone, the first sequence to reach 200 digits was 2340 on January 28th 2016, by Tom Womack.) The rest of this page is dedicated to analysis of aliquot sequences as it relates to the ongoing computational research into unknown sequences.

Now that we've defined $\sigma$ and $a$, it's time to take a small detour and learn about multiplicative functions. They are of large importance in elementary number theory, and we shall make use of their defining property quite a lot while studying $\sigma$.

Definition: a number-theoretic function on integers $f$ is called **multiplicative** if, for any integers
$m$ and $n$ where $gcd(m, n) = 1$, $f(m \cdot n) = f(m) \cdot f(n)$. (By extension, $f$ is called **completely
multipicative** if the property holds even when $m$ and $n$ share some divisors.) For example: the identity
function, $f(x) = x$, is multiplicative (in fact completely so) for $f(xy) = xy = x \cdot y = f(x) \cdot f(y)$.

Our goal now is to prove that $\sigma$, the sum of divisors function, is also multiplicative. This will allow us to deduce a great deal of other things about $\sigma$. In fact, the multiplicativity of $\sigma$ follows trivially from a simple, general and incredibly useful helper theorem: given a multiplicative function $f$, define a new function $$F(n) = \sum_{d \mid n}{f(d)}$$ as the sum of $f$ applied to the divisors of $n$; then $F$ too is multiplicative.

Proof: Let $m$ and $n$ again share no common factors (besides $1$).
Then the divisors $d$ of $mn$ may be written as $d = rs$, where $r \mid m$ and $s \mid n$, and $gcd(r, s) = 1$
(which follows from $gcd(m, n) = 1$). And so:
$$F(mn) = \sum_{d \mid mn}{f(d)} = \sum_{r \mid m, s \mid n}{f(rs)} = \sum_{r \mid m, s \mid n}{f(r) f(s)}$$
where the last equality follows from the multiplicativity of $f$. Now, note the range
of the sum -- $r$ and $s$ *independently* range over the divisors of $m$ and $n$ respectively (since
$gcd(r, s) = 1$), with one term in the sum for each possible product of $r$ and $s$, and so we notice the sum may
be written as a rectangular "cross table" of terms: the divisors $r$ of $m$ label the columns, the divisors $s$
of $n$ label the rows, and the term at column $r$ and row $s$ is $f(r) \cdot f(s)$. But consider
$$F(m) F(n) = \left(\sum_{r \mid m}{f(r)}\right) \left(\sum_{s \mid n}{f(s)}\right) $$
By distributing the terms of one sum over the other, this product is in fact the sum of all possible products of
terms -- all possible products of $f(r)$ and $f(s)$. But these are exactly the terms that comprise our cross
term table from before! And so $$F(m) F(n) = \sum_{r \mid m, s \mid n}{f(r) f(s)} = F(mn)$$ and the
multiplicativity of $F$ follows from that of $f$, as desired.

This theorem has a number of immediate corollaries, two of which are as follows: the count of divisors of a number, label it $\nu(n)$, is multiplicative, for $\nu(n) = \sum_{d \mid n}{1}$, and $f(x) = 1$ is trivially multiplicative, so $\nu$ is as well. Our close friend $\sigma(n)$ is also multiplicative, for $\sigma(n) = \sum_{d \mid n}{d}$, where the function of the divisors is just the identity function, which we also know is multiplicative, and so $\sigma$ is as well.

Now we use multiplicativity to deduce some properties of $\nu$ and $\sigma$. Most importantly, it suffices to know a multiplicative function's value over powers of primes, since all integers uniquely factor as a product of prime powers (which are by definition mutually coprime). As an example: let $p$ be any prime number, and let $a$ be a positive integer. Then $\nu(p) = 2$ (all primes have exactly two divisors) and $\nu(p^a) = a + 1$ (powers of prime numbers have as many divisors as the power plus one). Now we consider any integer $n$, which can be factored as $$n = \prod_{p_i \mid n}{{p_i}^{a_i}}$$ Then $$\nu(n) = \nu\left(\prod_{p_i \mid n}{{p_i}^{a_i}}\right) = \prod_{p_i \mid n}{\nu\left({p_i}^{a_i}\right)} = \prod_{p_i \mid n}{(a_i + 1)}$$ (That is, take the powers of the primes dividing $n$, add one to each power, and multiply those all together to get $\nu(n)$. The middle equality follows from the multiplicativity of $\nu$.) And now we apply the same process to $\sigma$: $\sigma(p) = p + 1$, and $\sigma(p^a) = \sum_{d \mid p^a}{d} = \sum_{i=0}^{a}{p^i}$, which by the sum of geometric series is $\frac{p^{a+1}-1}{p-1}$, and so $$\sigma(n) = \sigma\left(\prod_{p_i \mid n}{{p_i}^{a_i}}\right) = \prod_{p_i \mid n}{\sigma\left({p_i}^{a_i}\right)} = \prod_{p_i \mid n}{\frac{{p_i}^{{a_i}+1}-1}{{p_i}-1}}$$ (where the middle equality again follows from multiplicativity). So in general, to calculate $\sigma(n)$ and in turn $a(n)$, it suffices to factor $n$ into its constituent prime powers, after which $\sigma(n)$ is only a few multiplications (as opposed to actually enumerating every single possible divisor, which can take a long time if there lots of prime factors). Of course factoring an integer is in general difficult, but that is currently the best known method to calculate $\sigma(n)$ (after all, it's hard to calculate the sum of divisors without knowing the divisors).

Finally, we conclude this detour by applying our newfound properties of $\sigma$ to the discussion of even
perfect numbers. First we note that the statement we already proved about even perfect numbers can be proven
again in a much simpler manner using $\sigma$: let $n = 2^{p-1} \cdot (2^p-1)$, where $2^p-1$ is prime. Then
$$\sigma(n) = \sigma(2^{p-1} \cdot (2^p -1)) = \sigma(2^{p-1}) \cdot \sigma(2^p-1) =
(2^p-1) \cdot 2^p = 2 \cdot 2^{p-1} \cdot (2^p-1) = 2n$$
and $n$ is perfect. The proof of the converse is due to Euler and
is as follows: let $n$ be an even perfect number, and write $n = 2^b \cdot m$ for some $b \geq 1$ with $m$ odd.
Then
$$2^{b+1} \cdot m = 2n = \sigma(n) = \sigma(2^b \cdot m) = \sigma(2^b) \cdot \sigma(m) = (2^{b+1}-1) \cdot \sigma(m)$$
Note that since $(2^{b+1}-1)$ is odd, it must divide the odd $m$ on the other side of the equation. We thus define
$$l = \frac{m}{(2^{b+1}-1)}$$
Also note that since $b \ge 1$, then $2^{b+1}-1 \ge 3$, and thus $l$ is a *proper* divisor of $m$.

Next we isolate $\sigma(m)$ and replace the terms with $2^{b+1}$ by $\frac{m}{l} + 1$ (obtained by rearranging
the definition of $l$):
$$ \sigma(m) = 2^{b+1} \cdot \frac{m}{2^{b+1}-1} = (\frac{m}{l} + 1) \cdot l = m + l$$
This is the fundamental deduction of the proof, for that equality $$\sigma(m) = m + l$$ precisely means that $l$ *is the only proper
divisor of* $m$. Thus we conclude a number of things, namely that 1) $l = 1$, 2) $m$ is prime, 3)
$m = 2^{b+1}-1$, and collectively that our even perfect number $n = 2^b \cdot m$ is of the form $2^b \cdot (2^{b+1}-1)$ with
$2^{b+1}-1$ a Mersenne prime, which is what we set out to prove.

Before we get to the meat of the page, lets first talk about some types of sequences that aren't of great importance to the computational search of sequences, and what makes them relatively unimportant.

To begin with, after having already defined perfect numbers, we now classify all other numbers similarly:
Let $n$ be any integer. If $a(n) \gt n$, then $n$ is said to be **abundant**. As we already discussed, if
$a(n) = n$, $n$ is **perfect**, and if $a(n) \lt n$, $n$ is **deficient**.

We can get a sense of these properties by examining $a(n)$ for $n$ in some relatively large range, say, $10^5$ to $10^6$. Although we won't detail it here, suffice it to say that some patterns emerge:

- Odd numbers tend to be deficient
- Even numbers tend to be abundant, though perhaps less strongly than odds are deficient
- If $n$ is even, so is $a(n)$
- If $n$ is odd, so is $a(n)$

Now we come to deficiency and abundancy. First, we define the **abundance** of a number to be
$$\alpha(n) = \frac{a(n)}{n}$$ so that deficient numbers have abundance less than 1, perfect numbers have
abundance 1, and abundant numbers have abundance greater than 1. Lets develop a sense for how the prime factors
of a number affect its abundance. First, denote the divisors of $n$ as $d_i$, where $i$ runs from
$1$ to $k$, where $k$ is the number of divisors, such that $d_1 = 1$ and $d_k = n$. Note that by construction,
$n/d_i = d_{k-i+1}$. Then:
$$\alpha(n) = \frac{a(n)}{n} = \frac{1}{n} \sum_{i=1}^{k-1}{d_i} = \sum_{i=1}^{k-1}{\frac{d_i}{n}} =
\sum_{i=1}^{k-1}{\frac{1}{d_{k-i+1}}} = \sum_{i=2}^{k}{\frac{1}{d_i}}$$
Thus abundance is the sum of the inverse of the divisors greater than $1$, including $n$ itself. Obviously the
smallest divisors dominate the sum, i.e. a divisor of $x$ digits affects the abundance in only the $x$th decimal
place. Heuristically then, we can get a powerfully close approximation to the abundance of a number just by
knowing a few of its smallest divisors. One example: let $n = 2 \cdot 3 \cdot 5 \cdot 54673257461630679457$. A
first approximation to the
abundance of $n$ is $\frac{1}{2} + \frac{1}{3} + \frac{1}{5} = 1.03\bar{3}$; a second approximation includes the
small divisors that are product of the three small primes (i.e. the exact abundance of $2 \cdot 3 \cdot 5 = 30$):
$\frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \frac{1}{6} + \frac{1}{10} + \frac{1}{15} + \frac{1}{30} =
\frac{7}{5} = 1.4$. The last terms to include in the full abundance are $\frac{1}{54673257461630679457}$,
$\frac{1.4}{54673257461630679457}$, and $\frac{1}{30 \cdot 54673257461630679457}$, which are 1.83e-20, 2.56e-20, and 6.10e-22 respectively, meaning the actual abundance is roughly 1.4000000000000000000445, which is actually
beyond the precision that standard double-sized floating point numbers can represent.

Knowing now that the smallest factors of a number largely determine its abundance, it's easy to see why most even numbers are abundant: all of them have an abundance of at least $\frac{1}{2}$, and any further powers of two or a couple more small primes will push the abundance over 1 in a pinch. Conversely, odd numbers have no guaranteed small factor: if an odd number's smallest prime factor is, say, 101, then unless there are hundreds or thousands of other divisors of this number, the abundance will certainly be less than 1. For example, these are the five smallest odd abundant numbers:

- $945 = 3^3 \cdot 5 \cdot 7$
- $1575 = 3^2 \cdot 5^2 \cdot 7$
- $2205 = 3^2 \cdot 5 \cdot 7^2$
- $2835 = 3^4 \cdot 5 \cdot 7$
- $3465 = 3^2 \cdot 5 \cdot 7 \cdot 11$

(As an aside, it's easy to see
how abundance and deficiency are related to the concepts of **smooth** and **rough** numbers, which
are defined as those numbers with their largest prime divisor smaller than a bound B, or the smallest prime
divisor larger than B, respectively. Of course, the modified definitions of **powersmoothness** are more
relevant to our discussion, where all prime powers dividing the number must be less than the bound B. If we
define $b(n)$ to be the smallest number B such that $n$ is **B-powersmooth**, then there is a very close
correlation between $a(n)/n$ and $n/b(n)$ -- though the former arguably accounts better for the cases where
there are several high powers of multiple primes, instead of just one prime with a large exponent "inflating"
$b(n)$.)

At any rate, we've beaten to death the subject of abundance. We'll finish up with a couple further small but important properties of abundance. The main property in question is that $\alpha(mn) \gt \alpha(n)$, i.e. the abundance of a number is greater than the max of the abundance of any of its divisors. This is immediately evident from the above discussion: $mn$ has at least the divisors that $n$ has (such that $\alpha(mn) \ge \alpha(n)$), while guaranteeing the additional divisor $mn$ to be included in the sum of inverse divisors, such that $\alpha(mn) \ge \alpha(n) + \frac{1}{mn} \gt \alpha(n)$, as desired.

This propery of the aliquot abundance function has two immediate corrolaries: first, if $mn$ is perfect or deficient,
then $ 1 \geq \alpha(mn) \gt \alpha(n)$, so any divisor of $mn$ is itself deficient. Second and more
importantly, if $n$ is perfect or abundant, then $1 \leq \alpha(n) \lt \alpha(mn)$ for any $m$, so
any multiple of $n$ is also abundant. This latter property is the bane of sequence extenders
everywhere. Odd sequences are (to the best of my knowledge) merely composed of essentially random odd numbers,
the large majority of which are deficient, and so there is not currently known an unterminated odd sequence with a
substantial number of its terms abundant. Even sequences, on the other hand, do *not* have random terms, and as
the next secion discusses, even sequences follow patterns, where nearly all of the patterns guarantee a particuar perfect
or abundant number to occur in *every* line of the sequence -- thus, according to the prior property, guaranteeing
nearly every term is (substantially) larger than the previous one, growing quickly and without bound (with one primary
exception). This is the main reason that many people suspect Catalan's aliquot conjecture to be false. Quantifiers the
whys and wherefores of these patterns (and how they change) is the goal of the next section.

Finally we can start talking about the details of aliquot sequences as it pertains to the ongoing brute force sequence calculations. As above, odd sequences terminate quickly and are of no interest, so from now on we only deal with even numbers.

As a first step, if we were to pick a random even number and let it run for several terms, we notice that in most cases, there are some primes (other than 2!) that are consistently a factor in every term of the sequence. One such prototypical example is $n = 759679647438 = 2 \cdot 3 \cdot 47 \cdot 1039 \cdot 2592781$. The next five terms in its aliquot sequence are:

- $2 \cdot 3 \cdot 863 \cdot 153244589$
- $2 \cdot 3 \cdot 11^2 \cdot 47 \cdot 131 \cdot 177929$
- $2 \cdot 3 \cdot 11 \cdot 509 \cdot 29884333$
- $2 \cdot 3 \cdot 211067 \cdot 940279$
- $2 \cdot 3 \cdot 7 \cdot 28352024341$

- $2^5 \cdot 3 \cdot 5 \cdot 7 \cdot 43 \cdot 2861 \cdot 1566239$
- $2^5 \cdot 3 \cdot 5^2 \cdot 7 \cdot 56813 \cdot 1821263$
- $2^5 \cdot 3 \cdot 7 \cdot 257 \cdot 6211 \cdot 4408039$
- $2^5 \cdot 3 \cdot 7 \cdot 59 \cdot 239966328113$
- $2^5 \cdot 3 \cdot 7^2 \cdot 19 \cdot 218315230841$

Notice how $2^5 \cdot 3 \cdot 7$ divides every term (while the smaller prime 5 stays for a couple terms but then
disappears). Why does this happen? The answer, as it turns out, lies in the sum of the divisors of the power of
two. Indeed, $\sigma(2^b) = 2^{b+1}-1$ is odd. Let $v$ be any (odd!) non-trivial divisor of $\sigma(2^b)$, and
then write $n$ in the form $n = 2^b \cdot v \cdot m$, where the odd part of $n$ is split into the parts which
divide $\sigma(2^b)$, i.e. $v$, and the parts that don't, $m$. Then
$$\sigma(n) = \sigma(2^b) \cdot \sigma(v) \cdot \sigma(m) = (2^{b+1}-1) \cdot \sigma(v) \cdot \sigma(m)$$
and also
$$a(n) = (2^{b+1}-1) \cdot \sigma(v) \cdot \sigma(m) - 2^b \cdot v \cdot m$$
We don't know a priori what the power of 2 in $a(n)$ is, but for now we'll note that, as according to the
examples above, it's very likely to stay the same. Now since $v \mid \sigma(2^b)$ by definition, we have that
$v \mid \sigma(n)$, as well as $v \mid n$ (vacuously). Therefore $v$ divides their difference:
$$v \mid (\sigma(n) - n) = a(n)$$
This means that $v$, consisting of any prime factors of $\sigma(2^b) = 2^{b+1}-1$, are guaranteed to perpetuate
from term to term (as long as the power of 2 stays the same, which we'll get to shortly). This motivates the
following definition: a number of the form $2^b \cdot v$, where $v$ divides $\sigma(2^b)$, is called a
**guide**. (Note that when $v=1$, the guide is just the power of 2.) Guides are the bread and butter of the
study of even aliquot sequences. Here are the first six powers of 2 and the resulting possible guides:

Even power | $\sigma(2^b)$ | Guide | Abundance |
---|---|---|---|

$2^1$ | $3$ | $2\cdot 3$ | $1$ (perfect) |

$2$ | $\frac{1}{2}$ (deficient) | ||

$2^2$ | $7$ | $2^2 \cdot 7$ | $1$ (perfect) |

$2^2$ | $\frac{3}{4}$ (deficient) | ||

$2^3$ | $3 \cdot 5$ | $2^3 \cdot 3 \cdot 5$ | $2$ (abundant) |

$2^3 \cdot 3$ | $\frac{3}{2}$ (abundant) | ||

$2^3 \cdot 5$ | $\frac{5}{4}$ (abundant) | ||

$2^3$ | $\frac{7}{8}$ (deficient) | ||

$2^4$ | $31$ | $2^4 \cdot 31$ | $1$ (perfect) |

$2^4$ | $\frac{15}{16}$ (deficient) | ||

$2^5$ | $3^2 \cdot 7$ | $2^5 \cdot 3 \cdot 7$ | $2$ (abundant) |

$2^5 \cdot 3$ | $\frac{13}{8}$ (abundant) | ||

$2^5 \cdot 7$ | $\frac{5}{4}$ (abundant) | ||

$2^5$ | $\frac{31}{32}$ (deficient) | ||

$2^6$ | $127$ | $2^6 \cdot 127$ | $1$ (perfect) |

$2^6$ | $\frac{63}{64}$ (deficient) |

Hopefully this makes sense -- with any small primes to go with the powers of 2, the guide immediately becomes abundant and thus the sequence will increase. And note further that the higher powers of 2, even without any small primes, are very nearly abundant anyways -- not much help. About the only way to send a sequence consistently down is to catch and keep the sole $2$ guide. ($2^2$ tends to decrease on average, but not by much -- $2^3$ roughly averages no decrease or increase, while higher powers of 2 increase very slowly on average.)

As a final note on guides, let $v' \gt 1$ be a prime divisor of $\sigma(2^b)$ that doesn't divide $n = 2^b \cdot v \cdot m$. Therefore $v' \mid \sigma(n)$, but $v' \nmid n$, and therefore $v'$ a priori doesn't divide $a(n)$. What this means is that just as $2^2 \cdot 7$ can't lose the 7 (without the power of 2 changing), nor can $2^2$ gain a factor of 7 to become $2^2 \cdot 7$ (again, assuming the power of 2 doesn't change). As another example, just as $2^3 \cdot 3$ can't lose the 3 to become just $2^3$, nor can $2^3 \cdot 3$ gain the 5 to become $2^3 \cdot 3 \cdot 5$. And so the only possible way for a guide to change is if the power of 2 changes, which brings us directly to the next section.

The next question of course, is when and how the power of 2 changes. Recall earlier when we were talking about
guides that, when noting that $2^b \cdot v \mid a(2^b \cdot v \cdot m)$, we only assumed that $2^b \mid a(2^b
\cdot v \cdot m)$ (as is nearly always the case) in order to perpetuate the guide. If the power of 2 changes, then
$v$ no longer divides $\sigma(2^{b'})$, and we have a new guide based on $2^{b'}$ instead of $2^b$. For example,
let $n = 2^5 \cdot 5 \cdot 7 \cdot 13$. Then $b = 5$ and $v = 7$, and $a(n) = 2^7 \cdot 7 \cdot 31$. Although $v$
does indeed divide $a(n)$, the power of 2 changed and thus the $2^5 \cdot 7$ guide was lost, transforming into
$2^7$. (In this case, $\sigma(2^7) = 3 \cdot 5 \cdot 17$, so fortunately $v = 1$ in the new guide.) We call these
changes in the power of 2 **mutations**.

Before delving headlong into the whys and hows of mutations, lets take a detour to define a few functions which
shall make our bookkeeping easier. Let $n$ be a number of the form $2^b \cdot m$, where $m$ is odd (and $b = 0$
is allowed). Then we define $$f(2^b \cdot m) = 2^b$$ i.e. $f$ is the largest power of 2 that divides $n$. Note
that it is completely multiplicative ($f(kl) = f(k)f(l)$ for any $k$ and $l$). Next we define $$\beta(n) =
\log_2(f(n))$$ i.e. the exponent of the largest power of 2 in $n$. Being the logarithm of a completely
multiplicative function, note that $\beta(kl) = \beta(k) + \beta(l)$ for any $k$ and $l$. Finally, and this is
the point of this diversion, we define $$\tau(n) = \beta(\sigma(n))$$ i.e. the exponent of 2 in $\sigma(n)$.
This is called the **twos count** of $n$, and it plays an important role in aliquot sequence mutations. (Note
that the author thinks that "twos count" is perhaps more appropriate for $\beta$ than for $\tau$, but this name
has already been applied to $\tau$ by others far more expert than the author. A point in favor of this name is
that it then makes sense to talk about twos counts of primes, e.g. "the twos count of 7 is 3".) Finally, we note
that $\tau$ is "logarithmically multiplicative", analogously to $\beta$: whenever $k$ and $l$ are coprime,
$$\tau(kl) = \beta(\sigma(kl)) = \beta(\sigma(k)\sigma(l)) = \beta(\sigma(k))+\beta(\sigma(l)) =
\tau(k)+\tau(l)$$ (Note that if $f$ were not completely multiplicative, we could not conclude that $\tau$ is
logarithmically multiplicative, since we don't know that $\sigma(k)$ and $\sigma(l)$ are coprime.) As an
example, $\tau(5) = \beta(\sigma(5)) = \beta(6) = \beta(2^1\cdot3) = 1$. Meanwhile, $\tau(11) =
\beta(\sigma(11)) = \beta(12) = \beta(2^2 \cdot 3) = 2$, and finally, by the "multiplicativity" of $\tau$, we thus
have that $\tau(55) = \tau(5\cdot11) = \tau(5)+\tau(11) = 1+2=3$ (which we can verify by noting that $\sigma(55)
= 2^3\cdot3^2$). The final stop on the detour is the following criterion for $\beta$: $\beta(n) = x$ means that
$2^x \mid n$, but $2^{x+1} \nmid n$ -- a simple way to quantify this is that $n \equiv 2^x \pmod{2^{x+1}}$,
which is equivalent to $\beta(n) = x$.

Now we can dive head first to the bottom of the pool. In this paragraph we write $n$ in the usual form $2^b \cdot v \cdot m$, $m$ odd, where by definition of $v$, it and $m$ are coprime. A mutation occurs when the power of two changes, which means we want to know what circumstances of $n$ and $a(n)$ cause $\beta(a(n)) \neq \beta(n) = b$.

Proceeding directly: $$\beta(a(n)) = \beta(\sigma(n)-n)$$ We need some way to relate $\beta$ of a sum to $\beta$ applied to the summands. Fortunately, this is straightforward: let $x$ and $y$ be two numbers of the form $2^i \cdot k$ and $2^j \cdot l$, where $k$ and $l$ are odd. Without loss of generality, lets assume that $i \leq j$. Then $x+y = 2^i(k + 2^{j-i}l)$. If $i \neq j$, then $(k + 2^{j-i}l)$ is odd and so $\beta(x+y) = i = \min(\beta(x), \beta(y))$. Otherwise if $i=j$, then $x+y = 2^i(k+l)$, where $k+l$ is thus even and $\beta(x+y) \gt i=j$. Unfortunately we can't say more about that case without knowing more about $m$ and $l$ (though fortunately it doesn't matter much). Note that these same conclusions apply to $x-y$.

Applying these results to $\beta(a(n)) = \beta(\sigma(n) - n)$, we see that if $\beta(\sigma(n)) = \tau(n) \gt b$, then $\beta(a(n)) = \min(\tau(n) \gt b, b) = b$ and no mutation occurs.

If $\tau(n) = b$, then $\beta(a(n)) > b$, and a mutation occurs like in the example at the beginning of the section, where the power of 2 increases (how much it increases again depends on the odd parts of $n$ and $\sigma(n)$).

Finally, if $\tau(n) \lt b$, then $\beta(a(n)) = \min(\tau(n) \lt b, b) = \tau(n)$ and again we have a mutation, this time where the exponent decreases to $\tau(n)$. The criterion for a mutation occuring, then, is that $$\tau(n) \leq b .$$

In order to proceed further, we have to have an idea what $\tau(n)$ looks like for an arbitrary number $n$. In particular, in the fashion of $\sigma$ and $\nu$ oh so long ago, we calculate $\tau(p^a)$ for an arbitrary prime number $p$. But $\tau$ turns out to not be quite so straightforward as $\sigma$ or $\nu$, so we'll start with primes themselves, not prime powers. In particular, let $p$ be an odd prime. ($\sigma(2^a)=2^{a+1}-1$ is odd, so $\tau(2^a)=0$ and so we restrict our study to odd primes.) Then $\sigma(p)=p+1$, and we need to calculate $\beta(p+1)$. By the criterion for $\beta$ described previously, we have that $$\beta(p+1)=x \iff p+1 \equiv 2^x \pmod{2^{x+1}}$$ whence we know that $$\tau(p) = x \iff p \equiv 2^x-1 \pmod {2^{x+1}}$$ (This can be calculated in an algorithmic manner by testing succesive $x$ starting with $x=1$; of course, practically speaking, it's simpler to merely count the trailing zero bits in the binary representation of $p+1$ than to search for $x$ in this manner.) Now we can move on to prime powers. First, recall from the beginning of the page that $\sigma$ of a perfect square is odd. That is, whenever $a$ is even, $\sigma(p^a)$ is odd, and thus $$\tau(p^{2k}) = \beta(\sigma(p^{2k})) = 0$$ This turns out to be a boon when it comes to breaking certain guides, as we'll later deduce.

Otherwise, if $a$ is odd and $a\gt1$, then we define $a=2k+1$ and write $$\sigma(p^a) = \sum_{j=0}^a{p^j} = \sum_{i=0}^{k}({p^{2i}+p^{2i+1})}$$ Consider the powers of $p \pmod {2^{x+1}}$. By the previous criterion, we have that $p \equiv 2^x - 1 \pmod {2^{x+1}}$. By simple computation, $$p^2 \equiv 2^{2x} - 2^{x+1} + 1 \pmod{2^{x+1}}$$ where the former two terms are congruent to 0. So $$p^2 \equiv 1 \pmod{2^{x+1}}$$ and so $p^3 \equiv p$ and inductively we have $$p^{2i} + p^{2i+1} \equiv 1 + p \equiv 2^x \pmod {2^{x+1}}$$ This motivates us to factor out the $(1 + p)$, for indeed $$(p^{2i} + p^{2i+1}) = (1+p)\cdot p^{2i}$$ so that $$\sigma(p^a) = (1+p) \cdot \sum_{i=0}^{k}{p^{2i}}$$ where this sum has $l = k+1$ terms. So we have that $$\tau(p^a) = \beta(1+p) + \beta(\sum_{i=0}^{k}{p^{2i}})$$ Now the trick is to perform this pairing and factoring process again -- for $$(p^{2i} + p^{2i+2}) = (1+p^2)\cdot p^{4i}$$ and in turn $$\sum_{i=0}^{l-1}{p^{2i}} = (1+p^2) \cdot \sum_{i=0}^{l'-1}{p^{4i}}$$ where $l' = l/2$. But the key observation is that we can only repeat this process as long as $l$ and $l'$ in turn are even -- as soon as we are left with an odd number of terms, we can no longer pair terms, and further we know that the sum is itself odd. In general then, we can perform this pairing and factoring $y = \beta(l)$ times (where again, $a = 2l-1$). We can then write $$\sigma(p^a) = (1+p) \cdot (1+p^2) \cdot (1+p^4) \cdot \ldots \cdot (1+p^{(2^y)}) \cdot \sum_{i=0}^{l_y-1}{p^{(2^{y+1}\cdot i)}}$$ (with $l = 2^y \cdot l_y$), where the last sum has an odd number of terms since $l_y$ is odd. We may then apply the logarithmic multiplicativity of $\beta$: $$\beta(\sigma(p^a)) = \beta(p+1) + \beta(1+p^2) + \beta(1+p^4) + \ldots + \beta(1+p^{2^y}) + 0$$ where the previous sum over $p^{(2^{y+1}\cdot i)}$ contribues nothing because it is odd. Now we note that since $p^{2i} \equiv 1 \pmod{2^{x+1}}$, we have that $$1+p^{2i} \equiv 2 \pmod{2^{x+1}} \implies \beta(1+p^{2i}) = 1$$ and since we have $y=\beta(l)$ such terms, then finally $$\tau(p^a) = \beta(\sigma(p^a)) = \beta(p+1) + \beta(l) = \tau(p) + \beta(\frac{a+1}{2})$$ (Note that this argument applies to any geometric sum with an odd ratio -- the only difference is that if the ratio isn't prime, we instead note that any odd perfect square satisfies $r^{2i} \equiv 1 \pmod{8}$ [since $3^2 \equiv 5^2 \equiv 7^2 \equiv 1 \pmod{8}$], instead of the stronger statement that $p^{2i} \equiv 1 \pmod{2^{x+1}}$, but that still implies that $\beta(1+r^{2i}) = 1$, as necessary.)

Now that we know how to calculate $\tau(p^a)$, we can come back to our criterion for mutation: $$\tau(n) \leq b$$
We now recall that $\tau(kl) = \tau(k)+\tau(l)$ when $k$ and $l$ are coprime, and expand $$\tau(n) = \tau(2^b
\cdot v \cdot m) = \tau(2^b) + \tau(v) +\tau(m)$$ But we know the prime powers composing $v$ and $m$, and in
particular we know that even-powered primes contribute nothing to the sum in $\tau(n)$. Thus we define the
**canonical form** of an aliquot sequence as follows: $$n = 2^b \cdot v \cdot s \cdot t$$ where $v$ consists
of the (powers of) primes that divide $\sigma(2^b)$; $s$ consists of the powers of all other primes whose
exponent is even, and $t$ is everything else, the odd-powered primes that don't divide $\sigma(2^b)$. (For
example, let $n = 697099605116255176680532531614820 = 2^2 \cdot 5 \cdot 7^3 \cdot 347^2 \cdot 683 \cdot 919^4
\cdot 1201^3$. Then $b=2$, $v=7^3$, $s=347^2 \cdot 919^4$, and $t=5\cdot 683 \cdot 1201^3$.) Then $$\tau(n) =
\tau(2^b \cdot v \cdot s \cdot t) = \tau(2^b) + \tau(v) + \tau(s) + \tau(t)$$ But as before, we know that
$\tau(2^b) = 0$, and furthermore, since $s$ consists only of even-powered primes, $\tau(s)$ is also zero. So our
mutation criterion is then $$\tau(n) = \tau(v) + \tau(t) \leq b$$ But $v$ are the primes which compose the guide,
which is guaranteed to perpetuate, so the only part of the inequality that changes from term to term of the
sequence is $t$, and so we semantically write $$\tau(t) \leq b - \tau(v)$$ where the right side is determined
only by the guide at hand.

Now we're getting somewhere. We can interpret this as follows: any odd prime has a twos count of at least 1,
since $\sigma(p) = p+1$ is even. Furthermore, as we calculated above, an odd prime raised to an odd power has a
twos count at least as big as the prime itself. So, fundamentally, $t$ must be composed of no more than
$b - \tau(v)$ distinct primes, and even that doesn't guarantee a mutation if the primes have a twos count bigger
than one (as roughly half of all primes do). We therefore define the **class** of a guide as $b - \tau(v)$,
where a lower class means $t$ must be composed of fewer primes to cause the sequence to mutate, so lower class
guides are more stable, while higher class guides are more liable to mutate. In particular, if a guide is of
class 1, then *$t$ must consist of only one 1 prime*, and what's worse, if a guide has class 0 or less,
then there is no $t$ whatsoever that will cause the guide to mutate. Fortunately, there's another way to break
these guides, as we'll get into shortly. In the meantime, here's the same table of guides as above, except this
time including their class:

Even power | $\sigma(2^b)$ | Guide | Abundance | Class |
---|---|---|---|---|

$2^1$ | $3$ | $2\cdot 3$ | $1$ (perfect) | $-1$ |

$2$ | $\frac{1}{2}$ (deficient) | $1$ | ||

$2^2$ | $7$ | $2^2 \cdot 7$ | $1$ (perfect) | $-1$ |

$2^2$ | $\frac{3}{4}$ (deficient) | $2$ | ||

$2^3$ | $3 \cdot 5$ | $2^3 \cdot 3 \cdot 5$ | $2$ (abundant) | $0$ |

$2^3 \cdot 3$ | $\frac{3}{2}$ (abundant) | $1$ | ||

$2^3 \cdot 5$ | $\frac{5}{4}$ (abundant) | $2$ | ||

$2^3$ | $\frac{7}{8}$ (deficient) | $3$ | ||

$2^4$ | $31$ | $2^4 \cdot 31$ | $1$ (perfect) | $-1$ |

$2^4$ | $\frac{15}{16}$ (deficient) | $4$ | ||

$2^5$ | $3^2 \cdot 7$ | $2^5 \cdot 3 \cdot 7$ | $2$ (abundant) | $0$ |

$2^5 \cdot 3$ | $\frac{13}{8}$ (abundant) | $3$ | ||

$2^5 \cdot 7$ | $\frac{5}{4}$ (abundant) | $2$ | ||

$2^5$ | $\frac{31}{32}$ (deficient) | $5$ | ||

$2^6$ | $127$ | $2^6 \cdot 127$ | $1$ (perfect) | $-1$ |

$2^6$ | $\frac{63}{64}$ (deficient) | $6$ |

By convention, we call those guides with class less than or equal to 1 **drivers**. This chart illustrates the
bad situation for Catalan's aliquot conjecture: all the most stable guides are precisely the ones that send a
sequence up. The only guide that consistently sends a sequence down is $2$ ($2^2$ also does, but in a much
lesser way); it is called the **downdriver**. Note that all perfect numbers are guides of class -1: if $2^p-1$
is a Mersenne prime, then we already know that $2^{p-1} \cdot (2^p-1)$ is a perfect number; further, the Mersenne
prime is precisely equal to $\sigma(2^{p-1})$, so that the perfect number is in fact a guide, and finally
$\tau(2^p-1) = p$, such that the class is $(p-1) - p = -1$.

The way in which drivers of class $\leq 0$ can be broken (thus leaving open the possibility that Catalan's aliquot conjecture is true) is if one of the primes in $v$ is raised to an even power. In this case, write $v = v' \cdot w$, where $w$ are the primes with an even power, and $v'$ the remainder (in the case of even perfect numbers, $v'$ is necessarily $1$). Then we have $\tau(n) = \tau(v') + \tau(w) + \tau(t) = \tau(v') + \tau(t)$, such that the effective class is now $b - \tau(v') \gt b - \tau(v)$; the class is effectively raised by the twos count of the primes in $v$ whose power is even. Therefore the guide $2^2 \cdot 7^2$ has class $-1 + \tau(7) = 2$ (even though the 7 is still guaranteed to be perpetuated to each term), $2^3 \cdot 3^2 \cdot 5$ has class $0 + \tau(3) = 3 - \tau(5) = 2$, and $2^5 \cdot 3 \cdot 7^2$ has class $3$. Here's some food for thought: the largest known Mersenne prime is currently $M = 2^{74,207,281}-1$, and if we define the corresponding perfect number as $P_M=2^{74,207,280}(2^{74,207,281}-1)$, what are the odds that the sequence starting with $n = 3*P_M$ will ever be divisible by $M^2$, as would be required to make the sequence bounded? Or conversely, given a truly infinite number of iterations, surely even the most unlikely things must eventually happen...

As a final thought, we can use the criterion $\tau(t) \leq$ the class, together with our knowledge of what $\tau$ means, to locate sequences whose last term is currently unfactored, yet which might mutate upon factorization of the line. Such an example would be something like $2^2 \cdot 7^2 \cdot C130$, where C130 means a composite number of 130 digits, and the guide has an effective class of $2$. If we assume that this composite splits into two component primes, each with exponent 1 (as is overwhelmingly likely), then for a mutation to occur, each of those primes must have $\tau(p_1) = \tau(p_2) = 1$ (for if either had $\tau \gt 1$, then $\tau(t) = \tau(p_1) + \tau(p_2) > 2$, and a mutation is guaranteed not to occur). And by the criterion that $\tau(p) = x \iff p \equiv 2^x-1 \pmod{2^{x+1}}$, then we can say that each of the component primes must be $1 \pmod{4}$, and therefore the composite must also be $1 \pmod{4}$. And so if we have several sequences with $2^2 \cdot 7^2 \cdot C$ and we want to find mutations among those sequences, we can eliminate those whose composite is $3 \pmod{4}$. A similar analysis can be made for guides of higher class.

The author currently has at least one question regarding guides. Are there any other guides besides even perfect numbers and $2^3 \cdot 3 \cdot 5$, $2^5 \cdot 3 \cdot 7$, and $2^9 \cdot 3 \cdot 11 \cdot 31$ with class less than 1? Heuristically, one would think not: any prime factor of $\sigma(2^b) = 2^{b+1} - 1$ must have a twos count at most $b-2$ (since $2^b-1$ can't divide $2^{b+1}-1$, and for $b \gt 4$, $b-1 \nmid b+1$, whence $2^{b-1}-1 \nmid 2^{b+1}-1$ [and obviously $3 \cdot 2^{b-1}-1 \nmid 2^{b+1}-1$]), and realistically we can repeat that argument such that for abitrarily large $b$, we can exclude possible twos counts above $b/2$ or something similar, so that the twos count of $\sigma(2^b)$ is almost certainly logarithmically less than $b$.