Which numbers n have more divisors than any smaller number, and how large is the number of divisors d(n)...
arithmetic/highly.composite New
New entry, edited from material collected for the archive and not yet in a released version.
Problem
Which numbers n have more divisors than any smaller number, and how
large is the number of divisors d(n) for n up to 100,000,000?
[ Editor: the opening sentence above is the editor's summary; the
original posting follows. ]
The divisor function d(n) is the sum of number of divisors that divide
integrally a number n. The first few values of d(n), such that both n
and d(n) are larger than the previous, are given in table 1.
Divisor Function d(n)
n d(n) n d(n) n d(n)
1 1 24 8 180 18
2 2 36 9 240 20
4 3 48 10 360 24
6 4 60 12 720 30
12 6 120 16 840 32
Table 1.
Can anyone extend this table to cover n<=100,000,000 or provide a
source if this information is available? d(n) is needed in a C-program
to allocate space for some arrays, and some idea of its size is needed.
-- Randall L. Rathbun <Randall.Rathbun@SanDiego.NCR.COM>
Show solution
The numbers you are interested in are frequently referred to as `highly composite numbers', and have been studied by Ramanujan and Erdos, among others. The two sequences you want appear as numbers 196 and 385 in Sloane's "A Handbook of Integer Sequences". Ramanujan was rather fond of calculating himself and probably calculated many values; see his "Collected Papers", p. 78-128, or his article "Highly Composite Numbers", Proc. London Math. Soc. 14 (1915) 347-400. (I would be willing to bet that a table exists in these articles, but since both books have mysteriously disappeared from our math library, I am unable to verify this.) About ten years ago, I wrote a little APL program to compute these numbers. I don't absolutely guarantee that the numbers are correct, but at least they match the numbers in Sloane's table as far as d(n) = 336. HIGHLY COMPOSITE NUMBERS d(n) n 1 1 2 2 3 4 4 6 6 12 8 24 9 36 10 48 12 60 16 120 18 180 20 240 24 360 30 720 32 840 36 1260 40 1680 48 2520 60 5040 64 7560 72 10080 80 15120 84 20160 90 25200 96 27720 100 45360 108 50400 120 55440 128 83160 144 110880 160 166320 168 221760 180 277200 192 332640 200 498960 216 554400 224 665280 240 720720 256 1081080 288 1441440 320 2162160 336 2882880 360 3603600 384 4324320 400 6486480 432 7207200 448 8648640 480 10810800 504 14414400 512 17297280 576 21621600 600 32432400 640 36756720 672 43243200 720 61261200 768 73513440 800 110270160 -- Jeff Shallit, Department of Computer Science, University of Chicago I suggest you read the Thesis of Guy Robin of the University of Limoges (France), who studied these numbers and worked out an algorithm that generates all highly composite numbers (as one calls them) between N0 and N1. The address of the University is : U. F. R. des Sciences Departement de Mathematique 123 avenue Albert Thomas F-87060 Limoges Cedex France