Thread: Give a general algorithm/formula for finding the power ai

1. 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)

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

2. Originally Posted by nacknacka
Hi, I've this is my homework I've been given and I can only manage part i) and iii)

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 $\displaystyle \alpha$ of a prime p that divides n! is $\displaystyle \alpha=\sum^\infty_{k=1}\left[\frac{n}{p^k}\right]$ , with $\displaystyle [x]=$ the floor function. Note that:

1) the sum is finite {why?}

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

Tonio

3. Hello, nacknacka!

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

$\displaystyle (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: .$\displaystyle \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: .$\displaystyle \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: .$\displaystyle \left[\frac{400}{125}\right] \:=\:3$ more factors-of-5.

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

Therefore, 400! ends with 99 zeroes.

4. Hello, nacknacka!

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

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

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

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

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

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

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

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

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

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

Therefore: . $\displaystyle 18! \;=\;2^{16}\cdot3^8\cdot5^3\cdot7^2\cdot11\cdot13\ cdot17$

5. 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: .$\displaystyle \left[\frac{18}{2}\right] \:=\:9$ factors-of-2.

.
.
.

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

$\displaystyle 18!=18*17*16*15*14*13*12*11*10*9*8*7*6*5*4*3*2$ = $\displaystyle (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$ =$\displaystyle 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