An Elementary Introduction to Aliquot Sequence Analysis

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.

The sum of divisors function and aliquot sequences (or, the introduction to the introduction)

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.

Some more fundamentals

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.

Abundant and deficient numbers, odd sequences, and basic properties of $a(n)$

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:

Let's try to quantify these statements. We start with parity: first we note that, as $a(n) = \sigma(n)-n$, we need to determine the parity of $\sigma(n)$. To do this, write $n$ as $2^b \cdot m$, with $m$ odd, whence $\sigma(n) = (2^{b+1}-1) \cdot \sigma(m)$. First consider the latter multiplicand: as $\sigma$ is the sum of divisors, we can add their parities to get the parity of $\sigma$. But, we can take a shortcut: since we know $m$ is odd, so are all of its divisors $d$; furthermore, every divisor $d$ has a counterpart, $e = m/d$. Since $d$ and $e$ are odd, their sum is even. Furthermore, except in one special case, every divisor has such a counterpart, and so $\sigma(m)$ is even. The special case is if $m$ is a perfect square (including the case $m=1$), in which case we have that $\sqrt{m}$ is both odd and an unpaired divisor, so $\sigma$ of an odd perfect square is odd. The term $2^{b+1}-1$ is always odd, so we have the following classification: $\sigma(n)$ is odd if and only if the odd part of $n$ is a perfect square. (Another way to say this is $\sigma(n)$ is odd if and only if $n$ is a square or twice a square.) And now we calculate the parity of $a(n)$: since $\sigma(n)$ is almost always even, the parity of $a(n)$ is the same as the parity of $n$, unless the odd part of $n$ is a perfect square, as previously. This confirms our observations and exactly quantifies the exceptions, and since perfect squares are very rare indeed in the computational wild (formally, their density in $\mathbb{N}$ is 0), we shall restrict ourselves to odd sequences or even sequences only.

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:

Note how they are all combinations of powers of the very smallest possible odd primes.

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

Sequence analysis

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:

(After 153 more terms, this sequence terminates as 350 -> 394 -> 200 -> 265 -> 59 -> 1.) Notice how 6 divides every term. Here's another example: let $n = 212046767651040 = 2^5 \cdot 3 \cdot 7 \cdot 5 \cdot 19 \cdot 23 \cdot 101 \cdot 1429847$. Then the next five terms are:

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)$GuideAbundance
$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)$GuideAbundanceClass
$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$.