Highly Composite Number

A Composite Number (also called a Superabundant Number) is a number $n$ which has more Factors than any other number less than $n$. In other words, $\sigma(n)/n$ exceeds $\sigma(k)/k$ for all $k<n$, where $\sigma(n)$ is the Divisor Function. They were called highly composite numbers by Ramanujan, who found the first 100 or so, and superabundant by Alaoglu and Erdös (1944).

There are an infinite number of highly composite numbers, and the first few are 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, ... (Sloane's A002182). Ramanujan (1915) listed 102 up to 6746328388800 (but omitted 293, 318, 625, 600, and 29331862500). Robin (1983) gives the first 5000 highly composite numbers, and a comprehensive survey is given by Nicholas (1988).

If

$$N=2^{a_2}3^{a_3}\cdots p^{a_p}$$ (1)

is the prime decomposition of a highly composite number, then

1. The Primes 2, 3, ..., $p$ form a string of consecutive Primes,

2. The exponents are nonincreasing, so $a_2\geq a_3\geq \ldots\geq a_p$, and

3. The final exponent $a_p$ is always 1, except for the two cases $N=4=2^2$ and $N=36=2^2\cdot 3^2$, where it is 2.

Let $Q(x)$ be the number of highly composite numbers $\leq x$. Ramanujan (1915) showed that

$$\lim_{x\to\infty} {Q(x)\over\ln x}=\infty.$$ (2)

Erdös (1944) showed that there exists a constant $c_1>0$ such that

$$Q(x)\geq (\ln x)^{1+c_1}$$ (3)

Nicholas proved that there exists a constant $c_2>0$ such that

$$Q(x)\ll (\ln x)^{c_2}.$$ (4)

See also Abundant Number

References

Alaoglu, L. and Erdös, P. ``On Highly Composite and Similar Numbers.'' Trans. Amer. Math. Soc. 56, 448-469, 1944.

Andree, R. V. ``Ramanujan's Highly Composite Numbers.'' Abacus 3, 61-62, 1986.

Berndt, B. C. Ramanujan's Notebooks, Part IV. New York: Springer-Verlag, p. 53, 1994.

Dickson, L. E. History of the Theory of Numbers, Vol. 1: Divisibility and Primality. New York: Chelsea, p. 323, 1952.

Flammenkamp, A. http://www.uni-bielefeld.de/~achim/highly.html.

Honsberger, R. Mathematical Gems I. Washington, DC: Math. Assoc. Amer., p. 112, 1973.

Honsberger, R. ``An Introduction to Ramanujan's Highly Composite Numbers.'' Ch. 14 in Mathematical Gems III. Washington, DC: Math. Assoc. Amer., pp. 193-207, 1985.

Kanigel, R. The Man Who Knew Infinity: A Life of the Genius Ramanujan. New York: Washington Square Press, p. 232, 1991.

Nicholas, J.-L. ``On Highly Composite Numbers.'' In Ramanujan Revisited: Proceedings of the Centenary Conference (Ed. G. E. Andrews, B. C. Berndt, and R. A. Rankin). Boston, MA: Academic Press, pp. 215-244, 1988.

Ramanujan, S. ``Highly Composite Numbers.'' Proc. London Math. Soc. 14, 347-409, 1915.

Ramanujan, S. Collected Papers. New York: Chelsea, 1962.

Robin, G. ``Méthodes d'optimalisation pour un problème de théories des nombres.'' RAIRO Inform. Théor. 17, 239-247, 1983.

Sloane, N. J. A. Sequence A002182/M1025 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

Wells, D. The Penguin Dictionary of Curious and Interesting Numbers. New York: Penguin Books, p. 128, 1986.