# document.write (document.title)

 Math 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 2 21 2 0 4 22 3 ±1 6 21 31 4 ±1 12 22 31 6 ±1 24 23 31 8 5 -1 36 22 32 9 1 48 24 31 10 7 -1 60 22 31 51 12 ±1 120 23 31 51 16 11 ±7 180 22 32 51 18 ±1 240 24 31 51 20 ±1 360 23 32 51 24 19 -1 720 24 32 51 30 -1 840 23 31 51 71 32 29 -1 1,260 22 32 51 71 36 -1 1,680 24 31 51 71 40 41 -11 2,520 23 32 51 71 48 1 5,040 24 32 51 71 60 71 -1 7,560 23 33 51 71 64 ±1 10,080 25 32 51 71 72 -1 15,120 24 33 51 71 80 1 20,160 26 32 51 71 84 1 25,200 24 32 52 71 90 -11 27,720 23 32 51 71 111 96 13 45,360 24 34 51 71 100 1 50,400 25 32 52 71 108 11 55,440 24 32 51 71 111 120 ±1 83,160 23 33 51 71 111 128 17 110,880 25 32 51 71 111 144 ±1 166,320 24 33 51 71 111 160 -1 221,760 26 32 51 71 111 168 ±13 277,200 24 32 52 71 111 180 13 332,640 25 33 51 71 111 192 1 498,960 24 34 51 71 111 200 1 554,400 25 32 52 71 111 216 ±17 665,280 26 33 51 71 111 224 -1 720,720 24 32 51 71 111 131 240 -17 1,081,080 23 33 51 71 111 131 256 -1 1,441,440 25 32 51 71 111 131 288 -1 2,162,160 24 33 51 71 111 131 320 17 2,882,880 26 32 51 71 111 131 336 ±17 3,603,600 24 32 52 71 111 131 360 -17 4,324,320 25 33 51 71 111 131 384 1 6,486,480 24 34 51 71 111 131 400 -1 7,207,200 25 32 52 71 111 131 432 -19 8,648,640 26 33 51 71 111 131 448 37 10,810,800 24 33 52 71 111 131 480 -37 14,414,400 26 32 52 71 111 131 504 1 17,297,280 27 33 51 71 111 131 512 4159 ±17 21,621,600 25 33 52 71 111 131 576 -23 32,432,400 24 34 52 71 111 131 600 -1 36,756,720 24 33 51 71 111 131 171 640 29 43,243,200 26 33 52 71 111 131 672 1 61,261,200 24 32 52 71 111 131 171 720 -1 73,513,440 25 33 51 71 111 131 171 768 ±19 110,270,160 24 34 51 71 111 131 171 800 1 122,522,400 25 32 52 71 111 131 171 864 -19 147,026,880 26 33 51 71 111 131 171 896 23 183,783,600 24 33 52 71 111 131 171 960 1 245,044,800 26 32 52 71 111 131 171 1008 -19 294,053,760 27 33 51 71 111 131 171 1024 -31 367,567,200 25 33 52 71 111 131 171 1152 1 551,350,800 24 34 52 71 111 131 171 1200 -19 698,377,680 24 33 51 71 111 131 171 191 1280 -1 735,134,400 26 33 52 71 111 131 171 1344 -1 1,102,701,600 25 34 52 71 111 131 171 1440 -1 1,396,755,360 25 33 51 71 111 131 171 191 1536 -1 2,095,133,040 24 34 51 71 111 131 171 191 1600 23 2,205,403,200 26 34 52 71 111 131 171 1680 -1 2,327,925,600 25 32 52 71 111 131 171 191 1728 29 2,793,510,720 26 33 51 71 111 131 171 191 1792 23 3,491,888,400 24 33 52 71 111 131 171 191 1920 -23 4,655,851,200 26 32 52 71 111 131 171 191 2016 1 5,587,021,440 27 33 51 71 111 131 171 191 2048 -23 6,983,776,800 25 33 52 71 111 131 171 191 2304 71 10,475,665,200 24 34 52 71 111 131 171 191 2400 -37 13,967,553,600 26 33 52 71 111 131 171 191 2688 1 20,951,330,400 25 34 52 71 111 131 171 191 2880 -1 27,935,107,200 27 33 52 71 111 131 171 191 3072 -31 41,902,660,800 26 34 52 71 111 131 171 191 3360 -1 48,886,437,600 25 33 52 72 111 131 171 191 3456 -23 64,250,746,560 26 33 51 71 111 131 171 191 231 3584 53 73,329,656,400 24 34 52 72 111 131 171 191 3600 ±1 80,313,433,200 24 33 52 71 111 131 171 191 231 3840 31 97,772,875,200 26 33 52 72 111 131 171 191 4032 29 128,501,493,120 27 33 51 71 111 131 171 191 231 4096 29 146,659,312,800 25 34 52 72 111 131 171 191 4320 23 160,626,866,400 25 33 52 71 111 131 171 191 231 4608 -29 240,940,299,600 24 34 52 71 111 131 171 191 231 4800 29 293,318,625,600 26 34 52 72 111 131 171 191 5040 1 321,253,732,800 26 33 52 71 111 131 171 191 231 5376 37 481,880,599,200 25 34 52 71 111 131 171 191 231 5760 43 642,507,465,600 27 33 52 71 111 131 171 191 231 6144 -29 963,761,198,400 26 34 52 71 111 131 171 191 231 6720 29 1,124,388,064,800 25 33 52 72 111 131 171 191 231 6912 -31 1,606,268,664,000 26 33 53 71 111 131 171 191 231 7168 1 1,686,582,097,200 24 34 52 72 111 131 171 191 231 7200 ±29 1,927,522,396,800 27 34 52 71 111 131 171 191 231 7680 -37 2,248,776,129,600 26 33 52 72 111 131 171 191 231 8064 67 3,212,537,328,000 27 33 53 71 111 131 171 191 231 8192 -1 3,373,164,194,400 25 34 52 72 111 131 171 191 231 8640 1 4,497,552,259,200 27 33 52 72 111 131 171 191 231 9216 43 6,746,328,388,800 26 34 52 72 111 131 171 191 231 10080 1 8,995,104,518,400 28 33 52 72 111 131 171 191 231 10368 ±37 9,316,358,251,200 26 33 52 71 111 131 171 191 231 291 10752 47 13,492,656,777,600 27 34 52 72 111 131 171 191 231 11520 29 18,632,716,502,400 27 33 52 71 111 131 171 191 231 291 12288 ±1 26,985,313,555,200 28 34 52 72 111 131 171 191 231 12960 -43 27,949,074,753,600 26 34 52 71 111 131 171 191 231 291 13440 ±67 32,607,253,879,200 25 33 52 72 111 131 171 191 231 291 13824 1 46,581,791,256,000 26 33 53 71 111 131 171 191 231 291 14336 1 48,910,880,818,800 24 34 52 72 111 131 171 191 231 291 14400 -31 55,898,149,507,200 27 34 52 71 111 131 171 191 231 291 15360 1 65,214,507,758,400 26 33 52 72 111 131 171 191 231 291 16128 37 93,163,582,512,000 27 33 53 71 111 131 171 191 231 291 16384 1 97,821,761,637,600 25 34 52 72 111 131 171 191 231 291 17280 ±37 130,429,015,516,800 27 33 52 72 111 131 171 191 231 291 18432 ±1 195,643,523,275,200 26 34 52 72 111 131 171 191 231 291 20160 37 260,858,031,033,600 28 33 52 72 111 131 171 191 231 291 20736 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

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.