Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Sum of Sequence

Last Updated on April 1, 2022 by Ria Pathak

### CONCEPTS USED:

Collatz conjecture

Easy

### PROBLEM STATEMENT`(`SIMPLIFIED`)`:

Given a positive number `N`, write a recursive function and sum all the number until `N` reaches to `1` after performing the following two operations :

1. If `N` is even, then `N` `=` `N/2`
1. If `N` is odd, then `N` `=` `3*N+1`

NOTE:

1. Sum of all number can be large, so print the answer with modulo `(10^9+7)`

2. It is guaranted that `N` will become `1` at some point.

#### For Example :

``````Input: N = 5

Output: 36

Explanation:

The sequence will be [5, 16, 8, 4, 2, 1]

5 is odd so N becomes 5*3 + 1 = 16
sum becomes 5 + 16 = 21

16 is even so N becomes 16/2 = 8
sum becomes  21 + 8 = 29

8 is even so N becomes 8/2 = 4
sum becomes  29 + 4 = 33

4 is even so N becomes 4/2 = 2
sum becomes  33 + 2 = 35

2 is even so N becomes 2/2 = 1
sum becomes  35 + 1 = 36

N becomes 1 , so return sum = 36``````

See original problem statement here

Do You Know?

This problem is known as Collatz conjecture and it is an open problem with unknown `Time Complexity`.

### SOLVING APPROACH:

1. Initialize a `Sum` variable as `0` and pass it to the recursive function.

2. Check if the value of `N` is `Even` or `Odd`. If `Even`, change `Sum` to `Sum` + `current-value-of-N` and reduce `N` to `N/2`, and pass both values to the recursive function.

3. If `N` is odd, change `Sum` to `Sum` + `current-value-of-N` and increment `N` by `N*3 + 1`, and pass these values to the recursive function.

4. If at any point `N` becomes `1`, return the `Sum` + `current-value-of-N` i.e. `Sum` + `1`.

### SOLUTIONS:

```#include
#define mod 1000000007

int sumOfSequence(int n, int sum){

if(n == 1)
return (sum + n)%mod;
if(n%2 == 0)
return sumOfSequence(n/2, (sum + n)%mod);
else
return sumOfSequence(n*3 + 1, (sum + n)%mod);
}

int main()
{
int t; scanf("%d", &t);
while(t--){
int n; scanf("%d", &n);
printf("%d\n", sumOfSequence(n, 0));
}
return 0;
}

```
```#include
using namespace std;
#define mod 1000000007

int sumOfSequence(int n, int sum){

if(n == 1)
return (sum + n)%mod;
if(n%2 == 0)
return sumOfSequence(n/2, (sum + n)%mod);
else
return sumOfSequence(n*3 + 1, (sum + n)%mod);
}

int main()
{
int t; cin>>t;
while(t--){
int n; cin>>n;
cout<< sumOfSequence(n, 0)<<"\n";
}
return 0;
}
```
```import java.util.*;
import java.io.*;

public class Main {
static int mod = 1000000007;
static int sumOfSequence(int n, int sum){

if(n == 1)
return (sum + n)%mod;

if(n%2 == 0)
return sumOfSequence(n/2, (sum + n)%mod);
else
return sumOfSequence(n*3 + 1, (sum + n)%mod);
}

public static void main(String args[]) throws IOException {

Scanner sc = new Scanner(System.in);
int t = sc.nextInt();

while(t != 0){
int n = sc.nextInt();
System.out.println(sumOfSequence(n, 0));
t--;
}
}
}
```
```def sumOfSequence(n, sum):

mod = 1000000007

if(n == 1):
return (sum + n)%mod

if(n%2 == 0):
return sumOfSequence(n//2, (sum + n)%mod)

else:
return sumOfSequence(n*3 + 1, (sum + n)%mod)

for _ in range(int(input())):

n = int(input())
print(sumOfSequence(n, 0))
```

[forminator_quiz id="998"]

This article tried to discuss Collatz conjecture. Hope this blog helps you understand and solve the problem. To practice more problems on Collatz conjecture you can check out MYCODE | Competitive Programming.