Results 1 to 5 of 5

Math Help - Give a general algorithm/formula for finding the power ai

  1. #1
    Newbie
    Joined
    May 2010
    Posts
    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by nacknacka View Post
    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 \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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,546
    Thanks
    539
    Hello, nacknacka!

    Your answer to (iii) is off . . .


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

    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,546
    Thanks
    539
    Hello, nacknacka!

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


    (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

    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Mar 2010
    Posts
    906
    Thanks
    204
    Quote Originally Posted by Soroban View Post
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 7
    Last Post: October 21st 2011, 03:57 AM
  2. Replies: 5
    Last Post: September 8th 2010, 08:32 PM
  3. Finding a formula for a matrix raised to the nth power
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: August 5th 2009, 04:03 PM
  4. finding general algorithm
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 11th 2008, 05:12 AM
  5. Algorithm for computing power sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 18th 2007, 05:59 AM

Search Tags


/mathhelpforum @mathhelpforum