# Thread: Counting Problem

1. ## 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?

2. 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.

3. 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, $\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.

4. I can understand how to arrive at the first solution using prime factorization. I am still having trouble finding the second solution.

5. 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 $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$