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.
What is 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.
C
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.
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
C
C
#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
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). You can also read about dynamic array in c.
Finding Nth Tribonacci Number
C
C
#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 an example of Tribonacci series?
The Tribonacci sequence is similar to Fibonacci sequence, where each term is the sum of the three preceding terms. The first three terms of the Tribonacci sequence are 0, 0, and 1. 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. Example of first 10 terms in a Tribonacci series are 0, 0, 1, 1, 2, 4, 7, 13, 24, 44.
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 is the Tribonacci series algorithm?
The Tribonacci series algorithm prints a sequence where each term is the sum of the three preceding terms. It starts with the initial values of 0, 0, and 1. 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. The algorithm calculates the next terms by adding the three previous terms and continues the process.
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 Coding Ninjas Studio for more exciting articles, interview experiences, and fantastic Data Structures and Algorithms problems. Please upvote our blog to help the other ninjas grow.
39+ registered 