Highly Composite Numbers
   

   

 Math Help -> Number Theory -> Factors, Coprimes, Totient -> Highly Composite Numbers 

Highly Composite Numbers

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
2212 0
4223 ±1
621 314 ±1
1222 316 ±1
2423 3185-1
3622 329 1
4824 31107-1
6022 31 5112 ±1
12023 31 511611±7
18022 32 5118 ±1
24024 31 5120 ±1
36023 32 512419-1
72024 32 5130 -1
84023 31 51 713229-1
1,26022 32 51 7136 -1
1,68024 31 51 714041-11
2,52023 32 51 7148 1
5,04024 32 51 716071-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 131240 -17
1,081,08023 33 51 71 111 131256 -1
1,441,44025 32 51 71 111 131288 -1
2,162,16024 33 51 71 111 131320 17
2,882,88026 32 51 71 111 131336 ±17
3,603,60024 32 52 71 111 131360 -17
4,324,32025 33 51 71 111 131384 1
6,486,48024 34 51 71 111 131400 -1
7,207,20025 32 52 71 111 131432 -19
8,648,64026 33 51 71 111 131448 37
10,810,80024 33 52 71 111 131480 -37
14,414,40026 32 52 71 111 131504 1
17,297,28027 33 51 71 111 1315124159±17
21,621,60025 33 52 71 111 131576 -23
32,432,40024 34 52 71 111 131600 -1
36,756,72024 33 51 71 111 131 171640 29
43,243,20026 33 52 71 111 131672 1
61,261,20024 32 52 71 111 131 171720 -1
73,513,44025 33 51 71 111 131 171768 ±19
110,270,16024 34 51 71 111 131 171800 1
122,522,40025 32 52 71 111 131 171864 -19
147,026,88026 33 51 71 111 131 171896 23
183,783,60024 33 52 71 111 131 171960 1
245,044,80026 32 52 71 111 131 1711008 -19
294,053,76027 33 51 71 111 131 1711024 -31
367,567,20025 33 52 71 111 131 1711152 1
551,350,80024 34 52 71 111 131 1711200 -19
698,377,68024 33 51 71 111 131 171 1911280 -1
735,134,40026 33 52 71 111 131 1711344 -1
1,102,701,60025 34 52 71 111 131 1711440 -1
1,396,755,36025 33 51 71 111 131 171 1911536 -1
2,095,133,04024 34 51 71 111 131 171 1911600 23
2,205,403,20026 34 52 71 111 131 1711680 -1
2,327,925,60025 32 52 71 111 131 171 1911728 29
2,793,510,72026 33 51 71 111 131 171 1911792 23
3,491,888,40024 33 52 71 111 131 171 1911920 -23
4,655,851,20026 32 52 71 111 131 171 1912016 1
5,587,021,44027 33 51 71 111 131 171 1912048 -23
6,983,776,80025 33 52 71 111 131 171 1912304 71
10,475,665,20024 34 52 71 111 131 171 1912400 -37
13,967,553,60026 33 52 71 111 131 171 1912688 1
20,951,330,40025 34 52 71 111 131 171 1912880 -1
27,935,107,20027 33 52 71 111 131 171 1913072 -31
41,902,660,80026 34 52 71 111 131 171 1913360 -1
48,886,437,60025 33 52 72 111 131 171 1913456 -23
64,250,746,56026 33 51 71 111 131 171 191 2313584 53
73,329,656,40024 34 52 72 111 131 171 1913600 ±1
80,313,433,20024 33 52 71 111 131 171 191 2313840 31
97,772,875,20026 33 52 72 111 131 171 1914032 29
128,501,493,12027 33 51 71 111 131 171 191 2314096 29
146,659,312,80025 34 52 72 111 131 171 1914320 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 1915040 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 the Math Help site is Graeme McRae.
     [home]  [email]  [search]  [Links to Math Sites]  [Whiteboard]