How many factors does a million have?

1 000 000

Printable View

- May 8th 2006, 01:10 PMNatasha1How many factors does a million have?
How many factors does a million have?

1 000 000 - May 8th 2006, 01:52 PMThePerfectHackerQuote:

Originally Posted by**Natasha1**

$\displaystyle \tau (n)$. It is defined as the number of distinct divisors of $\displaystyle n$. For example,

$\displaystyle \tau (3)=2$ cuz 3 only got 2 factors 1 and 3.

There is a formula, if

$\displaystyle n=p_1^{a_1}p_2^{a_2}....p_k^{a_k}$

is the prime-factorization of $\displaystyle n$

Then,

$\displaystyle \tau (n)=(a_1+1)(a_2+1)...(a_k+1)$

Thus, since,

$\displaystyle 1,000,000=10^6=(2\cdot 5)^6=2^6\cdot 5^6$

Thus, $\displaystyle (6+1)(6+1)=7\cdot 7=49$ - May 23rd 2006, 08:08 AMsrulikbdns formula!
:) what is the proof?

- May 23rd 2006, 09:10 AMCaptainBlackQuote:

Originally Posted by**srulikbd**

$\displaystyle

n=p_1^{a_1}p_2^{a_2}....p_k^{a_k}

$

Then any factor $\displaystyle r$ of $\displaystyle n$ is of the form:

$\displaystyle

r=p_1^{b_1}p_2^{b_2}....p_k^{b_k}

$

where $\displaystyle b_i \in \{0,\ 1, \ ..,\ a_i\}$, and each number of this

form is a factor of $\displaystyle n$.

So how many $\displaystyle r$'s are there? Well the first exponent can take

any one of $\displaystyle a_1+1$ values the second can ....

Hence the number of factors is:

$\displaystyle

\prod_{i=1}^n (a_i+1)

$

RonL - May 23rd 2006, 10:31 AMsrulikbdtnx a lot
easy indeed ;)

- May 23rd 2006, 01:25 PMThePerfectHackerQuote:

Originally Posted by**srulikbd**

This one is more advanced but more elegant ;)

**Theorem:**

If $\displaystyle f$ is a number theoretic function which is multiplicative. Then, the function $\displaystyle F$ definied as, $\displaystyle F(n)=\sum_{d|n}f(d)$ is also.

---------

Note that,

$\displaystyle \tau (n)=\sum_{d|n}1$

Since, $\displaystyle f(n)=1$ is multiplicative since,

$\displaystyle f(ab)=f(a)f(b)$ whenever $\displaystyle \gcd(a,b)=1$ we have that,

$\displaystyle \tau(n)$ is mulitplicative.

Since,

$\displaystyle \tau(p^n)=n+1$

You have,

$\displaystyle \tau(p_1^{k_1}\cdot ....\cdot p_s^{k_s})=(k_1+1)\cdot ...\cdot (k_s+1)$

because or multiplicativity.