Results 1 to 2 of 2

Math Help - Primes help

  1. #1
    Junior Member
    Joined
    Jan 2009
    Posts
    57

    Primes help

    I need help with this question please!

    Create a formula (using sigma, logs, floor function) that computes the exponent of any particular prime in the prime factorization of a given factorial.

    we use the notation
    exp(p, n!) = the exponent of prime p in the prime factorization of n!

    Example: exp(5, 25!) = 6

    help please!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    408

    A Simple Formula

    exp(p, n!) = \sum_{i=1}^{\infty} \lfloor \frac{n}{p^i}\rfloor

    For example, 625! contains 125 multiples of 5, 25 multiples of 25, 5 multiples of 125, and 1 multiple of 625, thus exp(5, 625!) = 125+25+5+1 = 156 .

    If you're actually going to use this in practice, the \infty is not necessary. Since \lfloor \frac{n}{p^i}\rfloor = 0 for  n<p^i , you only have to sum up to i=\lfloor \frac{ln(n)}{ln(p)} \rfloor , but that doesn't make for as pretty of a formula.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. primes
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 2nd 2010, 10:18 AM
  2. Primes
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 8th 2009, 01:26 PM
  3. Primes
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 12th 2009, 09:59 PM
  4. Help with primes
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: January 20th 2009, 08:01 PM
  5. primes
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 16th 2008, 12:21 AM

Search Tags


/mathhelpforum @mathhelpforum