Sum of Sequence

CONCEPTS USED:

Collatz conjecture

DIFFICULTY LEVEL:

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

2. 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))

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.