Give a general algorithm/formula for finding the power ai

Printable View

May 4th 2010, 06:25 AM
nacknacka

Give a general algorithm/formula for finding the power ai

Hi, I've this is my homework I've been given and I can only manage part i) and iii)

http://img535.imageshack.us/img535/7...ersproblem.png

My work for part

i)

2x(3^2)

iii)

A zero appears at the end of the solution (as we go from 1! to 400!) every time we cross a number ending in 5 and every time we cross a number ending in 0.

Two zeros appear every time we cross a number ending in 50 and every time we cross a number ending in 00, However, this includes numbers already counted above (beware of double counting.

Number of numbers ending in "5" : 40
Number of numbers ending in "00" : 4 (100, 200, 300, 400)
Number of numbers ending in "50" : 4 (50, 150, 250, 350)
Number of remaining numbers ending with one "0" : 32 = 4*8 (10, 20, 30, 40, 60, 70, 80, 90 for each hundred).

Expected number of zeros at the end of the number = 40 + 8 + 8 + 32 = 88
May 4th 2010, 09:16 AM
tonio

Quote:

Originally Posted by nacknacka

Hi, I've this is my homework I've been given and I can only manage part i) and iii)

http://img535.imageshack.us/img535/7...ersproblem.png

My work for part

i)

2x(3^2)

iii)

A zero appears at the end of the solution (as we go from 1! to 400!) every time we cross a number ending in 5 and every time we cross a number ending in 0.

Two zeros appear every time we cross a number ending in 50 and every time we cross a number ending in 00, However, this includes numbers already counted above (beware of double counting.

Number of numbers ending in "5" : 40
Number of numbers ending in "00" : 4 (100, 200, 300, 400)
Number of numbers ending in "50" : 4 (50, 150, 250, 350)
Number of remaining numbers ending with one "0" : 32 = 4*8 (10, 20, 30, 40, 60, 70, 80, 90 for each hundred).

Expected number of zeros at the end of the number = 40 + 8 + 8 + 32 = 88

For (ii) The maximal power $\alpha$ of a prime p that divides n! is $\alpha=\sum^\infty_{k=1}\left[\frac{n}{p^k}\right]$ , with $[x]=$ the floor function. Note that:

1) the sum is finite {why?}

2) In fact $\alpha=\frac{n-\sum^\infty_{k=0}a_i}{p-1}$ , where $n=a_0+a_1p+a_2p^2+...=$ the expression of n in base p.

Tonio
May 4th 2010, 10:52 AM
Soroban

Hello, nacknacka!

Your answer to $(iii)$ is off . . .

Quote:

$(iii)$ Find the number of final zeroes in the base-ten representation of 400!

Every factor-of-5 (combined with a factor of 2) produces a final zero.

How many factors-of-5 are contained in 400-factorial?

Every 5th number contains a factor-of-5: . $\left[\frac{400}{5}\right] \:=\:80$ factors-of-5.

But every 25th number contains a factor of 5²
. . each of which contributes another factor-of-5: . $\left[\frac{400}{25}\right] \:=\:16$ more factors-of-5.

And every 125th number contains a factor of 5³,
. . each of which contributes yet another factor-of-5: . $\left[\frac{400}{125}\right] \:=\:3$ more factors-of-5.

Hence, there are: . $80 + 16 + 3 \:=\:99$ factors-of-5.

Therefore, 400! ends with 99 zeroes.
May 4th 2010, 11:25 AM
Soroban

Hello, nacknacka!

You can probably anticipate my approach to the first problem . . .

Quote:

$(i)$ Find the prime factorization of 18!

Factors-of-2
Every 2nd number contains a factor of 2: . $\left[\frac{18}{2}\right] \:=\:9$ factors-of-2.
But every 4th number contains $2^2$ .
. . each of which contributes anothter factor-of-2: . $\left[\frac{18}{4}\right] \:=\:4$ more factors-of-2.
And every 8th number contains $2^3$
. . each of which contributes yet another factor-of-2: . $\left[\frac{18}{8}\right] \:=\:2$ more factors-of-2.
And every 16th number contains $2^4$
. . each of which contributes yet another factor-of-2: . $\left[\frac{18}{16}\right] \:=\:1$ more factors-of-2.
Hence, 18! contains sixteen 2's: . $2^{16}$

Factors-of-3
Every 3rd number contains a factor of 3: . $\left[\frac{18}{3}\right] \:=\:6$ factors-of-3
But every 9th number contains $3^2$
. . each of which contributes another factor-of-3: . $\left[\frac{18}{9}\right] \:=\:2$ more factors-of-3
Hence, 18! contains eight 3's: . $3^8$

Factors-of-5
Every 5th number contains a factor-of-5: . $\left[\frac{18}{5}\right] \:=\:3$ factors-of-5
Hence, 18! contains three 5's: . $3^5$

Factors-of-7
Every 7th number contains a factor-of-7: . $\left[\frac{18}{7}\right] \:=\:2$ factors-of-7

Factors-of-11, 13, 17
Every 11th number contains a factor-of-11: . $\left[\frac{18}{11}\right] \:=1$ factor-of-11

Every 13th number contains a factor-of-13: . $\left[\frac{18}{13}\right] \:=\:1$ factor-of-13

Every 17th number contains a factor-of-17: . $\left[\frac{18}{17}\right] \:=\:1$ factor-of-17

Hence, 18! contains: . $11\cdot13\cdot17$

Therefore: . $18! \;=\;2^{16}\cdot3^8\cdot5^3\cdot7^2\cdot11\cdot13\ cdot17$
May 4th 2010, 07:15 PM
hollywood

Quote:

Originally Posted by Soroban

Hello, nacknacka!

You can probably anticipate my approach to the first problem . . .

Factors-of-2
Every 2nd number contains a factor of 2: . $\left[\frac{18}{2}\right] \:=\:9$ factors-of-2.

.
.
.

For (i), there's always the brute force method:

$18!=18*17*16*15*14*13*12*11*10*9*8*7*6*5*4*3*2$ = $(2*3^2)*17*2^4*(3*5)*(2*7)*13*(2^2*3)*11*(2*5)*3^2 *2^3*7*(2*3)*5*2^2*3*2$ = $2^16*3^8*5^3*7^2*11*13*17$ which, of course, is the answer Soroban got.

For (iv), Soroban's method works for prime bases. For composite bases, you need to look at each prime factor of the base separately. In our base 10 example, there were plenty of factors of 2, so only the factors of 5 mattered.

- Hollywood