*Universität Bielefeld
*

Fakultät für Mathematik

# Highly Composite Numbers

A natural number *n* is called highly composite, if it has more divisors than any smaller number. Let the prime-factorization of such a number *n* be
p_{1}^{e1}p_{2}^{e2}p_{3}^{e3}...with *p*_{j} > p_{i} if *j > i * and the exponents *e*_{i} non-negative integers.
Generally the number of divisors of *n* is then *(e*_{1}+1)(e_{2}+1)(e_{3}+1)... and we have for highly composite numbers: if * j > i * then *e*_{j} <= e_{i}.
Lastly, denote by *m* the largest index *i* such that *e*_{i} > 0, also called the maximal prime index.
The average prime exponent *e*_{i} of such a hihly composite number is proportional to *1 / ln p*_{i}.
Here is a list of the first 1200 highly composite numbers computed 1991-10-31 on a HP 710/50 MHz.

Recently I discovered an Algorithm for Generating Highly Composite Numbers
and I recognized my misspelling "composited" :-/.
Therefore I dug up my old C-source for comparision.
The algorithm uses as non-triviality only S. Ramanujan's formula *[ln(p)/ln(q)] <= a*_{q} < = 2 [ln(p+)/ln(q)] to estimate the prime-exponents *a*_{q} of any prime *q* by the highest occuring prime *p* and its successor prime *p+*.
I think the program needed about 4 minutes to compute the smallest 1200 HCNs on the HP 710. Anyway, on an old K6-2 233 MHz it needs 49 sec for the first 1000 HCNs and
on an modern Athlon Thunderbird 1,2 GHz it needs < 6.5 sec.
I think this remarkable speed advantage is due to the fact that it is a C-program not a Mathematica-code.

But the real surprise was, that in the above cited PDF the 1000th HCN is given as *2*^{8}3^{6}5^{4}7^{3}11^{2}...157 163 which is my 1001-th ! Because for the 97-th HCN we got the same, it
seems that there is a HCN missing from Donald Siano's program!.
See his Web-site.
After an email exchange --- and the discovery of the miss of the 769-th HCN in his list ---
he said this publication/algorithm was only "a joke", "an entertainment",
not serious mathematics --- dispite he let check his result from a number theorist (Kiran Kedlaya) and then stated its correctness
(the claimed 1000-th HCN of his HCN-list is
indeed the 1000-th HCN) by an unpublished different algorithm.

Rerunning 2002-11-08 my C-program up to the 10000-th HCN enables this diagram:

Recall the definition of a superior highly composite number, SHCN, which
implies *e*_{i} = [1/(p_{i}^{1/x}-1)] for a certain *x > 0*.
Considering this sub-class of the HCNs, we
see that the asymptotics of the highest prime index *m* is given by an estimation of *Pi(ln(SHCN))*:

Anyway, bounds on *m* results in a remarkable speed-up of the respectively modified algorithm: e.g. the first 10000 HCNs in less than half a minute compared to half an hour without these heuristics!

How many HCNs are there up to a given bound *x*?
Erdös proved: asymptotically at least *ln*^{1+eps}(x).
From the following diagram we get the impression that *k*, the index of the k-th HCN, is perhaps proportional to *ln(HCN)*^{1.25}.

But here you see the long term variations on *k* better:

These made the estimation of the true exponent numerically very difficult.
And lastly have a look how *d(HCN)* is approximated by *ln(HCN)*:

Next a gziped list of the **proved** first 124260 HCNs (1.75 MB) ---
this was done by a new implemented algorithm using interval arithmetic in december 2002 - january 2003.

Each line of this uncompressed file contains a HCN in the format:

ln(HCN) ln(d(HCN)) m e_1 e_2 e_3 ... e_i^k_i ... 2^k_2 1^k1.

1st entry: ln(HCN) the natural logarithm of the HCN up to 6 digits.

2nd entry: ln(d(HCN)) the natural logarithm of the divisor-function up to 7 digits

3rd entry: m the number of different primes in the factorization of the HCN

remaining entries: e_1 e_2 ,,,, the list of the exponents of its canonical prime-factorization.
Here successive equal exponents are coded as e_i^k_i, meaning k_i identical
with exponent value e_i follow.

Finally a working-paper on the distribution of HCNs as DVI-File. The last two conjectures of this paper are used as bounds on *m*.
With this heuristic I computed the list of the **proven** smallest 779674 HCNs (1.5 MB).
Due to save space, each line of this 'unbzip2'ed file misses the ln(HCN) and ln(d(HCN)) entry and so starts with
the 3rd entry in the format described above for the first 1039000 HCNs.

Achim Flammenkamp

2003-02-11 16:30 UT+1