# Counting Problem

• Apr 21st 2010, 05:28 PM
MATNTRNG
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?
• Apr 21st 2010, 06:10 PM
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.
• Apr 21st 2010, 06:18 PM
undefined
Quote:

Originally Posted by MATNTRNG
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, $\displaystyle \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 $\displaystyle n=k_1k_2k_3$ in that order and first pick $\displaystyle k_1$ (there are 49 ways) and then look at $\displaystyle m=k_2k_3$ and proceed in the manner of the first problem. I'll leave the details to you.
• May 4th 2010, 09:35 AM
MATNTRNG
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, 12:03 PM
undefined
Quote:

Originally Posted by MATNTRNG
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 $\displaystyle 1\cdot1\cdot10^6$ is distinct from $\displaystyle 1\cdot10^6\cdot1$.

We let $\displaystyle n=k_1k_2k_3$, and then we fix $\displaystyle 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 $\displaystyle k_1=1$:

Write $\displaystyle n_2=k_2k_3$

$\displaystyle 10^6=k_2k_3$

There are 49 ways for this, as already found.

Case $\displaystyle k_1=2$:

Write $\displaystyle n_2=k_2k_3$

$\displaystyle 2^5\cdot5^6=k_2k_3$

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

Case $\displaystyle k_1=5$:

Write $\displaystyle n_2=k_2k_3$

$\displaystyle 2^6\cdot5^5=k_2k_3$

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

Case $\displaystyle k_1=10$:

Write $\displaystyle n_2=k_2k_3$

$\displaystyle 2^5\cdot5^5=k_2k_3$

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

...

Case $\displaystyle k_1=10^6$:

Write $\displaystyle n_2=k_2k_3$

$\displaystyle 1=k_2k_3$

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

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

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

Equivalently,

$\displaystyle \sum_{i=1}^7\sum_{j=1}^7i\cdot j$