Results 1 to 2 of 2

Math Help - finding the sum of series

  1. #1
    Member
    Joined
    Nov 2010
    Posts
    95

    finding the sum of series

    hi, if a and p are relativly co-prime integers, then is there any efficient way of calculating the following:
    (\sum_{k=0}^n\frac{1}{a^k}) \% p ? here n and p can be as large as: 0 ≤ N ≤ 2147483647, 2 ≤ P ≤ 2147483647 thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4

    Re: finding the sum of series

    Quote Originally Posted by pranay View Post
    hi, if a and p are relativly co-prime integers, then is there any efficient way of calculating the following:
    (\sum_{k=0}^n\frac{1}{a^k}) \% p ? here n and p can be as large as: 0 ≤ N ≤ 2147483647, 2 ≤ P ≤ 2147483647 thanks
    Well the series is a geometric series so can be summed to:

    \sum_{k=0}^n a^{-k}=\frac{1-a^{-(n+1)}}{1-a^{-1}}

    so you question becomes one of evaluating

    \frac{1-a^{-(n+1)}}{1-a^{-1}} \text{ mod } p

    efficiently.

    It might be productive to split the sum up into blocks (which can be summed explicitly using the geometric series formula) and computing the remainder on the blocks before combining the blocks and doing the grand remainder.

    We could consider a block size N such that:

    \frac{1-a^{-(N+1)}}{1-a^{-1}} > p

    (which we can obtained by solving \frac{1-a^{-(x+1)}}{1-a^{-1}}=p numerically)

    This thread is not really number theory (the remainders are fractional not integer) this is more like numerical analysis or mathematical software, so I am moving this to the "other advanced topics" area of MHF.


    CB
    Last edited by CaptainBlack; November 20th 2011 at 11:04 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: October 3rd 2011, 01:12 PM
  2. Finding a limit. Finding Maclaurin series.
    Posted in the Calculus Forum
    Replies: 2
    Last Post: May 18th 2010, 11:04 PM
  3. Finding a series ?
    Posted in the Calculus Forum
    Replies: 6
    Last Post: October 17th 2009, 02:47 AM
  4. Help in finding the sum of the series!
    Posted in the Calculus Forum
    Replies: 2
    Last Post: June 9th 2008, 04:30 AM
  5. Finding the sum of a series
    Posted in the Calculus Forum
    Replies: 3
    Last Post: November 2nd 2007, 09:26 AM

Search Tags


/mathhelpforum @mathhelpforum