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?

Printable View

- April 21st 2010, 06:28 PMMATNTRNGCounting 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?

- April 21st 2010, 07:10 PMDeadstar
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. - April 21st 2010, 07:18 PMundefined
n=1,000,000=2^6*5^6

The first problem is simply the number of divisors of 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**in that order**and first pick (there are 49 ways) and then look at and proceed in the manner of the first problem. I'll leave the details to you. - May 4th 2010, 10:35 AMMATNTRNG
I can understand how to arrive at the first solution using prime factorization. I am still having trouble finding the second solution.

- May 4th 2010, 01:03 PMundefined
So reviewing the problem statement, remember the order of the factors matters, so is distinct from .

We let , and then we fix .

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**:

Write

There are**49**ways for this, as already found.

**Case**:

Write

We need to count the divisors of . All we need are the exponents; multiply . There are**42**ways in this case.

**Case**:

Write

We need to count the divisors of . All we need are the exponents; multiply . There are**42**ways in this case.

**Case**:

Write

We need to count the divisors of . All we need are the exponents; multiply . There are**36**ways in this case.

...

**Case**:

Write

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

At the end, add up to get the final answer. The final answer can also be expressed compactly using a double summation symbol.

Equivalently,