# Recursively divisible numbers

Thomas Fink

London Institute for Mathematical Sciences, 35a South St, London W1K 2XF, UK
Centre National de la Recherche Scientifique, Paris, France  Divisible numbers
are useful whenever a whole needs to be divided into equal parts. But
sometimes it is necessary to divide the parts into subparts, and subparts into
sub-subparts, and so on, in a recursive way. To understand numbers that are
recursively divisible, I introduce the recursive divisor function: a recursive
analog of the usual divisor function. I give a geometric interpretation of
recursively divisible numbers and study their general properties—in particular
the number and sum of the recursive divisors. I show that the number of the
recursive divisors is equal to twice the number of ordered factorizations into
integers greater than one, a problem that has been much studied in its own
right. By computing those numbers which are more recursively divisible than
all of their predecessors, I recover many of the grid sizes commonly used in
graphic design and digital technologies, and suggest new grid sizes which have
not yet been adopted but should be. These are especially relevant to
recursively modular systems which must operate across multiple organizational
length scales.

##  1\. Introduction

###  1.1. Plato’s ideal city

Consider one of the earliest references to numbers which can be divided into
equal parts in many ways. Plato writes in his _Laws_ [1] that the ideal
population of a city is 5040, since this number has more divisors than any
number less than it. He observes that 5040 is divisible by 60 numbers,
including one to 10. A highly divisible population is useful for dividing the
city into equal-sized sectors for administrative, social and military
purposes.
This conception of divisibility can be extended. Once the city is divided into
equal parts, it is often necessary to divide a part into equal subparts. For
example, if 5040 is divided into 15 parts of 336, each part can in turn be
divided into subparts in 20 ways, since 336 has 20 divisors. But if 5040 is
divided into 16 parts of 315, each part can be divided into subparts in only
12 ways, since 315 has 12 divisors. Thus the division of the whole into 15
parts offers more optionality for further subdivisions than the division into
16 parts. Similar reasoning can be applied to the divisibility of the subparts
into sub-subparts, and so on, in a hierarchical way.
The goal of this paper is to quantify the notion of recursive divisibility and
understand the properties of numbers which possess it to a large degree.

Figure 1. Divisor trees for 1 to 24. The number of recursive divisors $a(n)$
counts the number of squares in each tree and the sum of recursive divisors
$b(n)$ adds up the side lengths of the squares in each tree. Divisor trees can
be generated for any number $n$ at lims.ac.uk/recursively-divisible-numbers.

###  1.2. Modular design

In graphic and digital design, grid systems [2, 3] use a fixed number of
columns or rows which form the primitive building blocks from which bigger
columns or rows are made. For example, a grid of 24 columns is often used for
books [2], and a grid of 96 columns is frequently used for websites [4]. In
exchange for giving up some freedom to choose the size of parts (columns or
rows), the space of possible designs gets smaller, making it easier to
navigate. And the design elements become more interoperable, like how Lego
bricks snap into place on a discrete grid, making it faster to build new
designs.
What are the best grid sizes for modular design? The challenge is committing
to a grid size now that provides the greatest optionality for an unknown
future. Imagine, for example, that I have to cut a pie into slices, to be
divided up later for an unknown number of colleagues. How many slices should I
choose? The answer in this case is relatively straightforward: the best grids
are the ones with the most divisors, such as the highly composite or super-
abundant numbers [5, 6].
But the story gets more complicated when it is necessary to consider multiple
steps into the future. For instance, imagine now that each colleague takes his
share of pie home to further divide it amongst his family. In this case, not
only does the whole need to be highly divisible, but the parts need to be
highly divisible, too. This process can be extended in a hierarchical way.
Design across multiple length scales has long been a feature of graphic
design. For example, newspapers are divided into columns for different
stories, and columns into sub-columns of text. But with the rise of digital
technologies, recursive modularity is becoming the rule. Columns of a website
become the full screen of the same site on a phone. Different regions of the
phone site offer different kinds of functionality, each with its own number of
parts, which may change over time.
What are the design rules for recursive modularity? The state-of-the-art seems
to be artisans’ lore [2, 3, 7], and there is little in the way of quantitative
reasoning. Indeed, my interest in this problem originated in discussions with
designers about the optimal grid size for the London Institute’s website.
This paper gives a mathematical basis for choosing grids that are suitable for
recursive design. It explains the preponderance of certain numbers in graphic
design and display technologies, and predicts new numbers which have not been
used but should be. More generally, it helps us understand recursively modular
systems which must simultaneously operate across multiple organizational
length scales.

###  1.3. Outline of paper

Including this introduction, this paper is divided into five parts. In part 2,
I review the usual divisor function and define the recursive divisor function.
I consider two specific instances of the recursive divisor function: the
number of recursive divisors and the sum of recursive divisors. I introduce
divisor trees (Figure 1), which give a geometrical interpretation of the
recursive divisor function. Using this, I show that the number of recursive
divisors is twice the number of ordered factorizations into integers greater
than one, a problem which has been well-studied in its own right [8, 9, 10,
11, 12]. By examining the internal structure of divisor trees, I find a
relation between the number and sum of recursive divisors.
In part 3, I investigate properties of the number of recursive divisors,
taking advantage of their relation to the number of ordered factorizations. I
give recursion relations for when $n$ is the product of distinct primes, and
for when $n$ is the product of primes to a power. The latter can be written in
closed form for one, two and three primes.
In part 4, I investigate properties of the sum of recursive divisors, which
are more difficult to calculate than the number of recursive divisors in part
3. I give recursion relations for when $n$ is the product of primes to a
power. These can be written in closed form for one, two and three primes by
making use of the relation between the sum and number of recursive divisors in
part 2.
In part 5, I investigate numbers which are recursively divisible to a high
degree. I call numbers with a record number of recursive divisors recursively
highly composite, and list them up to one million. These have been studied in
the context of the number of ordered factorizations [12]. I call numbers with
a record sum of recursive divisors, normalized by $n$, recursively super-
abundant, and also list them up to one million. I list applications of highly
recursive numbers in technology and digital displays, and conclude with a list
of open problems.

##  2\. Recursive divisor function and divisor trees

Throughout this paper I write $m|n$ to indicate $m$ divides $n$ and $m\lfloor
n$ to indicate $m$ is a proper divisor of $n$.

###  2.1. Divisor function

In order to write down a recursive divisor function, I first recall the usual
divisor function,

$\sigma_{x}(n)=\sum_{m|n}m^{x}.$

This sums the divisors of $n$ raised to some integer power $x$.
When $x=0$, the divisor function counts the number divisors of $n$ and is
generally written $d(n)$. It is well known that for

$n=p_{1}^{\alpha_{1}}\,p_{2}^{\alpha_{2}}\ldots p_{j}^{\alpha_{j}},$

where $p_{1},p_{2},\ldots,p_{j}$ are prime,

(1) $d(n)=(1+\alpha_{1})(1+\alpha_{2})\ldots(1+\alpha_{j}).$

Numbers $n$ for which $d(n)$ is larger than that of all of the predecessors of
$n$ are called highly composite numbers and have been extensively studied [5,
6].
When $x=1$, the divisor function sums the divisors of $n$ and is generally
written $\sigma(n)$. It is well known that

$\sigma(n)=\frac{p_{1}^{\alpha_{1}+1}-1}{p_{1}-1}\,\frac{p_{2}^{\alpha_{2}+1}-1}{p_{2}-1}\ldots\frac{p_{j}^{\alpha_{j}+1}-1}{p_{j}-1}.$

Numbers $n$ for which $\sigma(n)/n$ is larger than that of all of the
predecessors of $n$ are called super-abundant numbers and have also been
studied [6].
The quantity $\sigma(n)/n$ can be contrasted with $d(n)$ in the following way.
Highly divisible numbers can be divided into equal-sized parts in many
different ways. But when it comes to practical applications, not all divisions
are equally useful. In general, divisions into fewer parts are more useful
than divisions into many parts, because we are more likely to encounter the
need for fewer parts. In other words, there is a greater need to divide a
region into halves than into thirds, and into thirds than into fourths, and so
on. To give preferential treatment to numbers with smaller divisors, consider
that $d(n)$ awards a point for each divisor of $n$. Now let us give fewer
points for larger divisors. In particular, let us award 1 point for numbers
that can be divided into 1 part (namely, all numbers), $\nicefrac{{1}}{{2}}$
point for numbers that can be divided into 2 parts, $\nicefrac{{1}}{{3}}$
point for numbers that can be divided into 3 parts, and so on. This scheme
gives the score of $\sigma(n)/n$.

###  2.2. Recursive divisor function

In contrast with the usual divisor function, in this paper I am concerned not
only with the divisors of a number $n$ but also the divisors of the resultant
quotients, and the divisors of those resultant quotients, and so on. I
introduce and study the recursive divisor function,

$\kappa_{x}(n)=n^{x}+\sum_{m\lfloor n}\kappa_{x}(m),$

where the sum is over the proper divisors of $n$. When $x=0$, I call this the
number of recursive divisors $a(n)$, and when $x=1$, I call this the sum of
recursive divisors $b(n)$.

######  Definition 1.

The number of recursive divisors is $a(1)=1$ and

$a(n)=1+\sum_{m\lfloor n}a(m),$

where $m\lfloor n$ means $m$ is a proper divisor of $n$.

For example, $a(10)=1+a(1)+a(2)+a(5)=6$. Note that $a(n)$ depends only on the
set of exponents in the prime factorization of $n$ and not on the primes
themselves.

######  Definition 2.

The sum of recursive divisors is $b(1)=1$ and

$b(n)=n+\sum_{m\lfloor n}b(m),$

where $m\lfloor n$ means $m$ is a proper divisor of $n$.

For example, $b(10)=10+b(1)+b(2)+b(5)=20$. Unlike $a(n)$, $b(n)$ depends on
both the exponents and the primes in the prime factorization of $n$.
Ultimately I will be interested in $b(n)/n$, analogous to $\sigma(n)/n$
described above, but for now it is more natural to define and work with
$b(n)$.

###  2.3. Divisor trees

A geometric interpretation of the recursive divisor function $\kappa(n)$ can
be had by drawing the divisor tree for a given value of $n$. Divisor trees for
1 to 24 are shown in Figure 1. The number of recursive divisors $a(n)$ counts
the number of squares in each tree, whereas $d(n)$ counts the number of
squares in the main diagonal. The sum of recursive divisors $b(n)$ adds up the
side lengths of the squares in each tree, whereas $\sigma(n)$ adds up the side
lengths of the squares in the main diagonal. This can be extended to
$\kappa_{2}(n)$, which adds up area, and so on, but in this paper I only
consider $a(n)=\kappa_{0}(n)$ and $b(n)=\kappa_{1}(n)$.
A divisor tree is constructed as follows. First, draw a square of side length
$n$. Let $m_{1},m_{2},\ldots$ be the proper divisors of $n$ in descending
order. Then draw squares of side length $m_{1}$, $m_{2},\ldots$ with each
consecutive square situated to the upper right of its predecessor, kitty-
corner. This forms the main arm of a divisor tree. Now, for each of the
squares of side length $m_{1},m_{2},\ldots$, repeat the process. Let
$l_{1},l_{2},\ldots$ be the proper divisors of $m_{1}$ in descending order.
Then draw squares of side length $l_{1}$, $l_{2},\ldots$, but with the sub-arm
rotated $90^{\circ}$ counter-clockwise. Do the same for each of the remaining
squares in the main arm. This forms the branches off of the main arm. Now,
continue repeating this process, drawing arms off of arms off of arms, and so
on, until the arms are single squares of size 1. Divisor trees can be
generated for any number $n$ at lims.ac.uk/recursively-divisible-numbers.

Figure 2. Divisor trees for 96 and 100. There are $a(96)=224$ squares in the
left tree and $a(100)=52$ squares in the right. The sum of the side lengths of
the squares, or one-fourth of the tree perimeter, is $b(96)=768$ in the left
tree and $b(100)=340$ in the right. Divisor trees can be generated for any
number $n$ at lims.ac.uk/recursively-divisible-numbers.

###  2.4. Properties of divisor trees

In order to establish properties of the number and sum of recursive divisors,
it is helpful to consider a more fine-grained description of divisor trees,
namely, the number and sum of divisors—or squares in the divisor tree—of a
given size.

######  Proposition 1.

Let the number of recursive divisors of size $k$ be $a(n,k)$. Then $a(n,n)=1$
and for $k\lfloor n$,

$a(n,k)=\sum_{m\lfloor n}a(m,k),$

and $a(n,k)=0$ otherwise, where $k\lfloor n$ means $k$ is a proper divisor of
$n$.

_Proof._ The Proposition follows immediately from consideration of the divisor
trees. ∎

######  Lemma 1.

The number of recursive divisors of size $k$ satisifes

$a(k\,n,k)=a(n,1).$

_Proof._ By Proposition 1,

(2) $a(n,1)=\sum_{m\lfloor n}a(m,1)$

and

$a(k\,n,k)=\sum_{m\lfloor k\,n}a(m,k).$

Since $a(m,k)=0$ if $k$ does not divide $m$, this can be rewritten as

(3) $a(k\,n,k)=\sum_{m\lfloor n}a(k\,m,k).$

Let the prime omega function $\Omega(n)$ sum the exponents in the prime
factorization of $n$, that is, for
$n=p_{1}^{\alpha_{1}}\,p_{2}^{\alpha_{2}}\ldots p_{j}^{\alpha_{j}}$,
$\Omega(n)=\alpha_{1}+\alpha_{2}+\ldots+\alpha_{j}$. I prove the theorem by
induction on $\Omega(n)$. The base case $\Omega(n)=0$, or $n=1$, holds by
Proposition 1: $a(k\cdot 1,k)=a(1,1)$. I now show that if $a(k\,n,k)=a(n,1)$
for all $n$ such that $\Omega(n)<i$, then $a(k\,n,k)=a(n,1)$ for all $n$ such
that $\Omega(n)<i+1$. To see why, observe that in (3) all of the proper
divisors $m$ of $n$ must have $\Omega(m)$ at most $\Omega(n)-1$. Therefore by
assumption all of the $a(k\,m,k)$ in (3) reduce to $a(m,1)$, and the right
side of (3) takes the form of the right side of (2) and thus equals $a(n,1)$.
∎

######  Lemma 2.

For $n>1$, the number of recursive divisors of size 1 is equal to half the
total number of recursive divisors, that is,

$a(n,1)=a(n)/2.$

Note that recursive divisors of size 1 are equivalent to squares of size 1 in
the divisor trees.
_Proof._ Clearly

$a(n)=\sum_{m|n}a(n,m).$

By Lemma 1, this becomes

(4) $a(n)=\sum_{m|n}a(n/m,1)=\sum_{m|n}a(m,1),$

which we can equally express as

(5) $a(n)=a(n,1)+\sum_{m\lfloor n}a(m,1).$

Inserting Proposition 1 with $k=1$ into the above,

$a(n)=2a(n,1).\qed$

###  2.5. Relation to the number of ordered factorizations

Here I show that for $n>1$, the number of recursive divisors $a(n)$ is twice
the number of ordered factorizations into integers greater than one, which I
call $g(n)$. But before getting to that, I first introduce $g(n)$ and mention
some of the work on it.
The number of ordered factorizations $g(n)$ satisifes $g(1)=1$ and

$g(n)=\sum_{m\lfloor n}g(m).$

For example, 12 can be written as the product of integers greater than one in
eight ways: $12=6\cdot 2=2\cdot 6=4\cdot 3=3\cdot 4=3\cdot 2\cdot 2=2\cdot
3\cdot 2=2\cdot 2\cdot 3$. So $g(12)=8$.
Kalmar [8] was the first to consider $g(n)$, and it was later studied more
systematically by Hille [9]. Over the last 80 years several authors have
extended Hille’s results [10, 11, 12], some of which we will mention later.

######  Theorem 1.

Let $g(n)$ be the number of ordered factorizations into integers greater than
one and set $g(1)=1$. Then for $n>1$,

$a(n)=2g(n).$

_Proof._ The definition of $g(n)$ is identical to Proposition 1 for $k=1$,
that is, identical to $a(n,1)$. Since $g(1)=a(1,1)=1$, the proof follows
directly from Lemma 2. ∎

###  2.6. Relation between the number and sum of recursive divisors

The $b(n)$ are more difficult to calculate than the $a(n)$, and it would be
helpful to have an expression relating the $b(n)$ to the $a(n)$. Here I give
just such a relation. I will use it later to explicitly determine $b(n)$ for
certain values of $n$.

######  Theorem 2.

Let $B(n)=b(n)/n$ and $A(n)=a(n)/n$. Then

$B(n)=\frac{1}{2}+\frac{1}{2}\sum_{m|n}A(m).$

_Proof_. Let $b(n,m)$ be the sum of the side lengths of squares of size $m$ in
the $n$th divisor tree. Then

$b(n)=\sum_{m|n}b(n,m)=\sum_{m|n}m\,a(n,m).$

By Lemma 1,

$b(n)=\sum_{m|n}m\,a(n/m,1)=n+\sum_{m\lfloor n}m\,a(n/m,1).$

By Lemma 2,

$b(n)=n+\frac{1}{2}\sum_{m\lfloor
n}m\,a(n/m)=\frac{n}{2}+\frac{1}{2}\sum_{m|n}m\,a(n/m)=\frac{n}{2}+\frac{n}{2}\sum_{m|n}a(m)/m.$

With $B(n)=b(n)/n$ and $A(n)=a(n)/n$, the theorem follows. ∎

##  3\. Number of recursive divisors

The number of recursive divisors $a(n)$ is not as readily determined as the
number of divisors $d(n)$. The first 96 values of $a(n)$ are shown in Table 1,
which also gives a concise Mathematica algorithm for generating them. The
first 100,000 values are plotted in Figure 3.

$n$ |  $a(n)$ |  $n$ |  $a(n)$ |  $n$ |  $a(n)$ |  $n$ |  $a(n)$ |  $n$ |  $a(n)$ |  $n$ |  $a(n)$
---|---|---|---|---|---|---|---|---|---|---|---
1 | 1 | 17 | 2 | 33 | 6 | 49 | 4 | 65 | 6 | 81 | 16
2 | 2 | 18 | 16 | 34 | 6 | 50 | 16 | 66 | 26 | 82 | 6
3 | 2 | 19 | 2 | 35 | 6 | 51 | 6 | 67 | 2 | 83 | 2
4 | 4 | 20 | 16 | 36 | 52 | 52 | 16 | 68 | 16 | 84 | 88
5 | 2 | 21 | 6 | 37 | 2 | 53 | 2 | 69 | 6 | 85 | 6
6 | 6 | 22 | 6 | 38 | 6 | 54 | 40 | 70 | 26 | 86 | 6
7 | 2 | 23 | 2 | 39 | 6 | 55 | 6 | 71 | 2 | 87 | 6
8 | 8 | 24 | 40 | 40 | 40 | 56 | 40 | 72 | 152 | 88 | 40
9 | 4 | 25 | 4 | 41 | 2 | 57 | 6 | 73 | 2 | 89 | 2
10 | 6 | 26 | 6 | 42 | 26 | 58 | 6 | 74 | 6 | 90 | 88
11 | 2 | 27 | 8 | 43 | 2 | 59 | 2 | 75 | 16 | 91 | 6
12 | 16 | 28 | 16 | 44 | 16 | 60 | 88 | 76 | 16 | 92 | 16
13 | 2 | 29 | 2 | 45 | 16 | 61 | 2 | 77 | 6 | 93 | 6
14 | 6 | 30 | 26 | 46 | 6 | 62 | 6 | 78 | 26 | 94 | 6
15 | 6 | 31 | 2 | 47 | 2 | 63 | 16 | 79 | 2 | 95 | 6
16 | 16 | 32 | 32 | 48 | 96 | 64 | 64 | 80 | 96 | 96 | 224
Table 1. The first 96 values of the number of recursive divisors $a(n)$. A
concise Mathematica algorithm for the $a(n)$ is as follows: n = 2; max = 96; a
= {1}; While[n <= max, a = Append[a, 1 + Total[Part[a, Delete[Divisors[n],
-1]]]]; n++]; a

###  3.1. Distinct primes

Let $n=p_{1}\,p_{2}\ldots p_{k}$ be the product of $k$ distinct primes. By
(1), the number of divisors is simply $d(p_{1}\,p_{2}\ldots p_{k})=2^{k}$.
Here I calculate the less straightforward $a(p_{1}\,p_{2}\ldots p_{k})$.

######  Theorem 3.

Let $n=p_{1}\,p_{2}\ldots p_{k}$ be the product of $k$ distinct primes. Then
the exponential generating function of $a(p_{1}p_{2}\ldots p_{k})$ is

${\rm EG}(a(p_{1}p_{2}\ldots p_{k}),x)=\frac{e^{x}}{2-e^{x}}.$

_Proof._ This theorem is equivalent to

(6) $a(p_{1}p_{2}\ldots
p_{k})=1+\sum_{i=0}^{k-1}\binom{k}{i}a(p_{1}p_{2}\ldots p_{i}).$

I prove it by induction. First note that $a(p_{1})=1+\binom{1}{0}a(1)=2$. I
now show that if (6) is true for $k$, then it is true for $k+1$. I do so by
adding to $a(p_{1}p_{2}\ldots p_{k})$ all of the $a$s for divisors which
include $p_{k+1}$, apart from $a(p_{1}p_{2}\ldots p_{k+1})$, since
$p_{1}p_{2}\ldots p_{k+1}$ is not a proper divisor of itself. I also must add
$a(p_{1}p_{2}\ldots p_{k})$, which is left out of the expression for
$a(p_{1}p_{2}\ldots p_{k})$. This adds up to $a(p_{1}p_{2}\ldots p_{k+1})$,
and we can write

$\displaystyle a(p_{1}p_{2}\ldots p_{k+1})=$
$\displaystyle\,\,a(p_{1}p_{2}\ldots p_{k})+a(p_{1}p_{2}\ldots p_{k})$
$\displaystyle+$
$\displaystyle\,\,\binom{k}{0}a(p_{1})+\binom{k}{1}a(p_{1}p_{2})+\ldots+\binom{k}{k-1}a(p_{1}p_{2}\ldots
p_{k})$ $\displaystyle=$ $\displaystyle\,\,1+a_{1}(p_{1}p_{2}\ldots
p_{k})+\sum_{i=0}^{k-1}\binom{k}{i}a(p_{1}p_{2}\ldots
p_{i})+\sum_{i=0}^{k-1}\binom{k}{i}a(p_{1}p_{2}\ldots p_{i+1})$
$\displaystyle=$ $\displaystyle\,\,1+(k+1)a_{1}(p_{1}p_{2}\ldots
p_{k})+\sum_{i=0}^{k-1}\left(\binom{k}{i}+\binom{k}{i-1}\right)a(p_{1}p_{2}\ldots
p_{i})$ $\displaystyle=$ $\displaystyle\,\,1+(k+1)a_{1}(p_{1}p_{2}\ldots
p_{k})+\sum_{i=0}^{k-1}\binom{k+1}{i}a(p_{1}p_{2}\ldots p_{i})$
$\displaystyle=$
$\displaystyle\,\,1+\sum_{i=0}^{k}\binom{k+1}{i}a(p_{1}p_{2}\ldots
p_{i}).\qed$

So for the product of $k=1,2,\ldots$ distinct primes,
$a(k)=2,6,26,150,1082,9366,\ldots$, which is the number of ordered set
partitions of subsets of $\\{1,\ldots,n\\}$ (OEIS A000629 [13]).

Figure 3. The number of recursive divisors $a(n)$. The recursively highly
composite numbers, which satisfy $a(n)>a(m)$ for all $m<n$, are the big red
points.

###  3.2. Primes to a power

When $n$ is equal to the product of primes to powers, $a(n)$ is governed by
recursion relations relating it to values of $a(n)$ for primes to lower
powers.

######  Theorem 4.

Let $p,q$ and $r$ be prime. Then

$\displaystyle a(p^{c})$ $\displaystyle=$ $\displaystyle 2a(p^{c-1}),$
$\displaystyle a(p^{c}q^{d})$ $\displaystyle=$ $\displaystyle
2\Big{(}a(p^{c-1}q^{d})+a(p^{c}q^{d-1})-a(p^{c-1}q^{d-1})\Big{)},$
$\displaystyle a(p^{c}q^{d}r^{e})$ $\displaystyle=$ $\displaystyle
2\Big{(}a(p^{c-1}q^{d}r^{e})+a(p^{c}q^{d-1}r^{e})+a(p^{c}q^{d}r^{e-1}),$
$\displaystyle-$ $\displaystyle
a(p^{c}q^{d-1}r^{e-1})-a(p^{c-1}q^{d}r^{e-1})-a(p^{c-1}q^{d-1}r^{e}),$
$\displaystyle+$ $\displaystyle a(p^{c-1}q^{d-1}r^{e-1})\Big{)}.$

Analogous recursion relations apply for the product of four and more primes to
powers.

_Proof._ I first prove the case of $n=p^{c}$. From Definition 1,

(7) $a(p^{c})=1+\sum_{i=0}^{c-1}a(p^{i}).$

Adding $a(p^{c})$ to both sides,

$2a(p^{c})=1+\sum_{i=0}^{c}a(p^{i}).$

With $c\rightarrow c-1$,

$\sum_{i=0}^{c-1}a(p^{i})=2a(p^{c-1})-1,$

which, when inserted into (7), gives

$a(p^{c})=2a(p^{c-1}).$

Using this, the recursion relation for $n=p^{c}q^{d}$ can be proved, which can
in turn be used to prove the case for $n=p^{c}q^{d}r^{e}$, and so on. The
approach is similar to, but somewhat simpler than, that used to prove Theorem
6. However, Hille [9] and Chor _et al._ [10] proved that identical recursion
relations govern $g(n)$, the number of ordered factorizations into integers
greater than one. From Theorem 1, $a(n)=2g(n)$, and inserting this into
Hille’s and Chor’s recursion relations gives the desired results. ∎

######  Corollary 1.

Let $\tau$ be the maximum exponent in the prime factorization of $n$. Then
$2^{\tau}$ divides $a(n)$.

_Proof._ Notice that all of the recursion relations in Theorem 4 have a factor
of 2 on the right-hand side. The corollary is implied by iterating the
recursion relation $\tau$ times. On each iteration, the exponents on the right
are reduced by at most 1. Now iterate until the smallest exponent is reduced
to 0. Then the exponent disappears since, for example,
$a(p^{c}q^{0})=a(p^{c})$. Continuing this process, the recursion relations are
iterated $\tau$ times, giving $\tau$ factors of 2. ∎
In Table 3, which shows the high water marks for $a(n)$, the $a(n)$ are
expressed as a product of $2^{\tau}$ and an integer. Note that there are in
general no other guaranteed divisors of $a(n)$, since in many cases $a(n)$ is
the product of $2^{\tau}$ and a prime.
The recursion relations in Theorem 4 can be solved for one, two and three
primes to powers.

######  Theorem 5.

Let $p,q$ and $r$ be prime. Then

$\displaystyle a(p^{c})$ $\displaystyle=$ $\displaystyle 2^{c}$ $\displaystyle
a(p^{c}q^{d})$ $\displaystyle=$ $\displaystyle
2^{c}\sum_{i=0}^{d}\binom{d}{i}\binom{c+i}{i}.$ $\displaystyle
a(p^{c}q^{d}r^{e})$ $\displaystyle=$
$\displaystyle\sum_{j=0}^{d}(-1)^{j}\binom{d}{j}\binom{c+d-j}{d}a(p^{c+d-j}r^{e}).$

_Proof._ The result for $n=p^{c}$ follows by inspection. For $n=p^{c}q^{d}$
and $n=p^{c}q^{d}r^{e}$, Chor _et al._ [10] give the analogous results for
$g(n)$, the number of ordered factorizations into integers greater than one.
From Theorem 1, $a(n)=2g(n)$, and applying this to Chor’s results gives the
desired recurrence relations. ∎

##  4\. Sum of recursive divisors

The first 96 values of the sum of recursive divisors $b(n)$ are shown in Table
2, which also gives a concise Mathematica algorithm for generating them. The
first 100,000 values are plotted in Figure 4.

$n$ |  $b(n)$ |  $n$ |  $b(n)$ |  $n$ |  $b(n)$ |  $n$ |  $b(n)$ |  $n$ |  $b(n)$ |  $n$ |  $b(n)$
---|---|---|---|---|---|---|---|---|---|---|---
1 | 1 | 17 | 18 | 33 | 50 | 49 | 58 | 65 | 86 | 81 | 146
2 | 3 | 18 | 54 | 34 | 56 | 50 | 112 | 66 | 188 | 82 | 128
3 | 4 | 19 | 20 | 35 | 50 | 51 | 74 | 67 | 68 | 83 | 84
4 | 8 | 20 | 58 | 36 | 176 | 52 | 122 | 68 | 154 | 84 | 430
5 | 6 | 21 | 34 | 37 | 38 | 53 | 54 | 69 | 98 | 85 | 110
6 | 14 | 22 | 38 | 38 | 62 | 54 | 190 | 70 | 184 | 86 | 134
7 | 8 | 23 | 24 | 39 | 58 | 55 | 74 | 71 | 72 | 87 | 122
8 | 20 | 24 | 116 | 40 | 156 | 56 | 196 | 72 | 524 | 88 | 276
9 | 14 | 25 | 32 | 41 | 42 | 57 | 82 | 73 | 74 | 89 | 90
10 | 20 | 26 | 44 | 42 | 132 | 58 | 92 | 74 | 116 | 90 | 432
11 | 12 | 27 | 46 | 43 | 44 | 59 | 60 | 75 | 144 | 91 | 114
12 | 42 | 28 | 74 | 44 | 106 | 60 | 346 | 76 | 170 | 92 | 202
13 | 14 | 29 | 30 | 45 | 96 | 61 | 62 | 77 | 98 | 93 | 130
14 | 26 | 30 | 104 | 46 | 74 | 62 | 98 | 78 | 216 | 94 | 146
15 | 26 | 31 | 32 | 47 | 48 | 63 | 124 | 79 | 80 | 95 | 122
16 | 48 | 32 | 112 | 48 | 304 | 64 | 256 | 80 | 400 | 96 | 768
Table 2. The first 96 values of the sum of recursive divisors $b(n)$. A
concise Mathematica algorithm for the $b(n)$ is as follows: n = 2; max = 100;
b = {1}; While[n <= max, b = Append[b, n + Total[Part[b, Delete[Divisors[n],
-1]]]]; n++ ]; b

###  4.1. Primes to a power

When $n$ is equal to the product of primes to powers, $b(n)$ is governed by
recursion relations relating it to values of $b(n)$ for primes to lower
powers. The recursion relations are similar to those for $a(n)$, but are more
complex.

######  Theorem 6.

Let $p,q$ and $r$ be prime. Then

$\displaystyle b(p^{c})$ $\displaystyle=$ $\displaystyle
2b(p^{c-1})+(p-1)p^{c-1},$ $\displaystyle b(p^{c}q^{d})$ $\displaystyle=$
$\displaystyle
2\Big{(}b(p^{c-1}q^{d})+b(p^{c}q^{d-1})-b(p^{c-1}q^{d-1})\Big{)}+(p-1)(q-1)p^{c-1}q^{d-1},$
$\displaystyle b(p^{c}q^{d}r^{e})$ $\displaystyle=$ $\displaystyle
2\Big{(}b(p^{c-1}q^{d}r^{e})+a(p^{c}q^{d-1}r^{e})+a(p^{c}q^{d}r^{e-1})$
$\displaystyle-$ $\displaystyle
b(p^{c}q^{d-1}r^{e-1})-a(p^{c-1}q^{d}r^{e-1})-a(p^{c-1}q^{d-1}r^{e})$
$\displaystyle+$ $\displaystyle b(p^{c-1}q^{d-1}r^{e-1})\Big{)}$
$\displaystyle+$ $\displaystyle(p-1)(q-1)(r-1)p^{c-1}q^{d-1}r^{e-1}.$

_Proof._ I first prove the case of $n=p^{c}$. From Definition 2,

(8) $b(p^{c})=p^{c}+\sum_{i=0}^{c-1}b(p^{i}).$

Adding $b(p^{c})$ to both sides,

$2b(p^{c})=p^{c}+\sum_{i=0}^{c}b(p^{i}).$

With $c\rightarrow c-1$,

$\sum_{i=0}^{c-1}b(p^{i})=2b(p^{c-1})-p^{c-1},$

which, when inserted into (8), gives the desired recurrence relation.

Figure 4. The sum of recursive divisors $b(n)$, normalized by $n$. The
recursively super-abundant numbers, which satisfy $b(n)/n>b(m)/m$ for all
$m<n$, are the big red points.

I now prove the case of $n=p^{c}q^{d}$. From Definition 2,

(9)
$b(p^{c}q^{d})=p^{c}q^{d}+\sum_{i=0}^{c-1}\sum_{j=0}^{d}b(p^{i}q^{j})+\sum_{j=0}^{d-1}b(p^{c}q^{j}).$

Adding $b(p^{c}q^{d})$ to both sides,

(10)
$2b(p^{c}q^{d})=p^{c}q^{d}+\sum_{i=0}^{c-1}\sum_{j=0}^{d}b(p^{i}q^{j})+\sum_{j=0}^{d}b(p^{c}q^{j}),$

which we can equally write

(11) $2b(p^{c}q^{d})=p^{c}q^{d}+\sum_{i=0}^{c}\sum_{j=0}^{d}b(p^{i}q^{j}).$

With $d\rightarrow d-1$ in (10), we find

(12)
$\sum_{j=0}^{d-1}b(p^{c}q^{j})=2b(p^{c}q^{d-1})-p^{c}q^{d-1}-\sum_{j=0}^{c-1}\sum_{i=0}^{d-1}b(p^{i}q^{j}).$

With $c\rightarrow c-1$ and $d\rightarrow d-1$ in (11), we find

$\sum_{i=0}^{c-1}\sum_{j=0}^{d-1}b(p^{i}q^{j})=2b(p^{c-1}q^{d-1})-p^{c-1}q^{d-1},$

which inserting into (12) yields

(13)
$\sum_{j=0}^{d-1}b(p^{c}q^{j})=2b(p^{c}q^{d-1})-2b(p^{c-1}q^{d-1})+(1-p)p^{c-1}q^{d-1}.$

With $c\rightarrow c-1$ in (11), we find

(14)
$\sum_{i=0}^{c-1}\sum_{j=0}^{d}b(p^{i}q^{j})=2b(p^{c-1}q^{d})-p^{c-1}q^{d}.$

Inserting (13) and (14) into (9) gives the desired recursion relation.
For $n=p^{c}q^{d}r^{e}$, the proof is similar to that for $n=p^{c}q^{d}$ and
is omitted here. ∎

###  4.2. Explicit values

The recursion relations in Theorem 6 can be solved. I only give the results
for $n=p^{c}$ and $n=p^{c}q^{d}$. For $n=p^{c}q^{d}r^{e}$, the solution is
more intricate but can be solved in a similar way to that for $n=p^{c}q^{d}$.
The expressions simplify when $p=2$.

######  Theorem 7.

Let $p$ and $q$ be prime, and $B(n)=b(n)/n$. Then

$\displaystyle B(p^{c})$ $\displaystyle=$
$\displaystyle\frac{p-1-(2/p)^{c}}{p-2}\quad{\rm for}\;p\;{\rm odd},$
$\displaystyle B(2^{c})$ $\displaystyle=$ $\displaystyle(c+2)/2,$
$\displaystyle B(p^{c}q^{d})$ $\displaystyle=$
$\displaystyle\frac{1}{2}+\frac{1}{2}\sum_{i=0}^{c}\frac{2^{i}}{p^{i}}\sum_{j=0}^{d}\frac{1}{q^{j}}\sum_{k=0}^{j}\binom{i+k}{k}\binom{j}{k},$
$\displaystyle B(2^{c}q^{d})$ $\displaystyle=$
$\displaystyle\frac{1}{2}+\frac{1}{2}\sum_{j=0}^{d}\frac{1}{q^{j}}\sum_{k=0}^{j}\binom{j}{k}\binom{c+k+1}{k+1}.$

_Proof._ I first prove the case of $n=p^{c}$. From Theorem 2,

(15) $B(p^{c})=\frac{1}{2}+\frac{1}{2}\sum_{i=0}^{c}A(p^{i})$

From Theorem 4, $a(p^{c})=2^{c}$ and $A(p^{i})=a(p^{i})/p^{i}=(2/p)^{i}$.
Inserting this into (15), we find

$\displaystyle B(p^{c})$ $\displaystyle=$
$\displaystyle\frac{p-1-(2/p)^{c}}{p-2}.$

For $p=2$ this is indeterminate but, by L’Hôpital’s rule,

$B(2^{c})=(c+2)/2.\\\ $

I now prove the case of $n=p^{c}q^{d}$. From Theorem 2,

(16)
$B(p^{c}q^{d})=\frac{1}{2}+\frac{1}{2}\sum_{i=0}^{c}\sum_{j=0}^{d}A(p^{i}q^{j}).$

Theorem 5 gives $a(p^{c}q^{d})$ explicitly. Inserting
$A(p^{i}q^{j})=a(p^{i}q^{j})/(p^{i}q^{j})$ into (16) yields

$B(p^{c}q^{d})=\frac{1}{2}+\frac{1}{2}\sum_{i=0}^{c}\frac{2^{i}}{p^{i}}\sum_{j=0}^{d}\frac{1}{q^{j}}\sum_{k=0}^{j}\binom{i+k}{k}\binom{j}{k}.$

For $p=2$, this simplies:

$\displaystyle B(2^{c}q^{d})$ $\displaystyle=$
$\displaystyle\frac{1}{2}+\frac{1}{2}\sum_{j=0}^{d}\frac{1}{q^{j}}\sum_{k=0}^{j}\binom{j}{k}\sum_{i=0}^{c}\binom{i+k}{k}$
$\displaystyle=$
$\displaystyle\frac{1}{2}+\frac{1}{2}\sum_{j=0}^{d}\frac{1}{q^{j}}\sum_{k=0}^{j}\binom{j}{k}\binom{c+k+1}{k+1}.\qed$

##  5\. Recursively highly composite and
recursively super-abundant numbers

###  5.1. Highly composite and super-abundant numbers

I briefly review highly composite and super-abundant numbers before
considering their recursive analogues. A number $n$ is highly composite if it
has more divisors than any of its predecessors, that is, $d(n)>d(m)$ for all
$m<n$. These are shown in the right-hand column of Table 3. A number $n$ is
super-abundant if the sum of its divisors, normalized by $n$, is greater than
that of any of its predecessors, that is, $\sigma(n)/n>\sigma(m)/m$ for all
$m<n$. These are the starred numbers in the right-hand column of Table 3. Both
types of numbers have been extensively studied by Ramanujan and others [5, 6].
For sufficiently small values of $n$, super-abundant numbers are also highly
composite, but later this ceases to be the case. The first super-abundant
number that is not highly composite is 1,163,962,800 (A166735 [13]), and in
fact only 449 numbers are both super-abundant and highly composite (A166981
[13]).

$\begin{array}[]{rclrcrclr}&n&&.\mbox{\hskip 28.90755pt}a(n)&\mbox{\hskip
36.135pt}&&n&&\mbox{\hskip 14.45377pt}d(n)\\\ 1&=&1&1&\text{}&*1&=&1&1\\\
2&=&2&1\cdot 2&\text{}&*2&=&2&2\\\ 4&=&2^{2}&1\cdot
2^{2}&\text{}&*4&=&2^{2}&3\\\ 6&=&2\cdot 3&3\cdot 2&\text{}&*6&=&2\cdot 3&4\\\
8&=&2^{3}&1\cdot 2^{3}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
12&=&2^{2}\cdot 3&4\cdot 2^{2}&\text{}&*12&=&2^{2}\cdot 3&6\\\ 24&=&2^{3}\cdot
3&5\cdot 2^{3}&\text{}&*24&=&2^{3}\cdot 3&8\\\ 36&=&2^{2}\cdot 3^{2}&13\cdot
2^{2}&\text{}&*36&=&2^{2}\cdot 3^{2}&9\\\ 48&=&2^{4}\cdot 3&6\cdot
2^{4}&\text{}&*48&=&2^{4}\cdot 3&10\\\
\text{}&\text{}&\text{}&\text{}&\text{}&*60&=&2^{2}\cdot 3\cdot 5&12\\\
72&=&2^{3}\cdot 3^{2}&19\cdot 2^{3}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
96&=&2^{5}\cdot 3&7\cdot 2^{5}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
120&=&2^{3}\cdot 3\cdot 5&33\cdot 2^{3}&\text{}&*120&=&2^{3}\cdot 3\cdot
5&16\\\ 144&=&2^{4}\cdot 3^{2}&26\cdot
2^{4}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
\text{}&\text{}&\text{}&\text{}&\text{}&*180&=&2^{2}\cdot 3^{2}\cdot 5&18\\\
192&=&2^{6}\cdot 3&8\cdot 2^{6}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
240&=&2^{4}\cdot 3\cdot 5&46\cdot 2^{4}&\text{}&*240&=&2^{4}\cdot 3\cdot
5&20\\\ 288&=&2^{5}\cdot 3^{2}&34\cdot
2^{5}&\text{}&\text{}&\text{}&\text{}&\text{}\\\ 360&=&2^{3}\cdot 3^{2}\cdot
5&151\cdot 2^{3}&\text{}&*360&=&2^{3}\cdot 3^{2}\cdot 5&24\\\ 432&=&2^{4}\cdot
3^{3}&96\cdot 2^{4}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
480&=&2^{5}\cdot 3\cdot 5&61\cdot
2^{5}&\text{}&\text{}&\text{}&\text{}&\text{}\\\ 576&=&2^{6}\cdot
3^{2}&43\cdot 2^{6}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
720&=&2^{4}\cdot 3^{2}\cdot 5&236\cdot 2^{4}&\text{}&*720&=&2^{4}\cdot
3^{2}\cdot 5&30\\\ \text{}&\text{}&\text{}&\text{}&\text{}&*840&=&2^{3}\cdot
3\cdot 5\cdot 7&32\\\ 864&=&2^{5}\cdot 3^{3}&138\cdot
2^{5}&\text{}&\text{}&\text{}&\text{}&\text{}\\\ 960&=&2^{6}\cdot 3\cdot
5&78\cdot 2^{6}&\text{}&\text{}&\text{}&\text{}&\text{}\\\ 1152&=&2^{7}\cdot
3^{2}&53\cdot 2^{7}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
\text{}&\text{}&\text{}&\text{}&\text{}&*1260&=&2^{2}\cdot 3^{2}\cdot 5\cdot
7&36\\\ 1440&=&2^{5}\cdot 3^{2}\cdot 5&346\cdot
2^{5}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
\text{}&\text{}&\text{}&\text{}&\text{}&*1680&=&2^{4}\cdot 3\cdot 5\cdot
7&40\\\ 1728&=&2^{6}\cdot 3^{3}&190\cdot
2^{6}&\text{}&\text{}&\text{}&\text{}&\text{}\\\ 1920&=&2^{7}\cdot 3\cdot
5&97\cdot 2^{7}&\text{}&\text{}&\text{}&\text{}&\text{}\\\ 2160&=&2^{4}\cdot
3^{3}\cdot 5&996\cdot 2^{4}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
2304&=&2^{8}\cdot 3^{2}&64\cdot
2^{8}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
\text{}&\text{}&\text{}&\text{}&\text{}&*2520&=&2^{3}\cdot 3^{2}\cdot 5\cdot
7&48\\\ 2880&=&2^{6}\cdot 3^{2}\cdot 5&484\cdot
2^{6}&\text{}&\text{}&\text{}&\text{}&\text{}\\\ 3456&=&2^{7}\cdot
3^{3}&253\cdot 2^{7}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
4320&=&2^{5}\cdot 3^{3}\cdot 5&1590\cdot
2^{5}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
\text{}&\text{}&\text{}&\text{}&\text{}&*5040&=&2^{4}\cdot 3^{2}\cdot 5\cdot
7&60\\\ 5760&=&2^{7}\cdot 3^{2}\cdot 5&653\cdot
2^{7}&\text{}&\text{}&\text{}&\text{}&\text{}\\\ 6912&=&2^{8}\cdot
3^{3}&328\cdot 2^{8}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
\text{}&\text{}&\text{}&\text{}&\text{}&7560&=&2^{3}\cdot 3^{3}\cdot 5\cdot
7&64\\\ 8640&=&2^{6}\cdot 3^{3}\cdot 5&2402\cdot
2^{6}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
\text{}&\text{}&\text{}&\text{}&\text{}&*10080&=&2^{5}\cdot 3^{2}\cdot 5\cdot
7&72\\\ 11520&=&2^{8}\cdot 3^{2}\cdot 5&856\cdot
2^{8}&\text{}&\text{}&\text{}&\text{}&\text{}\end{array}$

TABLE 3. The left column shows the recursively highly composite numbers and
the recursively super-abundant numbers (which are starred) up to one million.
All of the recursively super-abundant numbers shown here are also recursively
highly composite, apart from one, 181,440. The right column shows the highly
composite numbers and the super-abundant numbers (which are starred) up to one
million. All of the super-abundant numbers shown here are also highly
composite.

$\begin{array}[]{rclrcrclr}&n&&\mbox{\hskip
7.22743pt}a(n)&\mbox{}&&n&&\mbox{}d(n)\\\
\text{}&\text{}&\text{}&\text{}&\text{}&*15120&=&2^{4}\cdot 3^{3}\cdot 5\cdot
7&80\\\ 17280&=&2^{7}\cdot 3^{3}\cdot 5&3477\cdot
2^{7}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
\text{}&\text{}&\text{}&\text{}&\text{}&20160&=&2^{6}\cdot 3^{2}\cdot 5\cdot
7&84\\\ 23040&=&2^{9}\cdot 3^{2}\cdot 5&1096\cdot
2^{9}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
\text{}&\text{}&\text{}&\text{}&\text{}&*25200&=&2^{4}\cdot 3^{2}\cdot
5^{2}\cdot 7&90\\\ 25920&=&2^{6}\cdot 3^{4}\cdot 5&10368\cdot
2^{6}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
\text{}&\text{}&\text{}&\text{}&\text{}&*27720&=&2^{3}\cdot 3^{2}\cdot 5\cdot
7\cdot 11&96\\\ 30240&=&2^{5}\cdot 3^{3}\cdot 5\cdot 7&20874\cdot
2^{5}&\text{}&\text{}&\text{}&\text{}&\text{}\\\ 34560&=&2^{8}\cdot 3^{3}\cdot
5&4864\cdot 2^{8}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
\text{}&\text{}&\text{}&\text{}&\text{}&45360&=&2^{4}\cdot 3^{4}\cdot 5\cdot
7&100\\\ 46080&=&2^{10}\cdot 3^{2}\cdot 5&1376\cdot
2^{10}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
\text{}&\text{}&\text{}&\text{}&\text{}&50400&=&2^{5}\cdot 3^{2}\cdot
5^{2}\cdot 7&108\\\ 51840&=&2^{7}\cdot 3^{4}\cdot 5&15979\cdot
2^{7}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
\text{}&\text{}&\text{}&\text{}&\text{}&*55440&=&2^{4}\cdot 3^{2}\cdot 5\cdot
7\cdot 11&120\\\ 60480&=&2^{6}\cdot 3^{3}\cdot 5\cdot 7&34266\cdot
2^{6}&\text{}&\text{}&\text{}&\text{}&\text{}\\\ 69120&=&2^{9}\cdot 3^{3}\cdot
5&6616\cdot 2^{9}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
\text{}&\text{}&\text{}&\text{}&\text{}&83160&=&2^{3}\cdot 3^{3}\cdot 5\cdot
7\cdot 11&128\\\ 86400&=&2^{7}\cdot 3^{3}\cdot 5^{2}&28481\cdot
2^{7}&\text{}&\text{}&\text{}&\text{}&\text{}\\\ 103680&=&2^{8}\cdot
3^{4}\cdot 5&23692\cdot 2^{8}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
\text{}&\text{}&\text{}&\text{}&\text{}&*110880&=&2^{5}\cdot 3^{2}\cdot 5\cdot
7\cdot 11&144\\\ 120960&=&2^{7}\cdot 3^{3}\cdot 5\cdot 7&53485\cdot
2^{7}&\text{}&\text{}&\text{}&\text{}&\text{}\\\ 138240&=&2^{10}\cdot
3^{3}\cdot 5&8790\cdot 2^{10}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
161280&=&2^{9}\cdot 3^{2}\cdot 5\cdot 7&17656\cdot
2^{9}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
\text{}&\text{}&\text{}&\text{}&\text{}&*166320&=&2^{4}\cdot 3^{3}\cdot 5\cdot
7\cdot 11&160\\\ 172800&=&2^{8}\cdot 3^{3}\cdot 5^{2}&42520\cdot
2^{8}&\text{}&\text{}&\text{}&\text{}&\text{}\\\ 207360&=&2^{9}\cdot
3^{4}\cdot 5&34026\cdot 2^{9}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
\text{}&\text{}&\text{}&\text{}&\text{}&221760&=&2^{6}\cdot 3^{2}\cdot 5\cdot
7\cdot 11&168\\\ 241920&=&2^{8}\cdot 3^{3}\cdot 5\cdot 7&80176\cdot
2^{8}&\text{}&\text{}&\text{}&\text{}&\text{}\\\ 276480&=&2^{11}\cdot
3^{3}\cdot 5&11447\cdot 2^{11}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
\text{}&\text{}&\text{}&\text{}&\text{}&*277200&=&2^{4}\cdot 3^{2}\cdot
5^{2}\cdot 7\cdot 11&180\\\ 311040&=&2^{8}\cdot 3^{5}\cdot 5&103540\cdot
2^{8}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
\text{}&\text{}&\text{}&\text{}&\text{}&*332640&=&2^{5}\cdot 3^{3}\cdot 5\cdot
7\cdot 11&192\\\ 345600&=&2^{9}\cdot 3^{3}\cdot 5^{2}&61436\cdot
2^{9}&\text{}&\text{}&\text{}&\text{}&\text{}\\\ 362880&=&2^{7}\cdot
3^{4}\cdot 5\cdot 7&267219\cdot
2^{7}&\text{}&\text{}&\text{}&\text{}&\text{}\\\ 414720&=&2^{10}\cdot
3^{4}\cdot 5&47576\cdot 2^{10}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
483840&=&2^{9}\cdot 3^{3}\cdot 5\cdot 7&116256\cdot
2^{9}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
\text{}&\text{}&\text{}&\text{}&\text{}&498960&=&2^{4}\cdot 3^{4}\cdot 5\cdot
7\cdot 11&200\\\ 552960&=&2^{12}\cdot 3^{3}\cdot 5&14652\cdot
2^{12}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
\text{}&\text{}&\text{}&\text{}&\text{}&*554400&=&2^{5}\cdot 3^{2}\cdot
5^{2}\cdot 7\cdot 11&216\\\ 604800&=&2^{7}\cdot 3^{3}\cdot 5^{2}\cdot
7&480953\cdot 2^{7}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
622080&=&2^{9}\cdot 3^{5}\cdot 5&156278\cdot
2^{9}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
\text{}&\text{}&\text{}&\text{}&\text{}&*665280&=&2^{6}\cdot 3^{3}\cdot 5\cdot
7\cdot 11&224\\\ 691200&=&2^{10}\cdot 3^{3}\cdot 5^{2}&86362\cdot
2^{10}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
\text{}&\text{}&\text{}&\text{}&\text{}&*720720&=&2^{4}\cdot 3^{2}\cdot 5\cdot
7\cdot 11\cdot 13&240\\\ 725760&=&2^{8}\cdot 3^{4}\cdot 5\cdot 7&422932\cdot
2^{8}&\text{}&\text{}&\text{}&\text{}&\text{}\\\ 829440&=&2^{11}\cdot
3^{4}\cdot 5&65018\cdot 2^{11}&\text{}&\text{}&\text{}&\text{}&\text{}\\\
967680&=&2^{10}\cdot 3^{3}\cdot 5\cdot 7&163934\cdot
2^{10}&\text{}&\text{}&\text{}&\text{}&\text{}\\\ \\\
\lx@intercol\hfil\emph{Recursively super-abundant but}\hfil\lx@intercol&&\\\
\lx@intercol\hfil\emph{not recursively highly composite}\hfil\lx@intercol&&\\\
181440&=&2^{6}\cdot 3^{4}\cdot 5\cdot 7&&\end{array}$

###  5.2. Recursively highly composite numbers

By analogy with highly composite numbers, a number $n$ is recursively highly
composite if it has more recursive divisors than any of its predecessors.

######  Definition 3.

A number is recursively highly composite if it satisfies

$a(n)>a(m)\,\,\,{\rm for\,\,all}\,\,\,m<n.$

These numbers are shown in the left-hand column of Table 3 up to one million.
In terms of divisor trees, a number is recursively highly composite if its
divisor tree has more squares than any of its predecessors’ divisor trees.
Because $a(n)$ depends only on the exponents in the prime factorization of
$n=p_{1}^{\alpha_{1}}\,p_{2}^{\alpha_{2}}\ldots p_{j}^{\alpha_{j}}$, the
exponents in recursively highly composite numbers must be non-increasing. For
assume that $\alpha_{i+k}<\alpha_{i}$ in a recursively highly composite
number. But
$p_{i}^{\alpha_{i+k}}p_{i+k}^{\alpha_{i}}<p_{i}^{\alpha_{i}}p_{i+k}^{\alpha_{i+k}}$,
so there exists an $m<n$ with the same value of $a(n)$, contradicting the
assumption. (I take the primes to be in ascending order.)

$n$ | _Technology_ |  _Standard displays_
---|---|---
24 | $10\times 24$ | Tetris |  |
| $24\times 16$ | 384-well assay |  |
48 | $128\times 48$ | TRS 80 |  |
72 | 72 points/in | Adobe point |  |
96 | $96\times 64$ | TI-81 calculator |  |
| $96\times 65$ | Nokia 1100 |  |
120 | $120\times 160$ | Nokia 100 | $160\times 120$ | QQVGA
144 | $144\times 168$ | Pebble Time watch |  |
240 | $240\times 64$ | Atari Portfolio | $320\times 240$ | Quarter VGA
288 | $352\times 288$ | Video CD | $352\times 288$ | CIF
360 | $360\times 360$ | LG Watch Style | $640\times 360$ | nHD
480 | $320\times 480$ | iPhone 1–3 | $640\times 480$ | VGA
| $480\times 480$ | LG Watch Sport |  |
576 | 576 lines | PAL analog television | $1024\times 576$ | WSVGA
720 | $720\times 364$ | Macintosh XL, Hercules | $1280\times 720$ | HD
864 |  |  | $1152\times 864$ | XGA+
960 |  | Facebook website |  |
1152 |  |  | $1152\times 2048$ | QWXGA
1440 |  | 3.5” disk block size | $2560\times 1440$ | Quad HD
1920 |  |  | $1920\times 1080$ | Full HD
2160 | $2160\times 1440$ | Microsoft Surface Pro 3 | $4096\times 2160$ | DCI 4K
|  |  | $3840\times 2160$ | 4K Ultra HD
2304 | $2304\times 1440$ | MacBook Retina display |  |
| $4096\times 2304$ | 21.5” 4K Retina iMac |  |
2880 | $\quad 2880\times 1800$ | 15 in MacBook Pro |  $5120\times 2880$ | 5K
3456 |  | Canon EOS 1100D |  |
4320 |  |  | $7680\times 4320$ | 8K Ultra HD
8640 |  |  | $15360\times 8640$ | 16K Ultra HD
Table 4. Some applications of recursively highly composite numbers and
recursively super-abundant numbers (which are starred) in technology and
standard displays.

###  5.3. Recursively super-abundant numbers

By analogy with super-abundant numbers, a number $n$ is recursively super-
abundant if the sum of its recursive divisors, normalized by $n$, is greater
than that of any of its predecessors.

######  Definition 4.

A number is recursively super-abundant if it satisfies

$b(n)/n>b(m)/m\,\,\,{\rm for\,\,all}\,\,\,m<n.$

The $b(n)$ are the starred numbers in the left-hand column of Table 3. In
terms of divisor trees, a number is recursively super-abundant if the
perimeter of its divisor tree, normalized such that the largest square has
length unity, is bigger than that of any of its predecessors’ divisor trees.
For sufficiently small values of $n$, recursively super-abundant numbers are
recursively highly composite. The first exception is at 181,440, and there are
likely more. (See the list of open questions at the end.)

###  5.4. Applications

Recursively divisible numbers are especially well suited to design across
multiple length scales, in which the whole must be divided into parts, the
parts into subparts, and so on. Recursively highly composite and recursively
super-abundant numbers are frequently found in technology and standard
displays, examples of which are shown in Table 4.
In technology, these numbers are used for the screen resolutions of watches,
phones, cameras and computers. They appear in games, such as Tetris, and in
high-throughput technologies, such as test tube microplates. As a result,
users of these technologies have maximal optionality for dividing the space
into parts in a hierarchical way when, for example, building a website,
designing a game or planning an experiment.
In display technologies, many standard resolutions use these numbers in the
height or width of the display, measured in pixels. Because standard displays
tend to preserve certain aspect ratios, such as 16:9, it is usually not
possible for both numbers to be either recursively highly composite or
recursively super-abundant.

###  5.5. Ten open questions

In this paper I introduced and studied the recursive divisor function and
recursively divisible numbers. There are many open questions on this topic,
and I list 10 here.

######  Question 1.

For what values of $n$ does a divisor tree overlap itself?

######  Question 2.

For what values of $n$ do divisor trees have an exact or approximate fractal
dimension?

######  Question 3.

For $x=2$ in the definition of the recursive divisor function, is
$\sigma_{2}(n)/n^{2}$ bounded? If so, what is the bound?

######  Question 4.

What are the recursion relations for $\sigma_{2}(n)$ for $n$ equal to primes
to a power?

######  Question 5.

Can the relation between $a(n)/n$ and $b(n)/n$ in Theorem 2 be generalized to
other values of $x$ in the definition of the recursive divisor function?

######  Question 6.

What is the recursion relation for $b(n)$ when $n$ is the product of $k$
distinct primes?

######  Question 7.

Are there a finite number of numbers that are both recursively highly
composite and recursively super-abundant, like the highly composite and super-
abundant numbers (OEIS A166981 [13])?

######  Question 8.

If the former statement is true, what is the largest number that is both
recursively highly composite and recursively super-abundant?

######  Question 9.

What is the largest number that is both highly composite and recursively
highly composite? And that is both super-abundant and recursively super-
abundant? (Table 3 suggests both might be 720.)

######  Question 10.

How do the shapes of recursively highly composite and recursively super-
abundant numbers differ from each other, in terms of the distribution of
exponents in their prime factorization?

I acknowledge Andriy Fedosyeyev and Rayan Melwani for helpful discussions.

## References

  * [1] M. Schofield (ed.), _Plato: Laws_ (Cambridge University Press, 2016).
  * [2] J. Müller-Brockmann, _Grid Systems in Graphic Design_ (Verlag Niggli, 1999).
  * [3] C. Baldwin _Design Rules: The Power of Modularity_ (MIT Press, 2000).
  * [4] See https://960.gs. This is really a grid of 96, since it is in terms of 10 pixel blocks.
  * [5] S. Ramanujan, Highly composite numbers, _P Lond Math Soc_ 14, 347 (1915). (The part of this paper on super-abundant numbers was originally surpressed.)
  * [6] L. Alaoglu, P. Erdös, On highly composite and similar numbers, _T Am Math Soc_ 56, 448 (1944).
  * [7] J. Maeda, _The Laws of Simplcity_ (MIT Press, 2006).
  * [8] L. Kalmar, A factorisatio numerorum probelmajarol, _Mat Fiz Lapok_ 38, 1 (1931).
  * [9] E. Hille, A problem in factorisatio numerorum, _Acta Arith_ 2, 134 (1936).
  * [10] B. Chor, P. Lemke, Z. Mador, On the number of ordered factorizations of natural numbers, _Disc Math_ 214, 123 (2000).
  * [11] M. Klazara, F. Luca, On the maximal order of numbers in the factorisatio numerorum problem, _J Number Theory_ 124, 470 (2007).
  * [12] M. Deléglise, M. Hernane, J.-L. Nicolas, Grandes valeurs et nombres champions de la fonction arithmétique de Kalmár, _J Number Theory_ 128, 1676 (2008).
  * [13] N. J. A. Sloane, editor, The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org, 2018.