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:-
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:
- To find the sum of series we can easily take a as common and find the sum of and multiply it with a.
- Steps to find the sum of the above series.
- Here, it can be resolved that:
- Here, it can be resolved that:
If we denote,
then,
and,
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)