Results 1 to 5 of 5

Math Help - Counting Problem

  1. #1
    Member
    Joined
    Mar 2010
    Posts
    144

    Counting Problem

    How many ways can 1,000,000 be expressed as a product of two natural numbers? (View 100*10,000 as different from 10,000*100.) As a product of three natural numbers?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    I'll give this a go...

    Factorise it into primes.

    1000000 = 2^6 5^6.

    Rewrite as

    2x2x2x2x2x2x5x5x5x5x5x5

    Then form two groups with that.

    For example,

    2x2 2x2x2x2x5x5x5x5x5x5 (=4 x 250000)

    I'll leave it to you to figure out how many ways there is but that's a start for ya.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by MATNTRNG View Post
    How many ways can 1,000,000 be expressed as a product of two natural numbers? (View 100*10,000 as different from 10,000*100.) As a product of three natural numbers?
    n=1,000,000=2^6*5^6

    The first problem is simply the number of divisors of n, \sigma_0(n).

    Each prime factor can have an exponent between 0 and 6 inclusive, so there are 7*7=49 divisors.

    (Edit: original solution for second problem was wrong.)

    I think the easiest way to approach the second problem is to think in terms of n=k_1k_2k_3 in that order and first pick k_1 (there are 49 ways) and then look at m=k_2k_3 and proceed in the manner of the first problem. I'll leave the details to you.
    Last edited by undefined; April 21st 2010 at 07:37 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Mar 2010
    Posts
    144
    I can understand how to arrive at the first solution using prime factorization. I am still having trouble finding the second solution.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1

    Post

    Quote Originally Posted by MATNTRNG View Post
    I can understand how to arrive at the first solution using prime factorization. I am still having trouble finding the second solution.
    So reviewing the problem statement, remember the order of the factors matters, so 1\cdot1\cdot10^6 is distinct from 1\cdot10^6\cdot1.

    We let n=k_1k_2k_3, and then we fix k_1.

    There are 49 cases. Each case will contribute some number of factorisations. At the end we will need to add the number of factorisations from each case together to arrive at the final answer.

    Case k_1=1:

    Write n_2=k_2k_3

    10^6=k_2k_3

    There are 49 ways for this, as already found.

    Case k_1=2:

    Write n_2=k_2k_3

    2^5\cdot5^6=k_2k_3

    We need to count the divisors of 2^5\cdot5^6. All we need are the exponents; multiply (5+1)\cdot(6+1)=6\cdot 7=42. There are 42 ways in this case.

    Case k_1=5:

    Write n_2=k_2k_3

    2^6\cdot5^5=k_2k_3

    We need to count the divisors of 2^6\cdot5^5. All we need are the exponents; multiply (6+1)\cdot(5+1)=7\cdot 6=42. There are 42 ways in this case.

    Case k_1=10:

    Write n_2=k_2k_3

    2^5\cdot5^5=k_2k_3

    We need to count the divisors of 2^5\cdot5^5. All we need are the exponents; multiply (5+1)\cdot(5+1)=6\cdot 6=36. There are 36 ways in this case.

    ...

    Case k_1=10^6:

    Write n_2=k_2k_3

    1=k_2k_3

    We need to count the divisors of 1. There is 1 way in this case.

    At the end, add up 49+42+42+36+\cdots+1 to get the final answer. The final answer can also be expressed compactly using a double summation symbol.

    \sum_{i=0}^6\sum_{j=0}^6(i+1)\cdot(j+1)

    Equivalently,

    \sum_{i=1}^7\sum_{j=1}^7i\cdot j
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. A counting problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 19th 2011, 05:19 AM
  2. Counting Problem Help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 9th 2010, 06:20 PM
  3. Counting Problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 27th 2010, 04:10 PM
  4. Replies: 3
    Last Post: April 13th 2009, 06:42 PM
  5. Counting problem
    Posted in the Statistics Forum
    Replies: 5
    Last Post: November 17th 2008, 05:10 PM

Search Tags


/mathhelpforum @mathhelpforum