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₁^e₁p₂^e₂p₃^e₃...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)(e₂+1)(e₃+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⁸3⁶5⁴7³11²...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.