Navigation 
 Home 
 Search 
 Site map 

 Contact Graeme 
 Home 
 Email 
 Twitter

 Skip Navigation LinksMath Help > Number Theory > Factors, Coprimes, and Totient Function > Highly Composite Numbers

Highly Composite Numbers

A highly composite number is a number, n, such that no number smaller than n has as many factors as n.

Example: The number 24 has 8 divisors. No smaller number has that many divisors, so we call 24 a highly composite number.  All of the numbers in the first column of the table, below, are highly composite.  By adding 1, we get squares of prime numbers.  I checked to see if this happens again, and I was surprised to find another example. Can you find it?

    24   25    52
    48   49    72
    120  121  112
    360  361  192
    840  841  292
    1680 1681 412
    5040 5041 712

Source: http://www.mathpuzzle.com/ 

Graeme's thinking on this problem:

Actually there are quite a few more highly composite numbers that aren't one less than a perfect square.  But a lot of them are one less (or one more) than a prime.  This table explains:

Highly Composite Numbers

HCN
(Sloane's A002182)		 prime factorization divisors
(Sloane's
A002183)		 sqrt n+1 nearest
prime
minus
HCN
(Sloane's
A117825)
1 1  1
221 2 0
422 3 ±1
621 31 4 ±1
1222 31 6 ±1
2423 31 85-1
3622 32 9 1
4824 31 107-1
6022 31 51 12 ±1
12023 31 51 1611±7
18022 32 51 18 ±1
24024 31 51 20 ±1
36023 32 51 2419-1
72024 32 51 30 -1
84023 31 51 713229 -1
1,26022 32 51 7136  -1
1,68024 31 51 7140 41-11
2,52023 32 51 7148  1
5,04024 32 51 7160 71-1
7,56023 33 51 7164  ±1
10,08025 32 51 7172  -1
15,12024 33 51 7180  1
20,16026 32 51 7184  1
25,20024 32 52 7190  -11
27,72023 32 51 71 11196  13
45,36024 34 51 71100  1
50,40025 32 52 71108  11
55,44024 32 51 71 111120  ±1
83,16023 33 51 71 111128  17
110,88025 32 51 71 111144  ±1
166,32024 33 51 71 111160  -1
221,76026 32 51 71 111168  ±13
277,20024 32 52 71 111180  13
332,64025 33 51 71 111192  1
498,96024 34 51 71 111200  1
554,40025 32 52 71 111216  ±17
665,28026 33 51 71 111224  -1
720,72024 32 51 71 111 131 240 -17
1,081,08023 33 51 71 111 131 256 -1
1,441,44025 32 51 71 111 131 288 -1
2,162,16024 33 51 71 111 131 320 17
2,882,88026 32 51 71 111 131 336 ±17
3,603,60024 32 52 71 111 131 360 -17
4,324,32025 33 51 71 111 131 384 1
6,486,48024 34 51 71 111 131 400 -1
7,207,20025 32 52 71 111 131 432 -19
8,648,64026 33 51 71 111 131 448 37
10,810,80024 33 52 71 111 131 480 -37
14,414,40026 32 52 71 111 131 504 1
17,297,28027 33 51 71 111 131 5124159±17
21,621,60025 33 52 71 111 131 576 -23
32,432,40024 34 52 71 111 131 600 -1
36,756,72024 33 51 71 111 131 171 640 29
43,243,20026 33 52 71 111 131 672 1
61,261,20024 32 52 71 111 131 171 720 -1
73,513,44025 33 51 71 111 131 171 768 ±19
110,270,16024 34 51 71 111 131 171 800 1
122,522,40025 32 52 71 111 131 171 864 -19
147,026,88026 33 51 71 111 131 171 896 23
183,783,60024 33 52 71 111 131 171 960 1
245,044,80026 32 52 71 111 131 171 1008 -19
294,053,76027 33 51 71 111 131 171 1024 -31
367,567,20025 33 52 71 111 131 171 1152 1
551,350,80024 34 52 71 111 131 171 1200 -19
698,377,68024 33 51 71 111 131 171 191 1280 -1
735,134,40026 33 52 71 111 131 171 1344 -1
1,102,701,60025 34 52 71 111 131 171 1440 -1
1,396,755,36025 33 51 71 111 131 171 191 1536 -1
2,095,133,04024 34 51 71 111 131 171 191 1600 23
2,205,403,20026 34 52 71 111 131 171 1680 -1
2,327,925,60025 32 52 71 111 131 171 191 1728 29
2,793,510,72026 33 51 71 111 131 171 191 1792 23
3,491,888,40024 33 52 71 111 131 171 191 1920 -23
4,655,851,20026 32 52 71 111 131 171 191 2016 1
5,587,021,44027 33 51 71 111 131 171 191 2048 -23
6,983,776,80025 33 52 71 111 131 171 191 2304 71
10,475,665,20024 34 52 71 111 131 171 191 2400 -37
13,967,553,60026 33 52 71 111 131 171 191 2688 1
20,951,330,40025 34 52 71 111 131 171 191 2880 -1
27,935,107,20027 33 52 71 111 131 171 191 3072 -31
41,902,660,80026 34 52 71 111 131 171 191 3360 -1
48,886,437,60025 33 52 72 111 131 171 191 3456 -23
64,250,746,56026 33 51 71 111 131 171 191 2313584  53
73,329,656,40024 34 52 72 111 131 171 191 3600 ±1
80,313,433,20024 33 52 71 111 131 171 191 2313840  31
97,772,875,20026 33 52 72 111 131 171 191 4032 29
128,501,493,12027 33 51 71 111 131 171 191 2314096  29
146,659,312,80025 34 52 72 111 131 171 191 4320 23
160,626,866,40025 33 52 71 111 131 171 191 2314608  -29
240,940,299,60024 34 52 71 111 131 171 191 2314800  29
293,318,625,60026 34 52 72 111 131 171 191 5040 1
321,253,732,80026 33 52 71 111 131 171 191 2315376  37
481,880,599,20025 34 52 71 111 131 171 191 2315760  43
642,507,465,60027 33 52 71 111 131 171 191 2316144  -29
963,761,198,40026 34 52 71 111 131 171 191 2316720  29
1,124,388,064,80025 33 52 72 111 131 171 191 2316912  -31
1,606,268,664,00026 33 53 71 111 131 171 191 2317168  1
1,686,582,097,20024 34 52 72 111 131 171 191 2317200  ±29
1,927,522,396,80027 34 52 71 111 131 171 191 2317680  -37
2,248,776,129,60026 33 52 72 111 131 171 191 2318064  67
3,212,537,328,00027 33 53 71 111 131 171 191 2318192  -1
3,373,164,194,40025 34 52 72 111 131 171 191 2318640  1
4,497,552,259,20027 33 52 72 111 131 171 191 2319216  43
6,746,328,388,80026 34 52 72 111 131 171 191 23110080  1
8,995,104,518,40028 33 52 72 111 131 171 191 23110368  ±37
9,316,358,251,20026 33 52 71 111 131 171 191 231 29110752  47
13,492,656,777,60027 34 52 72 111 131 171 191 23111520  29
18,632,716,502,40027 33 52 71 111 131 171 191 231 29112288  ±1
26,985,313,555,20028 34 52 72 111 131 171 191 23112960  -43
27,949,074,753,60026 34 52 71 111 131 171 191 231 29113440  ±67
32,607,253,879,20025 33 52 72 111 131 171 191 231 29113824  1
46,581,791,256,00026 33 53 71 111 131 171 191 231 29114336  1
48,910,880,818,80024 34 52 72 111 131 171 191 231 29114400  -31
55,898,149,507,20027 34 52 71 111 131 171 191 231 29115360  1
65,214,507,758,40026 33 52 72 111 131 171 191 231 29116128  37
93,163,582,512,00027 33 53 71 111 131 171 191 231 29116384  1
97,821,761,637,60025 34 52 72 111 131 171 191 231 29117280  ±37
130,429,015,516,80027 33 52 72 111 131 171 191 231 29118432  ±1
195,643,523,275,20026 34 52 72 111 131 171 191 231 29120160  37
260,858,031,033,60028 33 52 72 111 131 171 191 231 29120736  37

For more, see A. Flammenkamp's Table of 1200 Highly Composite Numbers

Other interesting factoids about Highly Composite Numbers

Highly composite numbers have sparked a number of interesting observations, some of which I will elaborate on here.

Proximity of HCNs to Primes

Bill McEachen pointed out to me that the offset from the HCN to the nearest prime (Sloane's A117825) is very often 1 i.e. adjacent to the HCN.  All but 12 of the first 41 terms have a prime adjacent, and half of the 120 numbers listed here have a prime adjacent.  Thanks to Bill for providing the data for the column of the table giving the offset to the nearest prime.

Relationship of HCNs to Fortunate Numbers

Reo Franklin Fortune, an anthropologist who was once married to Margaret Read, conjectured that all Fortunate numbers are prime.  Fortunate numbers (OEIS A005235) are P-pk#, where pk# is the kth "primorial" number (i.e. product of the first k primes) and P is the smallest prime larger than pk#+1.  In other words, the distance from a primorial to the next larger prime (farther than one unit away) is a prime number.  If H is an HCN, then the product of H's distinct prime factors, called the radical of H, or rad(H), is a primorial.  That is, H is a multiple of a fairly large primorial, so it's no wonder that the distance from each HCN to the next larger prime also seems to be prime.

"Nearest prime" Sequences of interest

Here, P is used in an expression of the form P-x to mean the next larger prime to x.  Similarly, x-p means the next prime smaller than x.

P-(H+1), (no OEIS), 2, 3, 3, 5, 5, 5, 5, 5, 7, 7, 11, 11, 7, 7, 13, 17, 13, 11, 11, 13, 11, 11, 13, 19, 13, 17, 11, 17, 17, 19, 29, 13, 13, 47, 13, 17, 13, 23, 17, 19, 17, ...

(H-1)-p, (no OEIS), 2, 3, 5, 5, 5, 5, 7, 7, 7, 7, 7, 11, 11, 11, 11, 17, 17, 11, 11, 13, 11, 11, 19, 17, 13, 29, 23, 17, 17, 13, 17, 17, 13, 17, 13, 17, 19, 17, 23, ...

P-pk#, (A005235), 3, 5, 7, 13, 23, 17, 19, 23, 37, 61, 67, 61, 71, 47, 107, 59, 61, 109, 89, 103, 79, 151, 197, 101, 103, 233, 223, 127, 223, 191, 163, 229, 643, ...

(pk#-1)-p, (A055211), 3, 7, 11, 13, 17, 29, 23, 43, 41, 73, 59, 47, 89, 67, 73, 107, 89, 101, 127, 97, 83, 89, 97, 251, 131, 113, 151, 263, 251, 223, 179, 389, 281, ...

Relationship of HCNs and Fortunate Numbers to Shinzel's Conjecture

According to www.primepuzzles.net/problems/prob_004.htm, it was shown by Rosser & Shoenfeld in 1975 that ln(pk#) < 1.001102pk.  (Rosser, J.B. & Schoenfeld, L. Sharper bounds for Chebyshev functions Teta(x) and PHI(x). Math .Comp., 29, 243-269,1975) 

Now, if there is a prime between x and x+ln(x)1.99, (a conjecture a little finer than Schinzel's conjecture that there is always a prime between x and ln(x)2), then there is a prime, P, between pk# and pk#+ln(pk#)1.99.

Combining these two ideas, we have P between pk# and pk#+(1.001102pk)1.99.

Now, (1.001102pk)1.99 < pk2 whenever pk is at least 2, so there is a prime, P, between pk# and pk#+pk2.

Suppose the difference P-pk# is composite. Then its smallest prime factor must be larger than pk, or else P would also be a multiple of pk, and it must have one other (not necessarily unique) prime factor larger than pk (or else it wouldn't be composite), so this composite number must be larger than pk2, which would contradict the existence of a prime between pk# and pk#+pk2.

Now, I ask you: is this a proof? Absolutely not! First, it depends on Schinzel's conjecture, and then it goes further to depend on a finer conjecture which is really quite dubious. But it does serve as a kind of probabilistic argument that can help you understand why there are so few, if any, composite Fortunate numbers, and also so few, if any, non-prime differences to the prime nearest a Highly Composite Number.

Special HCNs having a power of 2 factors

Robert G. Wilson v commented (modified by Ray Chandler) that all powers of two through 217 are present as a number of factors of an HCN, and no power of 2 above that is present at least through 251.  I believe I will prove here that 217 is the largest number that is both a power of two and the number of factors of an HCN -- a property I'll call "special".  In order for an HCN to be special, the exponents of all its prime factors must be one less than a power of 2.  That is, the exponents in the prime factorization of such an HCN must be a sequence such as 3,1,0 or 7,3,3,1,0 or the like.  This is because the number of factors is the product of one plus each exponent.

An effective way to show that a factorization can't be an HCN is to show that a different set of exponents gives a number smaller than the HCN but with as many or more factors.  For example, no HCN's factorization can begin with equal exponents 25 35, or larger, because if it did, then 28 33 would begin the factorization of a smaller number with exactly the same number of factors.  My shorthand way of depicting this situation is:

5, 5 -- no good because 8, 3 gives smaller HCN with as many factors

Naturally, if 5, 5 is no good, then 6, 6 or 7, 7 is no good for the same reason -- adding 3 to the first exponent and subtracting 2 from the second gives a smaller number with at least as many factors.  So the shorthand implies that "higher" sets of exponents sharing the same relationship are no good for the same reason.  Another shorthand I use from time to time is ep to represent the exponent of the prime, p.  For example, I'll refer to e2, e3, and the like.

Maybe it goes without saying, but just in case, I'll say it: the sequence of exponents in the prime factorization of an HCN must be non-increasing.  If, say 5, 4, appear as any two consecutive exponents then interchanging them makes a smaller number with the same number of factors.

It seems like there might be too many such sequences to nail them all down, but after plodding along for a while, I came to the conclusion there aren't really that many cases to consider, so here they are:

0 -- OK -- gives a special HCN with 1 factor
1, 0 -- OK -- gives a special HCN with 2 factors
1, 1, 0 -- OK -- gives a special HCN with 4 factors
1, 1, 1 -- no good because 3, 1, 0 gives smaller HCN with as many factors
          (e2=e3=e5 is no good when they're all 1 or bigger.)
3, 1, 0 -- OK -- gives a special HCN with 8 factors
3, 1, 1... -- OK -- gives special HCNs with 16 and 32 factors
3, 1, 1, 1, 1 -- no good, because 3, 3, 1, 1 gives smaller HCN with as many factors
3, 3, 1... -- OK -- gives special HCNs with 64, 128, and 256 factors
3, 3, 1, 1, 1, 1, 1 -- no good because 7, 3, 1, 1, 1, 1 gives smaller HCN with as many factors
3, 3, 3 -- no good because 5, 3, 2 gives smaller HCN with as many factors
          (see 1,1,1)
7, 1 -- no good because 5, 2 gives smaller HCN with more factors
7, 3, 1... -- OK -- gives special HCNs with 512, 1024, 2048, and 4096 factors
7, 3, and eight 1's -- no good because that eighth 1 is the exponent of 29, which exceeds 25,
          so 7, 3, 3, and six 1's gives smaller HCN with the same number of factors
7, 3, 3, 1... -- OK -- gives special HCNs with 8192, 16384, 32768, 65536, and 131072 factors
7, 3, 3, and eleven 1's -- no good because that eleventh 1 is the exponent of 43, which exceeds 42,
           so 8, 4, 3, 2 and nine 1's is smaller by a factor of 42/43, and has more factors
7, 3, 3, 3 -- no good because 8, 4, 3, 2 gives smaller HCN with more factors
7, 7 -- no good because 10, 5 gives smaller HCN with more factors
          (e2 can't equal e3 unless they're smaller than 5)
15, 1 -- no good because 13, 2 gives smaller HCN with more factors
15, 3 -- no good because 13, 5 gives smaller HCN with more factors
15, 7, 1 -- no good because 10, 7, 3 gives smaller HCN with more factors
15, 7, 3 -- no good because 10, 7, 5 gives smaller HCN with more factors
          (e2+1 must be less than four times e5+1 when e5 is at least 3)
15, 7, 7 -- no good because 14, 9, 6 gives smaller HCN with more factors
          (e3 can't equal e5 unless they're smaller than 5 or e2 exceeds e3 by less than 4)
15, 15 -- no good (see 7, 7)
a, b, where a is any of {31, 63, 127, ...} and b is any number from 1 to a/2 --
          no good because a-5, b+3 gives smaller HCN with more factors
a, a, where a is any of {31, 63, 127, ...} -- no good (see 7, 7)

Whew!  After reviewing 25 cases, all the sequences of exponents in the prime factorization of any "special" HCN have now been put to bed, and there are no others that might make an HCN "special".  (By special, in case you have forgotten by now, I mean an HCN that has a power of 2 factors).

Happy Exponent Ratios

As you are no doubt aware, having read each of the 25 cases in the last proof, an HCN is "happy" when its exponents e2, e3, e5, etc. form certain ratios.  The exponents can't be too close to each other, or too far away, either.  If e2=e3, for example, and they are bigger than a certain size, then the HCN isn't happy, and it's not an HCN at all.  If e2 is more than twice e3, and bigger than a certain size, then it's not happy, either.

What are these happy ratios?

Let H be a Highly Composite Number.  Let's imagine for the moment that the exponents in the prime factorization are real numbers, and let's further restrict our scope to just the primes 2 and 3.  Let's suppose the exponent of 2 is x-1 and the exponent of 3 is y-1.  Together, these two prime numbers "contribute" xy factors of H.  Now, let's further suppose that the contribution of these two primes is a constant, a, and that xy=a.  This means that y=a/x, so we have

2x-1 3a/x 

in the prime factorization of H.  H, we remember is a minimal number with this many factors, so we need to minimize H.  2x-1 3a/x-1 is minimized when the derivative of ln(2)(x-1)+ln(3)(a/x-1) is minimized.  The derivative of

ln(2)(x-1)+ln(3)(a/x-1)

is

ln(2)-a ln(3)/x2,

which is zero when x=sqrt(a ln(3)/ln(2)), and y=a/x=sqrt(a ln(2)/ln(3)), so the ratio of x:y is ln(3):ln(2).  In round numbers, for a given number of factors of H, H is minimized when the ratio of one plus the exponents of 2 and 3 is close to ln(3):ln(2), or about 1.585.

I'll call this the "exponent ratio" (e2+1)/(e3+1) -- the ratio of one plus the exponent of 2 to one plus the exponent of 3.  Looking at Flammenkamp's table of HCNs, we see this exponent ratio fluctuate from 1 to more than 2, but the geometric mean of this ratio over all 1200 HCNs is 1.58946, which is very close to the expected value of 1.585.  However, it shows no signs settling down to that value very quickly.  In fact, three of the last ten HCNs listed have exponent ratios of 2 or larger.  I would still expect to find an "N" such that for n larger than N, the exponent ratio lies properly between 1 and 2.

This concept generalizes to other primes as well.  We even see empirical evidence the generalization is right.  The geometric mean of the ratio (e3+1)/(e5+1) in Flammenkamp's data is 1.47278, very close to the expected ln(5)/ln(3) = 1.465.

Internet references

A. Flammenkamp, Table of 1200 Highly Composite Numbers

Related pages in this website

Puzzles

Prime Factorization 

The Sigma Function -- σ(n) is the sum of the factors of n, and σk(n) is the sum of the n's factors, each to the power k.  So, in particular, σ0(n), sometimes called τ(n), tau(n), is the number of factors of n.

Factoring Polynomials, a topic where factoring whole numbers comes up as one step of a procedure.

The Totient Function -- the number of coprimes of a number

 

The webmaster and author of this Math Help site is Graeme McRae.