![Highly composite number Cuisenaire rods 6](https://upload.wikimedia.org/wikipedia/commons/d/d0/Highly_composite_number_Cuisenaire_rods_6.png)
__FORCETOC__
A highly composite number is a
positive
Positive is a property of positivity and may refer to:
Mathematics and science
* Positive formula, a logical formula not containing negation
* Positive number, a number that is greater than 0
* Plus sign, the sign "+" used to indicate a posit ...
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
with more
divisor
In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...
s than any smaller positive integer has. The related concept of largely composite number refers to a positive integer which has at least as many divisors as any smaller positive integer. The name can be somewhat misleading, as the first two highly composite numbers (1 and 2) are not actually
composite number
A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor other than 1 and itself. Every positive integer is composite, prime, ...
s; however, all further terms are.
The late mathematician
Jean-Pierre Kahane
Jean-Pierre Kahane (11 December 1926 – 21 June 2017) was a French mathematician with contributions to harmonic analysis.
Career
Kahane attended the École normale supérieure and obtained the ''agrégation'' of mathematics in 1949. He then wor ...
has suggested that
Plato
Plato ( ; grc-gre, Πλάτων ; 428/427 or 424/423 – 348/347 BC) was a Greek philosopher born in Athens during the Classical period in Ancient Greece. He founded the Platonist school of thought and the Academy, the first institution ...
must have known about highly composite numbers as he deliberately chose
5040 as the ideal number of citizens in a city as 5040 has more divisors than any numbers less than it.
Ramanujan wrote and titled his paper on the subject in 1915.
Examples
The initial or smallest 38 highly composite numbers are listed in the table below . The number of divisors is given in the column labeled ''d''(''n''). Asterisks indicate
superior highly composite number
In mathematics, a superior highly composite number is a natural number which has the highest ratio of its number of divisors to ''some'' positive power of itself than any other number. It is a stronger restriction than that of a highly composite ...
s.
The divisors of the first 15 highly composite numbers are shown below.
The table below shows all 72 divisors of 10080 by writing it as a product of two numbers in 36 different ways.
The 15,000th highly composite number can be found on Achim Flammenkamp's website. It is the product of 230 primes:
:
where
is the sequence of successive prime numbers, and all omitted terms (''a''
22 to ''a''
228) are factors with exponent equal to one (i.e. the number is
). More concisely, it is the product of seven distinct primorials:
:
where
is the
primorial
In mathematics, and more particularly in number theory, primorial, denoted by "#", is a function from natural numbers to natural numbers similar to the factorial function, but rather than successively multiplying positive integers, the function ...
.
Prime factorization
Roughly speaking, for a number to be highly composite it has to have
prime factor
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s as small as possible, but not too many of the same. By the
fundamental theorem of arithmetic
In mathematics, the fundamental theorem of arithmetic, also called the unique factorization theorem and prime factorization theorem, states that every integer greater than 1 can be represented uniquely as a product of prime numbers, up to the ord ...
, every positive integer ''n'' has a unique prime factorization:
:
where
are prime, and the exponents
are positive integers.
Any factor of n must have the same or lesser multiplicity in each prime:
:
So the number of divisors of ''n'' is:
:
Hence, for a highly composite number ''n'',
* the ''k'' given prime numbers ''p''
''i'' must be precisely the first ''k'' prime numbers (2, 3, 5, ...); if not, we could replace one of the given primes by a smaller prime, and thus obtain a smaller number than ''n'' with the same number of divisors (for instance 10 = 2 × 5 may be replaced with 6 = 2 × 3; both have four divisors);
* the sequence of exponents must be non-increasing, that is
; otherwise, by exchanging two exponents we would again get a smaller number than ''n'' with the same number of divisors (for instance 18 = 2
1 × 3
2 may be replaced with 12 = 2
2 × 3
1; both have six divisors).
Also, except in two special cases ''n'' = 4 and ''n'' = 36, the last exponent ''c''
''k'' must equal 1. It means that 1, 4, and 36 are the only square highly composite numbers. Saying that the sequence of exponents is non-increasing is equivalent to saying that a highly composite number is a product of
primorials or, alternatively, the smallest number for its
prime signature.
Note that although the above described conditions are necessary, they are not sufficient for a number to be highly composite. For example, 96 = 2
5 × 3 satisfies the above conditions and has 12 divisors but is not highly composite since there is a smaller number 60 which has the same number of divisors.
Asymptotic growth and density
If ''Q''(''x'') denotes the number of highly composite numbers less than or equal to ''x'', then there are two constants ''a'' and ''b'', both greater than 1, such that
:
The first part of the inequality was proved by
Paul Erdős
Paul Erdős ( hu, Erdős Pál ; 26 March 1913 – 20 September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in ...
in 1944 and the second part by
Jean-Louis Nicolas
Jean-Louis Nicolas is a French number theorist.
He is the namesake (with Paul Erdős) of the Erdős–Nicolas numbers, and was a frequent co-author of Erdős, who would take over the desk of Nicolas' wife Anne-Marie (also a mathematician) whenev ...
in 1988. We have
[Sándor et al. (2006) p. 45]
:
and
:
Related sequences
Highly composite numbers higher than 6 are also
abundant number
In number theory, an abundant number or excessive number is a number for which the sum of its proper divisors is greater than the number. The integer 12 is the first abundant number. Its proper divisors are 1, 2, 3, 4 and 6 for a total of 16. The ...
s. One need only look at the three largest proper divisors of a particular highly composite number to ascertain this fact. It is false that all highly composite numbers are also
Harshad number
In mathematics, a harshad number (or Niven number) in a given number base is an integer that is divisible by the sum of its digits when written in that base.
Harshad numbers in base are also known as -harshad (or -Niven) numbers.
Harshad numbers ...
s in base 10. The first HCN that is not a Harshad number is 245,044,800, which has a digit sum of 27, but 27 does not divide evenly into 245,044,800.
10 of the first 38 highly composite numbers are
superior highly composite number
In mathematics, a superior highly composite number is a natural number which has the highest ratio of its number of divisors to ''some'' positive power of itself than any other number. It is a stronger restriction than that of a highly composite ...
s.
The sequence of highly composite numbers is a subset of the sequence of smallest numbers ''k'' with exactly ''n'' divisors .
Highly composite numbers whose number of divisors is also a highly composite number are for n = 1, 2, 6, 12, 60, 360, 1260, 2520, 5040, 55440, 277200, 720720, 3603600, 61261200, 2205403200, 293318625600, 6746328388800, 195643523275200 . It is extremely likely that this sequence is complete.
A positive integer ''n'' is a largely composite number if ''d''(''n'') ≥ ''d''(''m'') for all ''m'' ≤ ''n''. The counting function ''Q''
''L''(''x'') of largely composite numbers satisfies
:
for positive ''c'',''d'' with
.
[Sándor et al. (2006) p. 46]
Because the prime factorization of a highly composite number uses all of the first ''k'' primes, every highly composite number must be a
practical number
In number theory, a practical number or panarithmic number is a positive integer n such that all smaller positive integers can be represented as sums of distinct divisors of n. For example, 12 is a practical number because all the numbers from 1 ...
.
[.] Due to their ease of use in calculations involving
fraction
A fraction (from la, fractus, "broken") represents a part of a whole or, more generally, any number of equal parts. When spoken in everyday English, a fraction describes how many parts of a certain size there are, for example, one-half, eight ...
s, many of these numbers are used in
traditional systems of measurement and engineering designs.
See also
*
Superior highly composite number
In mathematics, a superior highly composite number is a natural number which has the highest ratio of its number of divisors to ''some'' positive power of itself than any other number. It is a stronger restriction than that of a highly composite ...
*
Highly totient number A highly totient number k is an integer that has more solutions to the equation \phi(x) = k, where \phi is Euler's totient function, than any integer below it. The first few highly totient numbers are
1, 2, 4, 8, 12, 24, 48, 72, 144, 240, ...
*
Table of divisors
*
Euler's totient function
In number theory, Euler's totient function counts the positive integers up to a given integer that are relatively prime to . It is written using the Greek letter phi as \varphi(n) or \phi(n), and may also be called Euler's phi function. In ot ...
*
Round number
A round number is an integer that ends with one or more " 0"s (zero-digit) in a given base. So, 590 is rounder than 592, but 590 is less round than 600. In both technical and informal language, a round number is often interpreted to stand for a ...
*
Smooth number
In number theory, an ''n''-smooth (or ''n''-friable) number is an integer whose prime factors are all less than or equal to ''n''. For example, a 7-smooth number is a number whose every prime factor is at most 7, so 49 = 72 and 15750 = 2 × 32 × ...
Notes
References
*
*
*
* Annotated and with a foreword by Jean-Louis Nicolas and Guy Robin.
External links
*
Algorithm for computing Highly Composite NumbersFirst 10000 Highly Composite Numbers as factors
5040 and other Anti-Prime Numbers - Dr. James Grimeby
Dr. James Grime for
Numberphile
''Numberphile'' is an educational YouTube channel featuring videos that explore topics from a variety of fields of mathematics. In the early days of the channel, each video focused on a specific number, but the channel has since expanded its s ...
{{Classes of natural numbers
Integer sequences