% Let's convert this to AMS-LaTeX, shall we?
\documentclass[12pt]{article}
\usepackage{latexsym, amsfonts}
\setlength{\textheight}{8.75in}
\setlength{\columnsep}{2.0pc}
\setlength{\textwidth}{6.8in}
\setlength{\topmargin}{0.25in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\oddsidemargin}{-.19in}
\setlength{\parindent}{1pc}
\def\NN{\mathbb{N}}
\newtheorem{lemma}{Proposition}
\newenvironment{proof}{\textsc{Proof:}}{$\Box$ \medskip}
\newenvironment{alg}[1]{\medskip \noindent \textbf{#1} \begin{list}%
{\textbf{Step \arabic{algctr}:}}%
{\usecounter{algctr} %\rightmargin=\leftmargin
\parsep=0pt \itemsep=0pt \topsep=0pt}}{\end{list} \medskip}
\newcounter{algctr}
\title{An Algorithm for Computing Highly Composite Numbers}
\author{Kiran S. Kedlaya}
\date{\today}
\begin{document}
%\begin{abstract}
%After Ramanujan, we define the {\it highly composite\/} numbers to be
%those with more divisors than any smaller numbers. We give a fast
%algorithm for computing these numbers.
%\end{abstract}
\maketitle
\section{Introduction}
A \emph{highly composite number} is a positive integer with more
divisors than any smaller positive integer. In other words, if
$\tau(n)$ denotes the number of divisors of $n$, then $n$ is highly
composite if $\tau(m) < \tau(n)$ for all $m < n$. The highly composite
numbers (HCNs) were introduced by Ramanujan \cite{ram}, who used them
to study the asymptotic growth of the $\tau$-function. Subsequent
investigators of these numbers include Erd\H{o}s \cite{erd} and
Nicolas \cite{nic}.
In order to guess asymptotic properties of the highly composite
numbers, it helps to be able to compute them efficiently. Robin
\cite{rob} gave an algorithm for computing HCNs based on the notion of
``b\'en\'efice'' (benefit). The purpose of this note is to describe
another such algorithm, which has the advantages of being fairly
simple as well as reasonably efficient.
\section{The Algorithm}
The key to the method is the notion of a {\it highly composite
$k$-product\/} (abbreviated HCP$_k$), defined to be a number with $k$
distinct prime factors having more divisors than any smaller number
with $k$ distinct prime factors. The following observations are
immediate consequences of the definition:
\begin{itemize}
\item
Every HCP$_k$ is of the form $p_1^{a_1}\dots p_k^{a_k}$, where
$p_i$ is the $i$-th prime and $a_1 \geq a_2 \geq \dots \geq a_k > 0$.
\item
If $p_1^{a_1}\dots p_k^{a_k}$ is an HCP$_k$, then
$p_1^{a_1}\dots p_{k-1}^{a_{k-1}}$ is an HCP$_{k-1}$.
\item
Every HCN
with exactly $k$ prime factors is an HCP$_k$.
\end{itemize}
Thus given a sufficiently long list of HCP$_{k-1}$'s, one can
construct a list of HCP$_{k}$'s as follows. Given an HCP$_{k}$ $n$,
for successive values of $j$, find the smallest HCP$_{k-1}$ $m$ such
that $(j+1) \tau(m) > \tau(n)$. The next HCP$_{k}$ is then the
minimum of $m p_{k}^{j}$ over all $j$. (Clearly once we encounter a
value of $j$ for which $m = f(k-1,1)$, we need not consider larger
$j$.)
This translates into a simple algorithm as follows. Let $f(k,n)$
denote the $n$-th HCP$_{k}$ and $d(k,n) = \tau(f(k,n))$. The above
discussion reduces the computation of $f$ to the computation of
functions $g(k,n)$ and $h(k, n)$ for $n \geq 1$ and $k \geq 2$ such that
\[
f(k, n) = p_{k}^{g(k,n)} f(k-1, h(k,n)), \quad
d(k, n) = (g(k,n) + 1) d(k-1, h(k,n)).
\]
We can ignore $k=1$ since clearly $f(1,n) = 2^{n}$.
\begin{alg}{Algorithm 1: Computing HCP$_k$'s}
\item
If $n = 1$, let $g(k, n) = h(k, n) = 1$ and STOP.
Otherwise, let $r = 2 f(k, n-1)$ and $j = 1$.
\item
Find the smallest integer $s$ for which either
$(j+1)d(k-1, s) > d(k, n - 1)$ or $p_k^j f(k-1, s) > r$.
If the latter fails to hold,
let $r = p_k^j f(k-1, s)$, $e_k = j$, and $m = s$.
\item
If $s > 1$, add 1 to $j$ and return to Step~2. Otherwise,
let $g(k, n) = e_k$, $h(k, n) = m$ and STOP.
\end{alg}
The HCNs can be found in a table of HCPs
by a process parallel to Algorithm~1. Namely, let $H(n)$ denote the
$n$-th HCN. To find $H(n)$, for each $k$,
find the smallest HCP$_{k}$ $m$ with more divisors than $H(n-1)$; the
smallest of these is $H(n)$. (As in Algorithm 1, once a value of $k$
is found such that $m = f(k,1)$, we need not consider larger $k$.)
\begin{alg}{Algorithm 2: Computing HCN's}
\item
If $n = 1$, let $H(n) = 1$ and STOP.
Otherwise, let $r = 2 H(n-1)$ and $k=1$.
\item
Find the smallest integer $s$ for which either
$d(k,s) > \tau(H(n-1))$ or $f(k,s) \geq r$. If the latter fails to
hold, let $r = f(k, s)$.
\item
If $s > 1$, add 1 to $k$ and return to Step~2. Otherwise,
let $H(n) = r$ and STOP.
\end{alg}
\section{Implementation}
While the algorithms are simple enough to describe, making them run
efficiently is a bit trickier. In this section, we describe some
modifications we have made to improve performance.
For successive values of $k$, we use Algorithm~1 to generate a list
of the values of $d(k,n)$, $f(k,n)$, $g(k,n)$, $h(k,n)$; we then use
Algorithm~2 to locate HCNs in these lists. The maximum length of a
list, the number of lists, and the number of HCNs are specified at
runtime, though a list is truncated before the maximum length if an
uncomputed value from a previous list is needed.
In Step~2 of either algorithm, we are asked to find the smallest $s$
with a given property; we can profit from the fact that with each pass
through the algorithm, this $s$ is getting larger. To be precise, in
Algorithm~1, for fixed $k$ and $j$, the value of $s$ is never
decreasing, while in Algorithm~2, for fixed $k$ the value of $s$ is
never decreasing. Hence by keeping track of the last values used and
searching from that point instead of from 1, we save a great deal of
time.
A second modification, which is easy to implement but slightly
complicated conceptually, involves decreasing the search space at
Step~1. We describe this first for Algorithm~2, where the necessary
modification is fairly simple.
\begin{lemma}
If $n$ is an HCN with $k$ distinct prime factors, then $n \leq
p_{k+1}^{2k}$.
\end{lemma}
\begin{proof}
Factor $n$ as $p_{i}^{e_{1}} \dots p_{k}^{e_{k}}$
and suppose $n > p_{k+1}^{2k}$. Then for some $i$, $p_{i}^{e_{i}} >
p_{k+1}^{2}$. Let $m = \lceil \log p_{k+1}/\log p_{i}
\rceil$; then $e_i > 2 \log_{p_i} p_{k+1} \geq 2m - 1$. But this means
that $n p_{k+1} / p_i^m$ is an integer less than $n$ with $\tau(n) 2(e_i
- m + 1) / (e_i + 1) \geq \tau(n)$ divisors, so $n$ is not an HCN.
\end{proof}
Therefore in Step~1, we may set $k$ to be the
smallest integer such that $n \leq p_{k+1}^{2k}$ rather than 1,
eliminating deep searches in lists that
will not yield any more HCNs.
The corresponding modification to Algorithm~1 requires
a lower bound on the exponent of $p_{k}$ for a large HCP$_{k}$. Such
a bound can be derived by modifying the above argument, but we get a much
better estimate by a different approach.
\begin{lemma}
For any $n, k \in \NN$, there exists $t \leq n$ with at most $k$
prime factors such that
\[
\tau(t) \geq \left( \frac{\log n}{k} \right)^{k} \prod_{i=1}^{k}
\frac{1}{\log p_{k}}.
\]
\end{lemma}
\begin{proof}
Let $\lambda_{i} = \log n/(k \log p_{i})$ and put $e_{i} = \lfloor
\lambda_{i} \rfloor$ and $t = \prod p_{i}^{e_{i}}$. Then
\[
\tau(t) = \prod (e_{i} + 1) \geq \prod \lambda_{i} =
\left( \frac{\log n}{k} \right)^{k} \prod_{i=1}^{k}\frac{1}{\log p_{k}}.
\]
\end{proof}
\begin{lemma}
Suppose
\[
\frac{(\log n)^{k}}
{(\log n + \log p_{1} + \dots + \log p_{k-1})^{k-1}}
> ke(\ell + 1) \log p_{k}.
\]
If $m = p_{1}^{e_{1}} \dots p_{k}^{e_{k}}$ is an HCP$_{k}$ greater than
$n$, then $e_{k} \geq \ell$.
\end{lemma}
\begin{proof}
As the right side is increasing in $\ell$, it suffices by induction to
prove that $e_k \neq \ell$. The left side
is increasing in $\log n$ (factor off $\log n$ and the rest is
obviously increasing), so the
assumed inequality still holds with $m$ in place of $n$. If $e_k =
\ell$, we have by the AM-GM inequality,
\[
\left( \frac{\log m - \ell \log p_{k} + \log p_{1} + \dots + \log p_{k-1}}{k-1}
\right)
^{k-1} \geq \prod_{i=1}^{k-1} [e_{i} + 1]\log p_{i} =
\frac{\tau(m)}{\ell+1} \prod_{i=1}^{k-1} \log p_{i}.
\]
On the other hand, by the previous lemma, there exists $t \leq m$ such
that
\begin{eqnarray*}
\tau(t) &\geq& \left( \frac{\log m}{k} \right)^{k} \prod_{i=1}^{k}
\frac{1}{\log p_{k}} \\
&>& \frac{(\log m + \log p_{1} + \dots +
\log p_{k-1})^{k-1}}{k^{k}}
k e (\ell +1) \log p_{k} \prod_{i=1}^{k}
\frac{1}{\log p_{k}} \\
&\geq& \left( \frac{\log m - \ell \log p_{k}+ \log p_{1} + \dots +
\log p_{k-1}}{k-1} \right)^{k-1}
e (\ell+1) \left( \frac{k-1}{k} \right)^{k-1} \prod_{i=1}^{k-1}
\frac{1}{\log p_{k}} \\
&\geq& \tau(m),
\end{eqnarray*}
using the fact that $e > [k/(k-1)]^{k-1}$ for all $k$. Hence $m$
cannot be an HCP$_{k}$.
\end{proof}
With these modifications, we have recreated Robin's table of 5000
highly composite numbers in several minutes on a Sun workstation.
Ramanujan's table of 102 HCNs appears almost instantly (note that his
table is missing the HCN $293318625600$ between the 85th and 86th
terms). These tables and the C code of the implementation described
above can be obtained from the author's WWW site INSERT-URL.
\begin{thebibliography}{9}
\bibitem{erd}
P. Erd\H{o}s, On highly composite numbers, \textit{J. London Math.
Soc.} \textbf{19} (1944) 130-133.
\bibitem{nic}
J.-L. Nicolas, Nombres hautement compos\'es, \textit{Acta Arith.}
\textbf{49} (1988) 395-412.
\bibitem{ram}
S. Ramanujan, Highly composite numbers, \textit{Proc. Lond. Math. Soc.}
(2) \textbf{14} (1915) 347-409.
\bibitem{rob}
G. Robin, M\'ethods d'optimisation pour un probl\`eme de th\'eorie des
nombres, \textit{R.A.I.R.O. Informatique th\'eoretique} \textbf{17}
(1983) 239-247.
\end{thebibliography}
\end{document}