Sunday, October 19, 2025
HomeData Modelling & AISum of N-terms of geometric progression for larger values of N |...

Sum of N-terms of geometric progression for larger values of N | Set 2 (Using recursion)

A Geometric series is a series with a constant ratio between successive terms. The first term of the series is denoted by a and the common ratio is denoted by r. The series looks like this:- a, ar, ar^2, ar^3, ar^4,...
The task is to find the sum of such a series, mod M.

Examples:  

Input:  a = 1, r = 2, N = 10000, M = 10000
Output:  8751

Input:  a = 1, r = 4, N = 10000, M = 100000
Output:  12501 

Approach: 

  1. To find the sum of series a + ar + ar^2 + ar^3 + . . . . + ar^N       we can easily take a as common and find the sum of 1 + r + r^2 + r^3 + . . . . + r^N       and multiply it with a.
  2. Steps to find the sum of the above series. 
    • Here, it can be resolved that: 
      [1 + r + r^2 + r^3 + . . . + r^(2*n+1)] = (1+r)*(1 + (r^2) + (r^2)^2 + (r^2)^3 + . . . + (r^2)^n)

If we denote, 
Sum(r, n) = 1 + r + r^2 + r^3 + . . . . + r^N.       then, 
Sum(r, 2 * n + 1) = (1 + r) * Sum(r^2, n).       and, 
Sum(r, 2 * n) = 1 + (r * (1 + r) * Sum(r^2, n - 1)).
This will work as our recursive case. 

  • So, the base cases are:
Sum(r, 0) = 1.
Sum(r, 1) = 1 + r.

Below is the implementation of the above approach.  

C++




// C++ implementation to
// illustrate the program
#include <iostream>
using namespace std;
 
// Function to calculate the sum
// recursively
int SumGPUtil(long long int r,
              long long int n,
              long long int m)
{
     
    // Base cases
    if (n == 0)
        return 1;
    if (n == 1)
        return (1 + r) % m;
     
    long long int ans;
    // If n is odd
    if (n % 2 == 1)
    {
        ans = (1 + r) *
              SumGPUtil((r * r) % m,
                        (n - 1) / 2, m);
    }
    else
    {
         
        // If n is even
        ans = 1 + (r * (1 + r) *
             SumGPUtil((r * r) % m,
                       (n / 2) - 1, m));
    }
    return (ans % m);
}
 
// Function to print the long value of Sum
void SumGP(long long int a,
           long long int r,
           long long int N,
           long long int M)
{
    long long int answer;
     
    answer = a * SumGPUtil(r, N, M);
    answer = answer % M;
     
    cout << answer << endl;
}
 
// Driver Code
int main()
{
     
    // First element
    long long int a = 1;
     
    // Common difference
    long long int r = 4;
     
    // Number of elements
    long long int N = 10000;
     
    // Mod value
    long long int M = 100000;
 
    SumGP(a, r, N, M);
 
    return 0;
}
 
// This code is contributed by sanjoy_62


Java




// Java implementation to
// illustrate the program
import java.io.*;
 
class GFG{
 
// Function to calculate the sum
// recursively
static long SumGPUtil(long r, long n,
                      long m)
{
     
    // Base cases
    if (n == 0)
        return 1;
    if (n == 1)
        return (1 + r) % m;
     
    long ans;
     
    // If n is odd
    if (n % 2 == 1)
    {
        ans = (1 + r) *
              SumGPUtil((r * r) % m,
                        (n - 1) / 2, m);
    }
    else
    {
        // If n is even
        ans = 1 + (r * (1 + r) *
             SumGPUtil((r * r) % m,
                       (n / 2) - 1, m));
    }
     
    return (ans % m);
}
 
// Function to print the value of Sum
static void SumGP(long a, long r,
                  long N, long M)
{
    long answer;
    answer = a * SumGPUtil(r, N, M);
    answer = answer % M;
     
    System.out.println(answer);
}
 
// Driver Code
public static void main (String[] args)
{
     
    // First element
    long a = 1;
     
    // Common difference
    long r = 4;
     
    // Number of elements
    long N = 10000;
     
    // Mod value
    long M = 100000;
 
    SumGP(a, r, N, M);
}
}
 
// This code is contributed by sanjoy_62


Python3




# Python3 implementation to illustrate the program
 
# Function to calculate the sum
# recursively
def SumGPUtil (r, n, m):
     
    # Base cases
    if n == 0: return 1
    if n == 1: return (1 + r) % m
   
    # If n is odd
    if n % 2 == 1:
        ans = (1 + r) * SumGPUtil(r * r % m,
                                  (n - 1)//2,
                                  m)
    else:
        #If n is even
        ans = 1 + r * (1 + r) * SumGPUtil(r * r % m,
                                          n//2 - 1,
                                          m)
   
    return ans % m
 
# Function to print the value of Sum
def SumGP (a, r, N, M):
     
    answer = a * SumGPUtil(r, N, M)
    answer = answer % M
    print(answer)
 
#Driver Program
if __name__== '__main__':
 
    a = 1 # first element
    r = 4 # common difference
    N = 10000 # Number of elements
    M = 100000 # Mod value
 
    SumGP(a, r, N, M)


C#




// C# implementation to
// illustrate the program
using System;
 
class GFG{
 
// Function to calculate the sum
// recursively
static long SumGPUtil(long r, long n,
                      long m)
{
     
    // Base cases
    if (n == 0)
        return 1;
    if (n == 1)
        return (1 + r) % m;
     
    long ans;
     
    // If n is odd
    if (n % 2 == 1)
    {
        ans = (1 + r) *
              SumGPUtil((r * r) % m,
                        (n - 1) / 2, m);
    }
    else
    {
         
        // If n is even
        ans = 1 + (r * (1 + r) *
             SumGPUtil((r * r) % m,
                       (n / 2) - 1, m));
    }
    return (ans % m);
}
 
// Function to print the value of Sum
static void SumGP(long a, long r,
                  long N, long M)
{
    long answer;
    answer = a * SumGPUtil(r, N, M);
    answer = answer % M;
     
    Console.WriteLine(answer);
}
 
// Driver Code
public static void Main()
{
     
    // First element
    long a = 1;
     
    // Common difference
    long r = 4;
     
    // Number of elements
    long N = 10000;
     
    // Mod value
    long M = 100000;
 
    SumGP(a, r, N, M);
}
}
 
// This code is contributed by sanjoy_62


Javascript




<script>
 
// Javascript implementation to
// illustrate the program
 
// Function to calculate the sum
// recursively
function SumGPUtil(r, n, m)
{
       
    // Base cases
    if (n == 0)
        return 1;
    if (n == 1)
        return (1 + r) % m;
       
    let ans;
       
    // If n is odd
    if (n % 2 == 1)
    {
        ans = (1 + r) *
              SumGPUtil((r * r) % m,
                        (n - 1) / 2, m);
    }
    else
    {
        // If n is even
        ans = 1 + (r * (1 + r) *
             SumGPUtil((r * r) % m,
                       (n / 2) - 1, m));
    }
       
    return (ans % m);
}
   
// Function to print the value of Sum
function SumGP(a, r, N, M)
{
    let answer;
    answer = a * SumGPUtil(r, N, M);
    answer = answer % M;
       
    document.write(answer);
}
   
 
// Driver Code
     
    // First element
    let a = 1;
       
    // Common difference
    let r = 4;
       
    // Number of elements
    let N = 10000;
       
    // Mod value
    let M = 100000;
   
    SumGP(a, r, N, M);
                       
</script>


Output: 

12501

 

Time complexity: O(log N)

Auxiliary Space: O(1)
 

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

RELATED ARTICLES

Most Popular

Dominic
32361 POSTS0 COMMENTS
Milvus
88 POSTS0 COMMENTS
Nango Kala
6728 POSTS0 COMMENTS
Nicole Veronica
11892 POSTS0 COMMENTS
Nokonwaba Nkukhwana
11954 POSTS0 COMMENTS
Shaida Kate Naidoo
6852 POSTS0 COMMENTS
Ted Musemwa
7113 POSTS0 COMMENTS
Thapelo Manthata
6805 POSTS0 COMMENTS
Umr Jansen
6801 POSTS0 COMMENTS