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
    9
    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
    9
    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
    9
    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, 08:39 PM
  2. Composite Numbers
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 2nd 2010, 03:42 PM
  3. composite numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 10th 2009, 12:52 PM
  4. Composite numbers
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: January 5th 2009, 10:19 AM
  5. Composite Numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 19th 2007, 07:41 AM

Search Tags


/mathhelpforum @mathhelpforum