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

- Apr 21st 2010, 05: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?

- Apr 21st 2010, 06: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. - Apr 21st 2010, 06:18 PMundefined
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 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, 12:03 PMundefined
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$