Update appNew update is available. Click here to update.

Tribonacci series in c

19RH1A05H6 Thanvi lahari Pendyala
Last Updated: Dec 27, 2022

Introduction

All of us know the Fibonacci series and how to write code to produce the series in most languages. Fibonacci series are produced in such a way that the sum of the recent two elements in the series is equal to the third element. But have you ever heard of the tribonacci series? No worries, we have got you covered. Let’s learn what the tribonacci series is, how to write a code to produce these series and how they are different from the Fibonacci series in this article.

tribonacci series

Tribonacci series

The tribonacci series is similar to the Fibonacci series. In the Fibonacci series, each term is a sum of two preceding numbers, whereas, in the tribonacci series, each term is a sum of three preceding numbers. The tribonacci series are as follows:

0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, 121415, ……. so on. The general formula to calculate the tribonacci series manually is:

t(n) = t(n-1) + t(n-2) + t(n-3)

Where t(0) = t(1) = 0, t(2) = 1 at the starting of the series.

We have two approaches to produce ‘n’ tribonacci series. They are 

  • simple/brute force method
  • recursion method.  

Simple/brute force method

In this simple method, we declare three variables and assign them with values 0, 0, and 1 in the beginning. Later we add all three terms and produce the next term of the series. Using this approach, let’s learn how to print the ‘n’ tribonacci series in C.

#include<stdio.h>
int main()
{
	int n, t1=0,t2=0,t3=1,t4,i;
	n = 6;
	printf("%d\t%d\t%d",t1,t2,t3);
	for(i=3;i<n;i++)
	{
		t4=a+b+c;
		printf("\t%d ",d);
		t1=t2;
		t2=t3;
		t3=t4;
	}
}


Output

0 0 1 1 2 4

Explanation:

Fourth term: 0+0+1=1 
Fifth Term: 0+1+1=2
Sixth term: 1+1+2=4
and so on.

In the above code, we considered three variables a,b,c whose values are 0,0,1 respectively. The fourth term can be produced by adding the variables (a+b+c = 0+0+1). Then we assign the current term values to the previous numbers and perform addition again, producing the above series.

Complexities

Time Complexity

The time complexity of the given solution is O(N), where N is the number of times the sum is performed to obtain a new term in the series.

Reason: We are performing the sum ‘n’ times to generate new terms; hence the complexity is O(N).

Auxiliary space complexity 

The Auxiliary space complexity of the given solution is O(1).

Reason: We need a variable to store the sum of preceding terms; hence the space complexity is O(1).

Recursion method

#include <stdio.h>
int printSeries(int n)
{
	if (n == 0 || n == 1 || n == 2)
		return 0;
	else if (n == 3)
		return 1;
	else
		return printSeries(n - 1) + printSeries(n - 2) + printSeries(n - 3);
}
void tribonacci(int n)
{
	for (int i = 1; i < n; i++)
		printf("%d\t", printSeries(i));
}
int main()
{
	int n = 5;
	tribonacci(n);
	return 0;
}


Output

0 0 1 1 2

working of stack in recursive method

The number 1 is sent as an argument to the function printSeries from the function tribonacci. As the number is equal to 1, the control will go to the first if statement and the function will return 0. Then the next number will be 2, and the function will return 0 again. Then the function will return 1 for the number 3. Now, as the number is 4, the function will return the sum of 0+0+1, which is 1, and similarly, for the number 5, it will return 2.

In the above code, we considered a single variable to read the required number of terms in the series. We then used recursion to add the three preceding numbers if the value of n is other than 0,1,2 or 3. This will produce the output as shown below.

Complexities

Time Complexity

The time complexity of the given solution is O(3N), where N is the number of times recursion took place.

Reason: We are performing 4 comparisons, 2 additions, and 3 subtractions in recursion; hence the complexity is O(3N).

Auxiliary space complexity 

The Auxiliary space complexity of the given solution is O(N).

Reason: We store the sum and update it ‘N’ times while performing the recursion; hence the space complexity is O(N).

Finding Nth Tribonacci Number

#include <stdio.h>
int getTrib(int n) {
	if (n == 0)
    		return 0;
   	if (n < 3)
		return 1;
	int x = 0, y = 1, z = 1, result;
  	for (int i = 3; i <= n; i++) {
    		ans = x + y + z;
     		x = y;
     		y = z;
     		z = result;
   	}
   	return result;
}

int main() {
	int n=5;
	printf("The %dth number in the tribonacci series is %d ",n, getTrib(n));
}


Output:

The 5th number in the tribonacci series is 2

We add the preceding three numbers in the above code and produce a tribonacci series. Then we iterate over the tribonacci series, find the Nth term, and print that number.  

Complexities

Time Complexity

The time complexity of the given solution is O(N), where N is the number of times the sum is performed to find the nth term in the series.

Reason: We are performing the sum ‘n’ times to generate new terms and then find the nth term; hence the complexity is O(N).

Auxiliary space complexity 

The Auxiliary space complexity of the given solution is O(1).

Reason: We need a variable to store the nth term found; hence the space complexity is O(1).

You can implement code by yourself with the help of an online editor.

Frequently Asked Questions

What is the tribonacci series?

The tribonacci series is a sequence where each fourth term is the addition of three preceding terms in the sequence. It can be defined as t(n) = t(n-1) + t(n-2) + t(n-3) where t(0) = t(1) = 0, t(2) = 1.

What is the difference between the Fibonacci series and the tribonacci series?

The Fibonacci series is a sequence where each third term is the addition of two preceding terms, whereas the tribonacci series is a sequence where each fourth term is the addition of three preceding terms in the sequence.

What are the numbers in the tribonacci series?

The numbers in the tribonacci series are 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, 121415, ……. so on.

What are the time complexities of the tribonacci series?

The time complexity is O(n) for the simple/brute force approach, and the time complexity is O(3N) for the recursive approach of the tribonacci series.

Which approach is better; recursive or simple?

The simple approach is better than the recursive approach because the recursive approach has exponential complexity, whereas the simple approach has linear complexity.

Conclusion

We have discussed the concept of the tribonacci series in this article. You can now take the code in this article as a reference and create the tribonacci series in different languages.

Hey Ninjas! We hope this blog helped you better to understand the tribonacci series concept. Please check out Coding Ninjas for more unique courses and guided paths. Also, try CodeStudio for more exciting articles, interview experiences, and fantastic Data Structures and Algorithms problems. Please upvote our blog to help the other ninjas grow.

Happy Coding!

Was this article helpful ?
0 upvotes