Results 1 to 4 of 4

Math Help - Highly Composite Numbers

  1. #1
    Member
    Joined
    May 2006
    Posts
    148
    Thanks
    1

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by fifthrapiers View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by fifthrapiers View Post
    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".
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by fifthrapiers View Post

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Composite numbers
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 12th 2010, 09:39 PM
  2. Composite Numbers
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 2nd 2010, 04:42 PM
  3. composite numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 10th 2009, 01:52 PM
  4. Composite numbers
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: January 5th 2009, 11:19 AM
  5. Composite Numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 19th 2007, 08:41 AM

Search Tags


/mathhelpforum @mathhelpforum