Thread: Highly Composite Numbers

PROBLEM BELOW (Note, for this prob., you will need to know tau is the numbers of divisors function.



A positive integer n, n > = 1, is said to be highly composite if tau(m) < tau(n) for all pos. integers m < n. The first 6 highly composite integers are 1, 2, 4, 6, 12, 24, 36, 48.

1.) Show if n is highly composite int., and also m is a pos. int. with tau(m) > tau(n), then there will exist a highly composite int. k such that n < k <= m.

HINT: You don't need to use formula of tau(n); only use the fact that you're looking at the sequence of integers: tau(1), tau(2), tau(3), ..., tau(n), ..., tau(m).

2.) From #1, conclude that there exists an infinite number of highly composite integers,

3.) Prove if n is a highly composite int., then n = 2^(a_1)*3^(a_2)*5^(a_3)*...*p_(k)^(a_k), where p_k is the k-th prime and a_1 >= a_2 >= a_3 >= ... >= a_k >= 0.

HINT: prove by contrapositive. Two cases to consider --> 1st case: assume n is missing a prime which says there exists an i where p_i and P_(i + 2) are factors of n, but p_(i + 1) is not a factor of n.
2nd case: assume that the a's are not in non- increasing order, which says that there exists an i such that a_i <= a_(i + 1)

Note the converse is not true.
n = 72 = 2^3*3^2 doesn't skip primes and the exponents are decreasing. Yet, tau(6) = tau(72) = 12, and thus 72 is not highly composite.

Originally Posted by fifthrapiers

PROBLEM BELOW (Note, for this prob., you will need to know tau is the numbers of divisors function.



A positive integer n, n > = 1, is said to be highly composite if tau(m) < tau(n) for all pos. integers m < n. The first 6 highly composite integers are 1, 2, 4, 6, 12, 24, 36, 48.

1.) Show if n is highly composite int., and also m is a pos. int. with tau(m) > tau(n), then there will exist a highly composite int. k such that n < k <= m.

It is an easy proof. Since n is highly composite we have that t(n)>t(i) for all 1<=i<n.
Now we are told that t(m)>t(n).
Therefore m>n because otherwise m<=n contradicts the fact that n is highly composite.
Now consider the list of integers,
t(1),t(2),t(3),...,t(n),t(n+1),...,t(m)
Look at the sublist,
t(n+1),t(n+2),...,t(m)
And choose the smallest maximal element (possible because this is finite).*
Call it k, thus, n<k<=m.
By our choice of k we have that t(k)>=t(i) for all n+1<=i<=m.
But we also have that t(k)>=t(m)>t(n)>t(j) for all 1<=j<n.
Thus, t(k)>=t(j) for all 1<=j<=k
Thus, t(k)>t(j) for all 1<=j<k by our choice of smallest.
Thus, by definition k is highly composite.
Q.E.D.

*)Given a non-empty set S of positive integers a "maximal element" is M so that M>=x for all x in S.
By smallest I mean the first in the list.

Originally Posted by fifthrapiers

2.) From #1, conclude that there exists an infinite number of highly composite integers,

Theorem: Given a positive integer n, then there exists another positive integer m>n so that t(n)<t(m).

Proof: The proof should seem obvious. Given any positive integer, you can find a huge number with many factors which will certainly exceede in number of divisors.
Here is the formal proof.
Given any positive integer n choose an odd prime p which does not divide n. Which is possible because there are infinitely many odd primes and n cannot contain all of them.
That means the gcd(p,n)=1.
Therefore choose m=p*n.
Thus, m>n certainly and t(m)=t(p*n)=t(p)*t(n)>t(n). (tau number function is weakly multiplicative).
By our previous observation there shall exist another highly composite number k, so that, n<k<=m.
Q.E.D.

Theorem: There are infinitely many highly composite number.

Proof: It is basically the proof above just expressed in mathematical rigor language. Assume that there are only finitely many in sake of a contradiction. Let S be the set of all highly composite numbers. This set is non-empty because 2 is in S (which I find funny because, 2, a prime, is highly composite ). Since this set is finite it has a maximal element*.
Call it t(M). Then by the previous theorem you can find N>M so that t(N)>t(M) where N is highly composite. Then N is not an element in the set because N is larger than all the elements. A contradiction. Thus there are infinitely many highly composite numbers.
Q.E.D.

*)Finite totally ordered sets always have maximal elements. This is a theorem in set theory. It should seem "obvious".

Originally Posted by fifthrapiers

3.) Prove if n is a highly composite int., then n = 2^(a_1)*3^(a_2)*5^(a_3)*...*p_(k)^(a_k), where p_k is the k-th prime and a_1 >= a_2 >= a_3 >= ... >= a_k >= 0.

That theorem is not completely true. It should say that if n>1 and highly composite ....

I am not going to prove by contrapositive. I will prove by contradiction (if that is what you really mean).

I want to show a_1>=a_2. Say a_1<a_2. Then form the number:
N=2^(a_2)*3^(a_1)*5^(a_3)*....*p_k^(a_k)
It is easy to see that N<n because we assumed a_1<a_2.
But yet, t(n)=(a_1+1)(a_2+1)...(a_k+1) and t(N)=(a_2+1)(a_1+1)...(a_k+1).
Thus, t(N)=t(n) and N<n.
Contradiction because n is highly composite.

I want to show that a_2>=a_3. Say a_2<a_3. Then form the number:
N=2^(a_1)*3^(a_3)*5^(a_2)*...*p_k^(a_k)
Again t(N)=t(n) with N<n.

Similarly for a_3>=a_4. And so on.

Thus, we shown that a_1>=a_2>=a_3>=...>=a_k
Q.E.D.