Supercomposite Numbers 8/01
(commonly known as 'highly composite' or sometimes 'versatile' numbers)

Ok, I've often admitted having a certain 'infinity' towards primes, but what would be
the opposite of "prime"? Most would agree it's 'numbers with lots of divisors'! What's 'lots'?

Definition (for positive integers only!)

A supercomposite ('s.c.') number is a number with more divisors than any smaller number.

Recalling that d(n) = number of (positive) divisors of n (including 1 and n)
we can say that n is s.c. if d(n) > d(m) for all m < n.

Example: 12 is s.c. because it has 6 divisors, {1,2,3,4,6,12}, more than any smaller number.

Here is a list (with Mathematica code included) of the first hundred values of d(n):
The s.c. 'versatile' (record-setting) nos. are in green, and the 'practical' (record-tyers) are blue.

Div[n_] := Divisors[n]; d[n_] := Length[Div[n]];
dees = Table[{n,d[n]}, {n,1,100}]; TableForm[dees,TableSpacing->{0,3}]
 ```n d(n) 1 1 2 2 3 2 4 3 5 2 6 4 7 2 8 4 9 3 10 4 11 2 12 6 13 2 14 4 15 4 16 5 17 2 18 6 19 2 20 6``` ```n d(n) 21 4 22 4 23 2 24 8 25 3 26 4 27 4 28 6 29 2 30 8 31 2 32 6 33 4 34 4 35 4 36 9 37 2 38 4 39 4 40 8``` ```n d(n) 41 2 42 8 43 2 44 6 45 6 46 4 47 2 48 10 49 3 50 6 51 4 52 6 53 2 54 8 55 4 56 8 57 4 58 4 59 2 60 12``` ```n d(n) 61 2 62 4 63 6 64 7 65 4 66 8 67 2 68 6 69 4 70 8 71 2 72 12 73 2 74 4 75 6 76 6 77 4 78 8 79 2 80 10``` ```n d(n) 81 5 82 4 83 2 84 12 85 4 86 4 87 4 88 8 89 2 90 12 91 4 92 6 93 4 94 4 95 4 96 12 97 2 98 6 99 6 100 9```

The first several supercomposites are in green; here's a list up to a thousand:
"PFE" means prime factoriz'n exponents: 12 = 2^2 * 3^1 = {2,1}.

Do[If[d[n]>Max[Table[d[m],{m,1,n-1}]],Print[n," ",d[n]]],{n,1,1000}]

(A really simple but inefficient program that makes no use of primes and exponents.)
 ```  n d(n) PFE(n) 1 1 {} 2 2 {1} 4 3 {2} 6 4 {1,1} 12 6 {2,1} 24 8 {3,1} 36 9 {2,2} 48 10 {4,1}``` ```  n d(n) PFE(n) 60 12 {2,1,1} 120 16 {3,1,1} 180 18 {2.2.1} 240 20 {4,1,1} 360 24 {3,2,1} 720 30 {4,2,1} 840 32 {2,1,1,1} ??? ?? {?,?,...}```

This is a cool dot-plot of d(n) vs. n, with the s.c. nos in green.

ds[n_] := Table[{m,d[m]}, {m,1,n}];
jp[n_] := ListPlot[ds[n],PlotJoined->True,
PlotStyle->{GrayLevel[.5],Thickness[.005]}];
dp[n_] := ListPlot[ds[n], PlotStyle->{Hue[0],PointSize[.015]}];
sc[n_] := ListPlot[Table[If[d[k]>Max[Table[d[m],{m,1,k-1}]],{k,d[k]},{1,1}],
{k,1,n}], PlotStyle->{Hue[.4],PointSize[.02]},AxesOrigin->{0,0}];
Show[jp[100],dp[100],sc[100]];

Notice that 6, 12, and 60 seem to 'hang onto their record' for a long time.
In fact, since 2n always has more divisors than n, the maximum ratio
between the next supercomposite and the present one is 2; most are less.

Exponent Structure (of PF of SC nos)

Recall from the number theory page (divisor chart) that d(36) = 3 * 3 because the prime
factorization ('PF') of 36 is 2^2 * 3^2 whose exponents are 2 and 2; denoted {2,2}.
In general if n = p1^e1 * p2^e2 * . . . * pk^ek , then the number of divisors of n is
d(n) = (e1 + 1)(e2 + 1) . . . (ek + 1).

This makes it easy to compute d(n); for example 750 = 2*3*5*5*5 = 2^1 * 3^1 * 5^3 ,
so d(750) = (1+1)(1+1)(3+1) = 2*2*4 = 16.. Sure enough, 750 has 16 divisors:

If n is supercomposite there are several things we can say about the PF of n :

1. No primes are skipped: p1 = 2 , p2 = 3 , p3 = 5 , p4 = 7 , etc.
. . . 35 = 5*7 can't be s.c. because the primes 2 and 3 were skipped;
. . . 6 = 2*3 would have the same number (4) of divisors, and is smaller.

2. The exponents don't increase: e1 >= e2 >= . . . >= ek
. . . 18 = 2^1 * 3^2 can't be s.c. because the exponents are {1,2}, and if we do {2,1}
. . . we get 2^2 * 3^1 = 12 , a smaller number with the same number of divisors.

3. The exponents must obey an infinite number of special inequalities ('Dan's Rules') :
. . . 96 = 2^5 * 3^1 can't be s.c. because it has 'too many 2's' ; d(96) = 12; replacing 96 with
. . . 2^3 * 3^2 = 72 gives a smaller number with at least as many divisors; d(72) = 12.
. . . The exponent transf'm'n {5,1} --> {3,2} could be called the '3/4 rule' bec. 96*3/4 = 72.

Well, that's it for now. Check back often for new stuff!
Click below for other topics, or visit the ask dan page!

[ number theory | geometry | top of page | lessons index]

+ Basic Skills +
Arithmetic, Prealgebra, Beginning Algebra
+ Precalculus +
Intermed.Algebra, Functions & graphs, Trigonometry
+ Calculus +
Limits, Differential Calc, Integral Calc, Vector Calc
+ Beyond Calculus +
Linear Algebra, Diff Equations, Math Major stuff
+ Other Stuff + You are here
Statistics, Number Theory, Geometry, Other requests?

[ home | info | meet dan | ask dan | dvc ]

This site maintained by B & L Web Design, a division of B & L Math Enterprises.